A penalty method for generalized Nash equilibrium problems

Previous Article
Global and global linear convergence of smoothing algorithm for the Cartesian $P_*(\kappa)$-SCLCP
JIMO Home
This Issue
Next Article
A note on the subtree ordered median problem in networks based on nestedness property

January 2012, 8(1): 51-65. doi: 10.3934/jimo.2012.8.51

A penalty method for generalized Nash equilibrium problems

Yanhong Yuan ^1, , Hongwei Zhang ^1, and Liwei Zhang ^1,

1.	School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China, China, China

Received December 2010 Revised July 2011 Published November 2011

Abstract
Related Papers

This paper considers a penalty algorithm for solving the generalized Nash equilibrium problem (GNEP). Under the GNEP-MFCQ at a limiting point of the sequence generated by the algorithm, we demonstrate that the limit point is a solution to the GNEP and the parameter becomes a constant after a finite iterations. We formulate the Karush-Kuhn-Tucker conditions for a penalized problem into a system of nonsmooth equations and demonstrate the nonsingularity of its Clarke’s generalized Jacobian at the KKT point under the so-called GNEP-Second Order Sufficient Condition. The nonsingularity facilitates the application of the smoothing Newton method for the global convergence and local quadratic rate. Finally, the numerical results are reported to show the effectiveness of the penalty method in solving generalized Nash equilibrium problem.

Keywords: Clarke’s generalized Jacobian., smoothing Newton method, Generalized Nash equilibrium, penalty method.

Mathematics Subject Classification: Primary: 91A06; Secondary: 91-08, 90C9.

Citation: Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51

References:

[1]	K. J. Arrow and G. Debreu, Existence of an equilibrium for a competitive economy, Econometrica, 22 (1954), 265-290. doi: 10.2307/1907353.
[2]	D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods," Athena Scientific, Belmont, Mass., 1996.
[3]	B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function, Mathematical Programming, 88 (2000), 211-216. doi: 10.1007/PL00011375.
[4]	F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley & Sons, New York, 1983.
[5]	G. Debreu, Definite and semidefinite quadratic forms, Econometrica, 20 (1952), 295-300. doi: 10.2307/1907852.
[6]	F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods, Mathematical Programming, 117 (2009), 163-194. doi: 10.1007/s10107-007-0160-2.
[7]	F. Facchinei and C. Kanzow, Penalty methods for the solution of generalized nash equilibrium problems, SIAM Journal on Optimization, 20 (2010), 2228-2253. doi: 10.1137/090749499.
[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]	M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm, Technical Report 2008-007, Department of Applied Mathematics and Physics, Kyoto University, July 2008.
[10]	A. Heusinger and C. Kanzow, Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type funcitons, Computational Optimization and Applications, 43 (2009), 353-377. doi: 10.1007/s10589-007-9145-6.
[11]	A. Kesselman, S. Leonardi and V. Bonifaci, Game-theoretic analysis of internet switching with selfish users, Lecture Notes in Computer Science, 3828 (2005), 236-245. doi: 10.1007/11600930_23.
[12]	R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization, 15 (1977), 959-972. doi: 10.1137/0315061.
[13]	L. W. McKenzie, On the existence of a general equilibrium for a competitive market, Econometrica, 27 (1959), 54-71. doi: 10.2307/1907777.
[14]	J. F. Nash, Jr., Equilibrium points in $n$-person games, Proceedings of the National Academy of Sciences of the USA, 36 (1950), 48-49. doi: 10.1073/pnas.36.1.48.
[15]	J. F. Nash, Non-cooperative games, Annals of Mathematics (2), 54 (1951), 286-295. doi: 10.2307/1969529.
[16]	J. V. Neumann, Zur theorie der gesellschaftsspiele, Mathematische Annalen, 100 (1928), 295-320. doi: 10.1007/BF01448847.
[17]	J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior," Princeton University Press, Princeton, 1953.
[18]	J.-S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Computational Management Science, 2 (2005), 21-56. doi: 10.1007/s10287-004-0010-0.
[19]	L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275.
[20]	L. Qi, D. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Mathematical Programming, 87 (2000), 1-35.
[21]	J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games, Econometrica, 33 (1965), 520-534. doi: 10.2307/1911749.
[22]	D. Sun, The strong second order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications, Mathematics of Operations Research, 31 (2006), 761-776. doi: 10.1287/moor.1060.0195.
[23]	J. Sun, D. Sun and L. Qi, A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems, SIAM Journal on Optimization, 14 (2004), 783-806. doi: 10.1137/S1052623400379620.

show all references

References:

[1]	K. J. Arrow and G. Debreu, Existence of an equilibrium for a competitive economy, Econometrica, 22 (1954), 265-290. doi: 10.2307/1907353.
[2]	D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods," Athena Scientific, Belmont, Mass., 1996.
[3]	B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function, Mathematical Programming, 88 (2000), 211-216. doi: 10.1007/PL00011375.
[4]	F. H. Clarke, "Optimization and Nonsmooth Analysis," John Wiley & Sons, New York, 1983.
[5]	G. Debreu, Definite and semidefinite quadratic forms, Econometrica, 20 (1952), 295-300. doi: 10.2307/1907852.
[6]	F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods, Mathematical Programming, 117 (2009), 163-194. doi: 10.1007/s10107-007-0160-2.
[7]	F. Facchinei and C. Kanzow, Penalty methods for the solution of generalized nash equilibrium problems, SIAM Journal on Optimization, 20 (2010), 2228-2253. doi: 10.1137/090749499.
[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]	M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm, Technical Report 2008-007, Department of Applied Mathematics and Physics, Kyoto University, July 2008.
[10]	A. Heusinger and C. Kanzow, Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type funcitons, Computational Optimization and Applications, 43 (2009), 353-377. doi: 10.1007/s10589-007-9145-6.
[11]	A. Kesselman, S. Leonardi and V. Bonifaci, Game-theoretic analysis of internet switching with selfish users, Lecture Notes in Computer Science, 3828 (2005), 236-245. doi: 10.1007/11600930_23.
[12]	R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM Journal on Control and Optimization, 15 (1977), 959-972. doi: 10.1137/0315061.
[13]	L. W. McKenzie, On the existence of a general equilibrium for a competitive market, Econometrica, 27 (1959), 54-71. doi: 10.2307/1907777.
[14]	J. F. Nash, Jr., Equilibrium points in $n$-person games, Proceedings of the National Academy of Sciences of the USA, 36 (1950), 48-49. doi: 10.1073/pnas.36.1.48.
[15]	J. F. Nash, Non-cooperative games, Annals of Mathematics (2), 54 (1951), 286-295. doi: 10.2307/1969529.
[16]	J. V. Neumann, Zur theorie der gesellschaftsspiele, Mathematische Annalen, 100 (1928), 295-320. doi: 10.1007/BF01448847.
[17]	J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior," Princeton University Press, Princeton, 1953.
[18]	J.-S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Computational Management Science, 2 (2005), 21-56. doi: 10.1007/s10287-004-0010-0.
[19]	L. Qi and J. Sun, A nonsmooth version of Newton's method, Mathematical Programming, 58 (1993), 353-367. doi: 10.1007/BF01581275.
[20]	L. Qi, D. Sun and G. Zhou, A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Mathematical Programming, 87 (2000), 1-35.
[21]	J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games, Econometrica, 33 (1965), 520-534. doi: 10.2307/1911749.
[22]	D. Sun, The strong second order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications, Mathematics of Operations Research, 31 (2006), 761-776. doi: 10.1287/moor.1060.0195.
[23]	J. Sun, D. Sun and L. Qi, A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems, SIAM Journal on Optimization, 14 (2004), 783-806. doi: 10.1137/S1052623400379620.

[1]	Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[2]	Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091
[3]	Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[4]	Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[5]	Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1
[6]	Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008
[7]	Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413
[8]	Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235
[9]	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 and Optimization, 2020, 10 (1) : 75-92. doi: 10.3934/naco.2019034
[10]	Xiao-Hong Liu, Wei-Zhe Gu. Smoothing Newton algorithm based on a regularized one-parametric class of smoothing functions for generalized complementarity problems over symmetric cones. Journal of Industrial and Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363
[11]	R. Baier, M. Dellnitz, M. Hessel-von Molo, S. Sertl, I. G. Kevrekidis. The computation of convex invariant sets via Newton's method. Journal of Computational Dynamics, 2014, 1 (1) : 39-69. doi: 10.3934/jcd.2014.1.39
[12]	Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143
[13]	Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty. Journal of Industrial and Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006
[14]	Shingo Takeuchi. The basis property of generalized Jacobian elliptic functions. Communications on Pure and Applied Analysis, 2014, 13 (6) : 2675-2692. doi: 10.3934/cpaa.2014.13.2675
[15]	Hengrui Luo, Alice Patania, Jisu Kim, Mikael Vejdemo-Johansson. Generalized penalty for circular coordinate representation. Foundations of Data Science, 2021, 3 (4) : 729-767. doi: 10.3934/fods.2021024
[16]	T. Gnana Bhaskar, S. Köksal, V. Lakshmikantham. Generalized quasilinearization method for semilinear hyperbolic problems. Discrete and Continuous Dynamical Systems, 2003, 9 (5) : 1263-1275. doi: 10.3934/dcds.2003.9.1263
[17]	Hao-Chun Lu. An efficient convexification method for solving generalized geometric problems. Journal of Industrial and Management Optimization, 2012, 8 (2) : 429-455. doi: 10.3934/jimo.2012.8.429
[18]	Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[19]	Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems and Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044
[20]	Yan Li, Liping Zhang. A smoothing Newton method preserving nonnegativity for solving tensor complementarity problems with $ P_0 $ mappings. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022041

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Yanhong Yuan Hongwei Zhang Liwei Zhang
on Google Scholar
Yanhong Yuan Hongwei Zhang Liwei Zhang

[Back to Top]