# American Institute of Mathematical Sciences

October  2019, 15(4): 1795-1807. doi: 10.3934/jimo.2018123

## Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints

 School of Science, Nanjing University of Posts and Telecommunications, Nanjing, Jiangsu 210023, China

* Corresponding author: Xiaona Fan

Received  July 2017 Revised  May 2018 Published  August 2018

In this paper, we utilize a new homotopy method to solve generalized Nash equilibrium problem with equality and inequality constraints on unbounded sets. Based on the existing homotopy method, we establish a new homotopy equation by introducing a suitable perturbation on the equality constraint, the existence and the global convergence of homotopy path under certain assumptions have also been proved. In the proposed method, the initial point only needs to satisfy the inequality constraints. Compared with the existing homotopy method, this method expands the scope of the initial points and provides the convenience for solving generalized Nash equilibrium problem. The numerical results illustrate the effectiveness of this method.

Citation: 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
##### References:

show all references

##### References:
The numerical results of Example 3.1
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.5, 0.5)^T$ A1 0.049842 19 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6755\times 10^{-7}$ A2 0.068653 23 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $4.8879\times 10^{-7}$ $(0.6, 0.4, 0.5, 0.5)^T$ A1 0.032000 11 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.2632\times 10^{-7}$ A2 0.047000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $8.5698\times 10^{-7}$ $(0.3, 0.4, 0.6, 0.5)^T$ A1 0.015000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.3661\times 10^{-7}$ $(0.3, 0.4, 0.5, 0.4)^T$ A1 0.016000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6057\times 10^{-7}$
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.5, 0.5)^T$ A1 0.049842 19 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6755\times 10^{-7}$ A2 0.068653 23 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $4.8879\times 10^{-7}$ $(0.6, 0.4, 0.5, 0.5)^T$ A1 0.032000 11 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.2632\times 10^{-7}$ A2 0.047000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $8.5698\times 10^{-7}$ $(0.3, 0.4, 0.6, 0.5)^T$ A1 0.015000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $1.3661\times 10^{-7}$ $(0.3, 0.4, 0.5, 0.4)^T$ A1 0.016000 12 $(0.5000, 0.5000, 0.7743, 0.2257)^T$ $5.6057\times 10^{-7}$
The numerical results of Example 3.2
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.7, 0.3, 0.3, 0.7)^T$ A1 0.017811 20 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.5142\times 10^{-7}$ A2 0.052286 23 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.2044\times 10^{-7}$ $(0.7, 0.3, 0.5, 0.5)^T$ A1 0.016000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.7536\times 10^{-7}$ A2 0.032000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.0169\times 10^{-7}$ $(0.6, 0.3, 0.6, 0.5)^T$ A1 0.016000 10 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $2.0758\times 10^{-7}$ $(0.6, 0.5, 0.6, 0.5)^T$ A1 0.015000 9 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $8.4904\times 10^{-7}$
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.7, 0.3, 0.3, 0.7)^T$ A1 0.017811 20 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.5142\times 10^{-7}$ A2 0.052286 23 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.2044\times 10^{-7}$ $(0.7, 0.3, 0.5, 0.5)^T$ A1 0.016000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $1.7536\times 10^{-7}$ A2 0.032000 11 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $5.0169\times 10^{-7}$ $(0.6, 0.3, 0.6, 0.5)^T$ A1 0.016000 10 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $2.0758\times 10^{-7}$ $(0.6, 0.5, 0.6, 0.5)^T$ A1 0.015000 9 $(0.5000, 0.5000, 0.7500, 0.2500)^T$ $8.4904\times 10^{-7}$
The numerical results of Example 3.3
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.2, 0.8)^T$ A1 0.060919 27 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $2.9945\times 10^{-7}$ A2 0.102540 102 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.3449\times 10^{-7}$ $(0.9, 0.1, 0.1, 0.9)^T$ A1 0.036579 33 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $4.5683\times 10^{-7}$ A2 0.097798 128 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.6001\times 10^{-7}$ $(0.3, 0.8, 0.4, 0.5)^T$ A1 0.050146 18 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $8.8414\times 10^{-7}$ $(0.2, 0.6, 0.3, 0.4)^T$ A1 0.032000 22 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $1.6179\times 10^{-7}$
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.2, 0.8)^T$ A1 0.060919 27 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $2.9945\times 10^{-7}$ A2 0.102540 102 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.3449\times 10^{-7}$ $(0.9, 0.1, 0.1, 0.9)^T$ A1 0.036579 33 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $4.5683\times 10^{-7}$ A2 0.097798 128 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $9.6001\times 10^{-7}$ $(0.3, 0.8, 0.4, 0.5)^T$ A1 0.050146 18 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $8.8414\times 10^{-7}$ $(0.2, 0.6, 0.3, 0.4)^T$ A1 0.032000 22 $(0.2165, 0.7835, 0.4331, 0.5669)^T$ $1.6179\times 10^{-7}$
The numerical results of Example 3.4
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.2, 0.8)^T$ A1 0.090294 34 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.9066\times 10^{-7}$ A2 0.170305 79 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $8.9245\times 10^{-7}$ $(0.7, 0.3, 0.3, 0.7)^T$ A1 0.074322 31 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.4454\times 10^{-7}$ A2 0.096164 64 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $6.9529\times 10^{-7}$ $(0.3, 0.8, 0.4, 0.7)^T$ A1 0.071024 32 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $7.7431\times 10^{-7}$ $(0.4, 0.5, 0.4, 0.5)^T$ A1 0.031000 17 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $1.3352\times 10^{-7}$
 $x_0$ method CPU IT $x^*$ $\mu^*$ $(0.8, 0.2, 0.2, 0.8)^T$ A1 0.090294 34 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.9066\times 10^{-7}$ A2 0.170305 79 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $8.9245\times 10^{-7}$ $(0.7, 0.3, 0.3, 0.7)^T$ A1 0.074322 31 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $9.4454\times 10^{-7}$ A2 0.096164 64 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $6.9529\times 10^{-7}$ $(0.3, 0.8, 0.4, 0.7)^T$ A1 0.071024 32 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $7.7431\times 10^{-7}$ $(0.4, 0.5, 0.4, 0.5)^T$ A1 0.031000 17 $(0.4420, 0.5580, 0.6384, 0.3616)^T$ $1.3352\times 10^{-7}$
 [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] 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 [4] Chunyang Zhang, Shugong Zhang, Qinghuai Liu. Homotopy method for a class of multiobjective optimization problems with equilibrium constraints. Journal of Industrial & Management Optimization, 2017, 13 (1) : 81-92. doi: 10.3934/jimo.2016005 [5] Ouayl Chadli, Gayatri Pany, Ram N. Mohapatra. Existence and iterative approximation method for solving mixed equilibrium problem under generalized monotonicity in Banach spaces. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019034 [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] Qilin Wang, Shengji Li. Lower semicontinuity of the solution mapping to a parametric generalized vector equilibrium problem. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1225-1234. doi: 10.3934/jimo.2014.10.1225 [8] Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015 [9] Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013 [10] Liyan Qi, Xiantao Xiao, Liwei Zhang. On the global convergence of a parameter-adjusting Levenberg-Marquardt method. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 25-36. doi: 10.3934/naco.2015.5.25 [11] Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics & Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1 [12] Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153 [13] Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2019060 [14] Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015 [15] Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 [16] Eric Cancès, Claude Le Bris. Convergence to equilibrium of a multiscale model for suspensions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 449-470. doi: 10.3934/dcdsb.2006.6.449 [17] Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial & Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717 [18] Figen Özpinar, Fethi Bin Muhammad Belgacem. The discrete homotopy perturbation Sumudu transform method for solving partial difference equations. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 615-624. doi: 10.3934/dcdss.2019039 [19] Piotr Kokocki. Homotopy invariants methods in the global dynamics of strongly damped wave equation. Discrete & Continuous Dynamical Systems - A, 2016, 36 (6) : 3227-3250. doi: 10.3934/dcds.2016.36.3227 [20] Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721

2018 Impact Factor: 1.025