TY - JOUR
T1 - On the Polyhedral Homotopy Method for Solving Generalized Nash Equilibrium Problems of Polynomials
AU - Lee, Kisun
AU - Tang, Xindong
N1 - Publisher Copyright:
© 2023, The Author(s).
PY - 2023/2/17
Y1 - 2023/2/17
N2 - The generalized Nash equilibrium problem (GNEP) is a kind of game to find strategies for a group of players such that each player’s objective function is optimized. Solutions for GNEPs are called generalized Nash equilibria (GNEs). In this paper, we propose a numerical method for finding GNEs of GNEPs of polynomials based on the polyhedral homotopy continuation and the Moment-SOS hierarchy of semidefinite relaxations. We show that our method can find all GNEs if they exist, or detect the nonexistence of GNEs, under some genericity assumptions. Some numerical experiments are made to demonstrate the efficiency of our method.
AB - The generalized Nash equilibrium problem (GNEP) is a kind of game to find strategies for a group of players such that each player’s objective function is optimized. Solutions for GNEPs are called generalized Nash equilibria (GNEs). In this paper, we propose a numerical method for finding GNEs of GNEPs of polynomials based on the polyhedral homotopy continuation and the Moment-SOS hierarchy of semidefinite relaxations. We show that our method can find all GNEs if they exist, or detect the nonexistence of GNEs, under some genericity assumptions. Some numerical experiments are made to demonstrate the efficiency of our method.
KW - Generalized Nash equilibrium problem
KW - Polyhedral homotopy
KW - Polynomial optimization
KW - Moment-SOS relaxation
KW - Numerical algebraic geometry
UR - http://www.scopus.com/inward/record.url?scp=85148333722&partnerID=8YFLogxK
UR - http://10.1007/s10915-023-02192-8
U2 - 10.1007/s10915-023-02138-0
DO - 10.1007/s10915-023-02138-0
M3 - Journal article
AN - SCOPUS:85148333722
SN - 0885-7474
VL - 95
JO - Journal of Scientific Computing
JF - Journal of Scientific Computing
IS - 1
M1 - 13
ER -