On the Polyhedral Homotopy Method for Solving Generalized Nash Equilibrium Problems of Polynomials

Kisun Lee, Xindong Tang*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Article number13
Number of pages26
JournalJournal of Scientific Computing
Volume95
DOIs
Publication statusPublished - 17 Feb 2023

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Engineering(all)
  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Generalized Nash equilibrium problem
  • Polyhedral homotopy
  • Polynomial optimization
  • Moment-SOS relaxation
  • Numerical algebraic geometry

Fingerprint

Dive into the research topics of 'On the Polyhedral Homotopy Method for Solving Generalized Nash Equilibrium Problems of Polynomials'. Together they form a unique fingerprint.

Cite this