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]

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

[2]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[3]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[4]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[5]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[6]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[7]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[8]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[9]

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020355

[10]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[11]

Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327

[12]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345

[13]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346

[14]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[15]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171

[16]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[17]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[18]

Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278

[19]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363

[20]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]