# American Institute of Mathematical Sciences

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. [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. [3] F. Alizadeh and D. Goldfarb, Second-order cone programming,, Mathematical Programming Series B, 9 (2003), 3. 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. 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. 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. doi: 10.1137/S1052623400380365. [7] J. M. Henderson and R. E. Quandt, "Micreconomic Theory: A Mathematical Approcach,", 3rd edition, (1980). [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. [9] L. W. McKenzie, On the existence of a general equilibrium for a competitive market,, Econometrica, 27 (1959), 54. 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. doi: 10.1073/pnas.36.1.48. [11] J. F. Nash, Non-cooperative games,, Annals of Mathematics, 54 (1951), 286. doi: 10.2307/1969529. [12] J. V. Neumann, Zur theorie der gesellschaftsspiele,, Mathematische Annalen, 100 (1928), 295. doi: 10.1007/BF01448847. [13] J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior,", Princeton University Press, (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. 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. doi: 10.1007/s101079900127. [16] J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games,, Econometrica, 33 (1965), 520. 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. doi: 10.1137/S1052623400379620. [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. [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.

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. [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. [3] F. Alizadeh and D. Goldfarb, Second-order cone programming,, Mathematical Programming Series B, 9 (2003), 3. 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. 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. 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. doi: 10.1137/S1052623400380365. [7] J. M. Henderson and R. E. Quandt, "Micreconomic Theory: A Mathematical Approcach,", 3rd edition, (1980). [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. [9] L. W. McKenzie, On the existence of a general equilibrium for a competitive market,, Econometrica, 27 (1959), 54. 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. doi: 10.1073/pnas.36.1.48. [11] J. F. Nash, Non-cooperative games,, Annals of Mathematics, 54 (1951), 286. doi: 10.2307/1969529. [12] J. V. Neumann, Zur theorie der gesellschaftsspiele,, Mathematische Annalen, 100 (1928), 295. doi: 10.1007/BF01448847. [13] J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior,", Princeton University Press, (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. 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. doi: 10.1007/s101079900127. [16] J. B. Rosen, Existence and uniqueness of equilibrium points for concave $n$-person games,, Econometrica, 33 (1965), 520. 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. doi: 10.1137/S1052623400379620. [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. [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.
 [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, 2017, 13 (5) : 1-13. 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] 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 [9] 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 [10] 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 [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: