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

A penalty method for generalized Nash equilibrium problems

1. 

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

Received  December 2010 Revised  July 2011 Published  November 2011

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.
Citation: 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
References:
[1]

K. J. Arrow and G. Debreu, Existence of an equilibrium for a competitive economy,, Econometrica, 22 (1954), 265. doi: 10.2307/1907353.

[2]

D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods,", Athena Scientific, (1996).

[3]

B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function,, Mathematical Programming, 88 (2000), 211. doi: 10.1007/PL00011375.

[4]

F. H. Clarke, "Optimization and Nonsmooth Analysis,", John Wiley & Sons, (1983).

[5]

G. Debreu, Definite and semidefinite quadratic forms,, Econometrica, 20 (1952), 295. doi: 10.2307/1907852.

[6]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Mathematical Programming, 117 (2009), 163. 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. doi: 10.1137/090749499.

[8]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems,, Annals of Operations Research, 175 (2010), 177. doi: 10.1007/s10479-009-0653-x.

[9]

M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm,, Technical Report 2008-007, (2008), 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. 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. doi: 10.1007/11600930_23.

[12]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM Journal on Control and Optimization, 15 (1977), 959. doi: 10.1137/0315061.

[13]

L. W. McKenzie, On the existence of a general equilibrium for a competitive market,, Econometrica, 27 (1959), 54. 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. doi: 10.1073/pnas.36.1.48.

[15]

J. F. Nash, Non-cooperative games,, Annals of Mathematics (2), 54 (1951), 286. doi: 10.2307/1969529.

[16]

J. V. Neumann, Zur theorie der gesellschaftsspiele,, Mathematische Annalen, 100 (1928), 295. doi: 10.1007/BF01448847.

[17]

J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior,", Princeton University Press, (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. 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. 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.

[21]

J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games,, Econometrica, 33 (1965), 520. 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. 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. 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. doi: 10.2307/1907353.

[2]

D. P. Bertsekas, "Constrained Optimization and Lagrange Multiplier Methods,", Athena Scientific, (1996).

[3]

B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function,, Mathematical Programming, 88 (2000), 211. doi: 10.1007/PL00011375.

[4]

F. H. Clarke, "Optimization and Nonsmooth Analysis,", John Wiley & Sons, (1983).

[5]

G. Debreu, Definite and semidefinite quadratic forms,, Econometrica, 20 (1952), 295. doi: 10.2307/1907852.

[6]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Mathematical Programming, 117 (2009), 163. 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. doi: 10.1137/090749499.

[8]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems,, Annals of Operations Research, 175 (2010), 177. doi: 10.1007/s10479-009-0653-x.

[9]

M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm,, Technical Report 2008-007, (2008), 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. 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. doi: 10.1007/11600930_23.

[12]

R. Mifflin, Semismooth and semiconvex functions in constrained optimization,, SIAM Journal on Control and Optimization, 15 (1977), 959. doi: 10.1137/0315061.

[13]

L. W. McKenzie, On the existence of a general equilibrium for a competitive market,, Econometrica, 27 (1959), 54. 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. doi: 10.1073/pnas.36.1.48.

[15]

J. F. Nash, Non-cooperative games,, Annals of Mathematics (2), 54 (1951), 286. doi: 10.2307/1969529.

[16]

J. V. Neumann, Zur theorie der gesellschaftsspiele,, Mathematische Annalen, 100 (1928), 295. doi: 10.1007/BF01448847.

[17]

J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior,", Princeton University Press, (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. 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. 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.

[21]

J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games,, Econometrica, 33 (1965), 520. 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. 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. 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 & 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 & 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 & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018123

[4]

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

[5]

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 & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008

[6]

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

[7]

Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235

[8]

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, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019034

[9]

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 & Management Optimization, 2010, 6 (2) : 363-380. doi: 10.3934/jimo.2010.6.363

[10]

Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty. Journal of Industrial & Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006

[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 & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143

[13]

Hao-Chun Lu. An efficient convexification method for solving generalized geometric problems. Journal of Industrial & Management Optimization, 2012, 8 (2) : 429-455. doi: 10.3934/jimo.2012.8.429

[14]

T. Gnana Bhaskar, S. Köksal, V. Lakshmikantham. Generalized quasilinearization method for semilinear hyperbolic problems. Discrete & Continuous Dynamical Systems - A, 2003, 9 (5) : 1263-1275. doi: 10.3934/dcds.2003.9.1263

[15]

Shingo Takeuchi. The basis property of generalized Jacobian elliptic functions. Communications on Pure & Applied Analysis, 2014, 13 (6) : 2675-2692. doi: 10.3934/cpaa.2014.13.2675

[16]

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

[17]

Zhong-Qing Wang, Ben-Yu Guo, Yan-Na Wu. Pseudospectral method using generalized Laguerre functions for singular problems on unbounded domains. Discrete & Continuous Dynamical Systems - B, 2009, 11 (4) : 1019-1038. doi: 10.3934/dcdsb.2009.11.1019

[18]

Fang Chen, Ning Gao, Yao- Lin Jiang. On product-type generalized block AOR method for augmented linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 797-809. doi: 10.3934/naco.2012.2.797

[19]

Matthias Gerdts, Martin Kunkel. A nonsmooth Newton's method for discretized optimal control problems with state and control constraints. Journal of Industrial & Management Optimization, 2008, 4 (2) : 247-270. doi: 10.3934/jimo.2008.4.247

[20]

Andy M. Yip, Wei Zhu. A fast modified Newton's method for curvature based denoising of 1D signals. Inverse Problems & Imaging, 2013, 7 (3) : 1075-1097. doi: 10.3934/ipi.2013.7.1075

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]