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-290. 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-415. doi: 10.2307/1885930.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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

[7]

J. M. Henderson and R. E. Quandt, "Micreconomic Theory: A Mathematical Approcach," 3rd edition, Mcgraw-Hill College, 1980. Google Scholar

[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.  Google Scholar

[9]

L. W. McKenzie, On the existence of a general equilibrium for a competitive market, Econometrica, 27 (1959), 54-71. 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-49. doi: 10.1073/pnas.36.1.48.  Google Scholar

[11]

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

[12]

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

[13]

J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior," Princeton University Press, Princeton, 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-56. 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-35. 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-534. 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-806. doi: 10.1137/S1052623400379620.  Google Scholar

[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.  Google Scholar

[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.  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-290. 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-415. doi: 10.2307/1885930.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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

[7]

J. M. Henderson and R. E. Quandt, "Micreconomic Theory: A Mathematical Approcach," 3rd edition, Mcgraw-Hill College, 1980. Google Scholar

[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.  Google Scholar

[9]

L. W. McKenzie, On the existence of a general equilibrium for a competitive market, Econometrica, 27 (1959), 54-71. 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-49. doi: 10.1073/pnas.36.1.48.  Google Scholar

[11]

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

[12]

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

[13]

J. V. Neumann and O. Morgenstern, "Theory of Games and Economic Behavior," Princeton University Press, Princeton, 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-56. 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-35. 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-534. 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-806. doi: 10.1137/S1052623400379620.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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 & 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 & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

[3]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021030

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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, 2020, 16 (3) : 1171-1185. doi: 10.3934/jimo.2018198

[15]

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

[16]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[17]

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

[18]

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

[19]

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

[20]

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

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]