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-290. doi: 10.2307/1907353.  Google Scholar

[2]

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

[3]

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

[4]

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

[5]

G. Debreu, Definite and semidefinite quadratic forms, Econometrica, 20 (1952), 295-300. 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-194. 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-2253. doi: 10.1137/090749499.  Google Scholar

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

[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. 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-377. 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-245. 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-972. 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-71. 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-49. doi: 10.1073/pnas.36.1.48.  Google Scholar

[15]

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

[16]

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

[17]

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

[21]

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

[2]

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

[3]

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

[4]

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

[5]

G. Debreu, Definite and semidefinite quadratic forms, Econometrica, 20 (1952), 295-300. 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-194. 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-2253. doi: 10.1137/090749499.  Google Scholar

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

[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. 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-377. 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-245. 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-972. 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-71. 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-49. doi: 10.1073/pnas.36.1.48.  Google Scholar

[15]

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

[16]

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

[17]

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

[21]

J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games, Econometrica, 33 (1965), 520-534. 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-776. 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-806. 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]

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

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
[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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006
[14]

Hengrui Luo, Alice Patania, Jisu Kim, Mikael Vejdemo-Johansson. Generalized penalty for circular coordinate representation. Foundations of Data Science, 2021  doi: 10.3934/fods.2021024
[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]

T. Gnana Bhaskar, S. Köksal, V. Lakshmikantham. Generalized quasilinearization method for semilinear hyperbolic problems. Discrete & 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 & 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 & 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 & Imaging, , () : -. doi: 10.3934/ipi.2021044
[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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy