A penalty method for generalized Nash equilibrium problems

Yanhong Yuan; Hongwei Zhang; Liwei Zhang

doi:10.3934/jimo.2012.8.51

Article Contents

2012, Volume 8, Issue 1: 51-65. Doi: 10.3934/jimo.2012.8.51

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

A penalty method for generalized Nash equilibrium problems

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

Received: December 2010

Revised: July 2011

Published: January 2012

Abstract / Introduction Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.