A smoothing Newton method for generalized Nash equilibrium problems with second-order cone  constraints

Yanhong Yuan; Hongwei Zhang; Liwei Zhang

doi:10.3934/naco.2012.2.1

Article Contents

2012, Volume 2, Issue 1: 1-18. Doi: 10.3934/naco.2012.2.1

This issue Previous Article Next Article Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints

A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints

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

Received: December 2010

Revised: May 2011

Published: February 2012

Abstract Related Papers Cited by

Abstract

We consider a type of generalized Nash equilibrium problems with second-order cone constraints. The Karush-Kuhn-Tucker system can be formulated as a system of semismooth equations involving metric projectors. Furthermore, the smoothing Newton method is given to get a Karush-Kuhn-Tucker point of the problem. The nonsingularity of Clarke's generalized Jacobian of the Karush-Kuhn-Tucker system, which is needed in the convergence analysis of smoothing Newton method, is demonstrated under the so-called constraint nondegeneracy condition in generalized Nash equilibrium problems and pseudo-strong second order optimality condition. At last, we take some experiments, in which the smoothing Newton method is applied. Furthermore, we get the normalized equilibria in the constraint-shared case. The numerical results show that the smoothing Newton method has a good performance in solving this type of generalized Nash equilibrium problems.

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]	K. J. Arrow, A utilitarian approach to the concept of equality in public expenditures, The Quarterly Journal of Economics, 85 (1971), 409-415.doi: 10.2307/1885930.
[3]	F. Alizadeh and D. Goldfarb, Second-order cone programming, Mathematical Programming Series B, 9 (2003), 3-51.doi: 10.1007/s10107-002-0339-5.
[4]	F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems, A Quarterly Journal of Operations Research, 5 (2007), 173-210.doi: 10.1007/s10288-007-0054-4.
[5]	F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods, Mathematical Programming Series B, 117 (2007), 163-194.doi: 10.1007/s10107-007-0160-2.
[6]	M. Fukushima, Z. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM Journal on Optimization, 12 (2001), 436-460.doi: 10.1137/S1052623400380365.
[7]	J. M. Henderson and R. E. Quandt, "Micreconomic Theory: A Mathematical Approcach," 3^rd edition, Mcgraw-Hill College, 1980.
[8]	H. Kato and M. Fukushima, An SQP-type algorithm for nonlinear second-order cone programs, Optimization Letters, 1 (2007), 129-144.doi: 10.1007/s11590-006-0009-2.
[9]	L. W. McKenzie, On the existence of a general equilibrium for a competitive market, Econometrica, 27 (1959), 54-71.doi: 10.2307/1907777.
[10]	J. F. Nash, 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.
[11]	J. F. Nash, Non-cooperative games, Annals of Mathematics, 54 (1951), 286-295.doi: 10.2307/1969529.
[12]	J. V. Neumann, Zur theorie der gesellschaftsspiele, Mathematische Annalen, 100 (1928), 295-320.doi: 10.1007/BF01448847.
[13]	J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior," Princeton University Press, Princeton, 1953.
[14]	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.
[15]	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 Series A, 87 (2000), 1-35.doi: 10.1007/s101079900127.
[16]	J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games, Econometrica, 33 (1965), 520-534.doi: 10.2307/1911749.
[17]	J. Sun, D. Sun and L. Qi, A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimizationproblems, SIAM Journal on Optimization, 14 (2003), 783-806.doi: 10.1137/S1052623400379620.
[18]	Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numerical Algebra, Control and Optimization, 1 (2011), 15-34.doi: 10.3934/naco.2011.1.15.
[19]	Y. Wang and L. Zhang, Nonsingularity in second-order cone programming via the smoothing metric projector, Science China, 53 (2010), 1025-1038.doi: 10.1007/s11425-009-0207-3.