American Institute of Mathematical Sciences

Advanced
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

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

Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[2]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[3]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[4]

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

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[6]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25
[7]

Ethan Akin, Julia Saccamano. Generalized intransitive dice II: Partition constructions. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021005
[8]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[9]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027
[10]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182
[11]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[12]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[13]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[14]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[15]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[16]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[17]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[18]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[19]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[20]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences