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.  Google Scholar

[2]

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

[3]

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

[4]

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

[5]

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

[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.  Google Scholar

[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.  Google Scholar

[8]

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

[9]

M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm,, Technical Report 2008-007, (2008), 2008.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

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

[13]

L. W. McKenzie, On the existence of a general equilibrium for a competitive market,, Econometrica, 27 (1959), 54.  doi: 10.2307/1907777.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

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

[17]

J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior,", Princeton University Press, (1953).   Google Scholar

[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.  Google Scholar

[19]

L. Qi and J. Sun, A nonsmooth version of Newton's method,, Mathematical Programming, 58 (1993), 353.  doi: 10.1007/BF01581275.  Google Scholar

[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.   Google Scholar

[21]

J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games,, Econometrica, 33 (1965), 520.  doi: 10.2307/1911749.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

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

[3]

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

[4]

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

[5]

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

[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.  Google Scholar

[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.  Google Scholar

[8]

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

[9]

M. Fukushima, Restricted generalized Nash equilibria and controlled penalty algorithm,, Technical Report 2008-007, (2008), 2008.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

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

[13]

L. W. McKenzie, On the existence of a general equilibrium for a competitive market,, Econometrica, 27 (1959), 54.  doi: 10.2307/1907777.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

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

[17]

J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior,", Princeton University Press, (1953).   Google Scholar

[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.  Google Scholar

[19]

L. Qi and J. Sun, A nonsmooth version of Newton's method,, Mathematical Programming, 58 (1993), 353.  doi: 10.1007/BF01581275.  Google Scholar

[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.   Google Scholar

[21]

J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games,, Econometrica, 33 (1965), 520.  doi: 10.2307/1911749.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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, 2019, 15 (4) : 1795-1807. 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]

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

[11]

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

[12]

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

[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]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020102

[17]

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

[18]

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

[19]

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

[20]

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

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]