2012, 2(1): 1-18. doi: 10.3934/naco.2012.2.1

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  March 2012

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.
Citation: 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
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]

K. J. Arrow, A utilitarian approach to the concept of equality in public expenditures,, The Quarterly Journal of Economics, 85 (1971), 409. doi: 10.2307/1885930. Google Scholar

[3]

F. Alizadeh and D. Goldfarb, Second-order cone programming,, Mathematical Programming Series B, 9 (2003), 3. doi: 10.1007/s10107-002-0339-5. Google Scholar

[4]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems,, A Quarterly Journal of Operations Research, 5 (2007), 173. doi: 10.1007/s10288-007-0054-4. Google Scholar

[5]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Mathematical Programming Series B, 117 (2007), 163. doi: 10.1007/s10107-007-0160-2. Google Scholar

[6]

M. Fukushima, Z. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems,, SIAM Journal on Optimization, 12 (2001), 436. doi: 10.1137/S1052623400380365. Google Scholar

[7]

J. M. Henderson and R. E. Quandt, "Micreconomic Theory: A Mathematical Approcach,", 3rd edition, (1980). Google Scholar

[8]

H. Kato and M. Fukushima, An SQP-type algorithm for nonlinear second-order cone programs,, Optimization Letters, 1 (2007), 129. doi: 10.1007/s11590-006-0009-2. Google Scholar

[9]

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

[10]

J. F. Nash, 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

[11]

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

[12]

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

[13]

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

[14]

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

[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. doi: 10.1007/s101079900127. Google Scholar

[16]

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

[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. doi: 10.1137/S1052623400379620. Google Scholar

[18]

Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares,, Numerical Algebra, 1 (2011), 15. doi: 10.3934/naco.2011.1.15. Google Scholar

[19]

Y. Wang and L. Zhang, Nonsingularity in second-order cone programming via the smoothing metric projector,, Science China, 53 (2010), 1025. doi: 10.1007/s11425-009-0207-3. 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]

K. J. Arrow, A utilitarian approach to the concept of equality in public expenditures,, The Quarterly Journal of Economics, 85 (1971), 409. doi: 10.2307/1885930. Google Scholar

[3]

F. Alizadeh and D. Goldfarb, Second-order cone programming,, Mathematical Programming Series B, 9 (2003), 3. doi: 10.1007/s10107-002-0339-5. Google Scholar

[4]

F. Facchinei and C. Kanzow, Generalized Nash equilibrium problems,, A Quarterly Journal of Operations Research, 5 (2007), 173. doi: 10.1007/s10288-007-0054-4. Google Scholar

[5]

F. Facchinei, A. Fischer and V. Piccialli, Generalized Nash equilibrium problems and Newton methods,, Mathematical Programming Series B, 117 (2007), 163. doi: 10.1007/s10107-007-0160-2. Google Scholar

[6]

M. Fukushima, Z. Luo and P. Tseng, Smoothing functions for second-order-cone complementarity problems,, SIAM Journal on Optimization, 12 (2001), 436. doi: 10.1137/S1052623400380365. Google Scholar

[7]

J. M. Henderson and R. E. Quandt, "Micreconomic Theory: A Mathematical Approcach,", 3rd edition, (1980). Google Scholar

[8]

H. Kato and M. Fukushima, An SQP-type algorithm for nonlinear second-order cone programs,, Optimization Letters, 1 (2007), 129. doi: 10.1007/s11590-006-0009-2. Google Scholar

[9]

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

[10]

J. F. Nash, 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

[11]

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

[12]

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

[13]

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

[14]

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

[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. doi: 10.1007/s101079900127. Google Scholar

[16]

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

[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. doi: 10.1137/S1052623400379620. Google Scholar

[18]

Y. Yuan, Recent advances in numerical methods for nonlinear equations and nonlinear least squares,, Numerical Algebra, 1 (2011), 15. doi: 10.3934/naco.2011.1.15. Google Scholar

[19]

Y. Wang and L. Zhang, Nonsingularity in second-order cone programming via the smoothing metric projector,, Science China, 53 (2010), 1025. doi: 10.1007/s11425-009-0207-3. Google Scholar

[1]

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

[2]

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

[3]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171

[4]

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

[5]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111

[6]

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

[7]

W. Sarlet, G. E. Prince, M. Crampin. Generalized submersiveness of second-order ordinary differential equations. Journal of Geometric Mechanics, 2009, 1 (2) : 209-221. doi: 10.3934/jgm.2009.1.209

[8]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703

[9]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951

[10]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089

[11]

Liu Yang, Xiaojiao Tong, Yao Xiong, Feifei Shen. A smoothing SAA algorithm for a portfolio choice model based on second-order stochastic dominance measures. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2018198

[12]

Maurizio Grasselli, Morgan Pierre. Convergence to equilibrium of solutions of the backward Euler scheme for asymptotically autonomous second-order gradient-like systems. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2393-2416. doi: 10.3934/cpaa.2012.11.2393

[13]

Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068

[14]

Yaqing Liu, Liancun Zheng. Second-order slip flow of a generalized Oldroyd-B fluid through porous medium. Discrete & Continuous Dynamical Systems - S, 2016, 9 (6) : 2031-2046. doi: 10.3934/dcdss.2016083

[15]

Hancheng Guo, Jie Xiong. A second-order stochastic maximum principle for generalized mean-field singular control problem. Mathematical Control & Related Fields, 2018, 8 (2) : 451-473. doi: 10.3934/mcrf.2018018

[16]

Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010

[17]

Lijun Yi, Zhongqing Wang. Legendre spectral collocation method for second-order nonlinear ordinary/partial differential equations. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 299-322. doi: 10.3934/dcdsb.2014.19.299

[18]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[19]

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529

[20]

José F. Cariñena, Javier de Lucas Araujo. Superposition rules and second-order Riccati equations. Journal of Geometric Mechanics, 2011, 3 (1) : 1-22. doi: 10.3934/jgm.2011.3.1

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]