Article Contents
Article Contents

# Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints

• * Corresponding author: Xiaona Fan
• In this paper, we utilize a new homotopy method to solve generalized Nash equilibrium problem with equality and inequality constraints on unbounded sets. Based on the existing homotopy method, we establish a new homotopy equation by introducing a suitable perturbation on the equality constraint, the existence and the global convergence of homotopy path under certain assumptions have also been proved. In the proposed method, the initial point only needs to satisfy the inequality constraints. Compared with the existing homotopy method, this method expands the scope of the initial points and provides the convenience for solving generalized Nash equilibrium problem. The numerical results illustrate the effectiveness of this method.

Mathematics Subject Classification: Primary: 90C33, 90C30; Secondary: 65C20.

 Citation:

• Table 1.  The numerical results of Example 3.1

 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.5, 0.5)^T$ A1 0.049842 19 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6755\times 10^{-7}$ A2 0.068653 23 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $4.8879\times 10^{-7}$ $(0.6, 0.4, 0.5, 0.5)^T$ A1 0.032000 11 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.2632\times 10^{-7}$ A2 0.047000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $8.5698\times 10^{-7}$ $(0.3, 0.4, 0.6, 0.5)^T$ A1 0.015000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.3661\times 10^{-7}$ $(0.3, 0.4, 0.5, 0.4)^T$ A1 0.016000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6057\times 10^{-7}$

Table 2.  The numerical results of Example 3.2

 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.7, 0.3, 0.3, 0.7)^T$ A1 0.017811 20 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.5142\times 10^{-7}$ A2 0.052286 23 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.2044\times 10^{-7}$ $(0.7, 0.3, 0.5, 0.5)^T$ A1 0.016000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.7536\times 10^{-7}$ A2 0.032000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.0169\times 10^{-7}$ $(0.6, 0.3, 0.6, 0.5)^T$ A1 0.016000 10 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $2.0758\times 10^{-7}$ $(0.6, 0.5, 0.6, 0.5)^T$ A1 0.015000 9 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $8.4904\times 10^{-7}$

Table 3.  The numerical results of Example 3.3

 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.2, 0.8)^T$ A1 0.060919 27 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $2.9945\times 10^{-7}$ A2 0.102540 102 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.3449\times 10^{-7}$ $(0.9, 0.1, 0.1, 0.9)^T$ A1 0.036579 33 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $4.5683\times 10^{-7}$ A2 0.097798 128 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.6001\times 10^{-7}$ $(0.3, 0.8, 0.4, 0.5)^T$ A1 0.050146 18 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $8.8414\times 10^{-7}$ $(0.2, 0.6, 0.3, 0.4)^T$ A1 0.032000 22 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $1.6179\times 10^{-7}$

Table 4.  The numerical results of Example 3.4

 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.2, 0.8)^T$ A1 0.090294 34 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.9066\times 10^{-7}$ A2 0.170305 79 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $8.9245\times 10^{-7}$ $(0.7, 0.3, 0.3, 0.7)^T$ A1 0.074322 31 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.4454\times 10^{-7}$ A2 0.096164 64 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $6.9529\times 10^{-7}$ $(0.3, 0.8, 0.4, 0.7)^T$ A1 0.071024 32 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $7.7431\times 10^{-7}$ $(0.4, 0.5, 0.4, 0.5)^T$ A1 0.031000 17 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $1.3352\times 10^{-7}$
•  [1] E. L. Allgower and K. Georg, Numerical Continuation Method: An Introduction, Springer-Vergal, Berlin, New York, 1990. doi: 10.1007/978-3-642-61257-2. [2] D. Aussel, R. Correa and M. Marechal, Gap functions for quasivariational inequalities and generalized Nash equilibrium problems, J. Optim. Theory Appl., 151 (2011), 474-488.  doi: 10.1007/s10957-011-9898-z. [3] H. Dietrich, A smooth dual gap function solution to a class of quasivariational inequalities, J. Math. Anal. Appl., 235 (1999), 380-393.  doi: 10.1006/jmaa.1999.6405. [4] A. Dreves, F. Facchinei, A. Fischer and M. Herrich, A new error bound result for Generalized Nash Equilibrium Problems and its algorithmic application, Comput. Optim. Appl., 59 (2014), 63-84.  doi: 10.1007/s10589-013-9586-z. [5] A. Dreves, F. Facchinei, C. Kanzow and S. Sagratella, On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., 21 (2011), 1082-1108.  doi: 10.1137/100817000. [6] F. Fachhinei, A. Fischer and M. Herrich, A family of Newton methods for nonsmooth constrained systems with nonisolated solutions, Math. Methods Oper. Res., 77 (2013), 433-443.  doi: 10.1007/s00186-012-0419-0. [7] F. Facchinei, A. Fischer and M. Herrich, An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions, Math. Program., 146 (2014), 1-36.  doi: 10.1007/s10107-013-0676-6. [8] F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, Annals of Operations Research, 175 (2010), 177-211.  doi: 10.1007/s10479-009-0653-x. [9] F. Facchinei, C. Kanzow and S. K. Sagratella, The semismooth Newton method for the solution of quasi-variational inequalities, Computational Optimization and Applications, 62 (2015), 85-109.  doi: 10.1007/s10589-014-9686-4. [10] F. Facchinei and J.-S. Pang, Nash equilibria: The variational approach, in Convex Optimization in Signal Processing and Communications, D. P. Palomar and Y. C. Eldar, eds., Cambridge University Press, Cambridge, (2010), 443–493. [11] M. Fukushima, A class of gap functions for quasi-variational inequality problems, J. Ind. Manag. Optim., 3 (2007), 165-171.  doi: 10.3934/jimo.2007.3.165. [12] N. Harms, T. Hoheisel and C. Kanzow, On a smooth dual gap function for a class of quasi-variational inequalities, J. Optim. Theory Appl., 163 (2014), 413-438.  doi: 10.1007/s10957-014-0536-4. [13] N. Harms, C. Kanzow and O. Stein, Smoothness properties of a regularized gap function for quasivariational inequalities, Optim. Methods Softw., 29 (2014), 720-750.  doi: 10.1080/10556788.2013.841694. [14] A. von Heusinger and C. Kanzow, Relaxation methods for generalized nash equilibrium problems with inexact line search, Journal of Optimization Theory and Applications, 143 (2009), 159-183.  doi: 10.1007/s10957-009-9553-0. [15] J. B. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications, Environmental Modeling & Assessment, 5 (2000), 63-73. [16] K. Kubota and M. Fukushima, Gap function approach to the generalized Nash equilibrium problem, J. Optim. Theory Appl., 144 (2010), 511-531.  doi: 10.1007/s10957-009-9614-4. [17] M. M. Makela and P. Neittaanmaki, Nonsmooth Optimization, World Scientific, Singapore, 1992. doi: 10.1142/1493. [18] R. B. Myerson, Nash equilibrium and the history of economic theory, Journal of Economic Literature, 37 (1999), 1067-1082. [19] G. L. Naber, Topological methods in Euclidean spaces, Cambridge University Press, 1980. [20] K. Taji, On gap functions for quasi-variational inequalities, Abstract Appl. Anal., 2008 (2008), Art. ID 531361, 7 pp. doi: 10.1155/2008/531361. [21] Q. Xu, X. Dai and B. Yu, Solving generalized Nash equilibrium problem with equality and inequality constraints, Optimization Methods & Software, 24 (2009), 327-337.  doi: 10.1080/10556780802578884.

Tables(4)