# 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 and 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-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," 3rd 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.

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. [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," 3rd 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.
 [1] Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050 [2] Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184 [3] Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050 [4] Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030 [5] Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091 [6] Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51 [7] Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171 [8] Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123 [9] 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 and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 [10] Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1 [11] Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021032 [12] 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 and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703 [13] 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 [14] Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951 [15] Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089 [16] 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 and Management Optimization, 2020, 16 (3) : 1171-1185. doi: 10.3934/jimo.2018198 [17] 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 and Applied Analysis, 2012, 11 (6) : 2393-2416. doi: 10.3934/cpaa.2012.11.2393 [18] Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial and Management Optimization, 2022, 18 (1) : 469-486. doi: 10.3934/jimo.2020164 [19] Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 [20] Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068

Impact Factor: