-
Previous Article
Uncertain portfolio selection with mental accounts and background risk
- JIMO Home
- This Issue
-
Next Article
Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization
Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints
School of Science, Nanjing University of Posts and Telecommunications, Nanjing, Jiangsu 210023, China |
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.
References:
[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. Google Scholar |
[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. Google Scholar |
[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. |
show all references
References:
[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. Google Scholar |
[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. Google Scholar |
[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. |
method | CPU | IT | |||
A1 | 0.049842 | 19 | |||
A2 | 0.068653 | 23 | |||
A1 | 0.032000 | 11 | |||
A2 | 0.047000 | 12 | |||
A1 | 0.015000 | 12 | |||
A1 | 0.016000 | 12 |
method | CPU | IT | |||
A1 | 0.049842 | 19 | |||
A2 | 0.068653 | 23 | |||
A1 | 0.032000 | 11 | |||
A2 | 0.047000 | 12 | |||
A1 | 0.015000 | 12 | |||
A1 | 0.016000 | 12 |
method | CPU | IT | |||
|
A1 | 0.017811 | 20 | ||
A2 | 0.052286 | 23 | |||
A1 | 0.016000 | 11 | |||
A2 | 0.032000 | 11 | |||
A1 | 0.016000 | 10 | |||
A1 | 0.015000 | 9 |
method | CPU | IT | |||
|
A1 | 0.017811 | 20 | ||
A2 | 0.052286 | 23 | |||
A1 | 0.016000 | 11 | |||
A2 | 0.032000 | 11 | |||
A1 | 0.016000 | 10 | |||
A1 | 0.015000 | 9 |
method | CPU | IT | |||
A1 | 0.060919 | 27 | |||
A2 | 0.102540 | 102 | |||
A1 | 0.036579 | 33 | |||
A2 | 0.097798 | 128 | |||
A1 | 0.050146 | 18 | |||
A1 | 0.032000 | 22 |
method | CPU | IT | |||
A1 | 0.060919 | 27 | |||
A2 | 0.102540 | 102 | |||
A1 | 0.036579 | 33 | |||
A2 | 0.097798 | 128 | |||
A1 | 0.050146 | 18 | |||
A1 | 0.032000 | 22 |
method | CPU | IT | |||
A1 | 0.090294 | 34 | |||
A2 | 0.170305 | 79 | |||
A1 | 0.074322 | 31 | |||
A2 | 0.096164 | 64 | |||
A1 | 0.071024 | 32 | |||
A1 | 0.031000 | 17 |
method | CPU | IT | |||
A1 | 0.090294 | 34 | |||
A2 | 0.170305 | 79 | |||
A1 | 0.074322 | 31 | |||
A2 | 0.096164 | 64 | |||
A1 | 0.071024 | 32 | |||
A1 | 0.031000 | 17 |
[1] |
Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091 |
[2] |
Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51 |
[3] |
Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020022 |
[4] |
Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1 |
[5] |
Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005 |
[6] |
Ouayl Chadli, Gayatri Pany, Ram N. Mohapatra. Existence and iterative approximation method for solving mixed equilibrium problem under generalized monotonicity in Banach spaces. Numerical Algebra, Control & Optimization, 2020, 10 (1) : 75-92. doi: 10.3934/naco.2019034 |
[7] |
Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1 |
[8] |
Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006 |
[9] |
Qilin Wang, Shengji Li. Lower semicontinuity of the solution mapping to a parametric generalized vector equilibrium problem. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1225-1234. doi: 10.3934/jimo.2014.10.1225 |
[10] |
Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015 |
[11] |
Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013 |
[12] |
Liyan Qi, Xiantao Xiao, Liwei Zhang. On the global convergence of a parameter-adjusting Levenberg-Marquardt method. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 25-36. doi: 10.3934/naco.2015.5.25 |
[13] |
Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015 |
[14] |
Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics & Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1 |
[15] |
Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153 |
[16] |
Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060 |
[17] |
Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial & Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717 |
[18] |
Figen Özpinar, Fethi Bin Muhammad Belgacem. The discrete homotopy perturbation Sumudu transform method for solving partial difference equations. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 615-624. doi: 10.3934/dcdss.2019039 |
[19] |
Eric Cancès, Claude Le Bris. Convergence to equilibrium of a multiscale model for suspensions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 449-470. doi: 10.3934/dcdsb.2006.6.449 |
[20] |
Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]