The Gauss-Seidel Method for Generalized Nash Equilibrium Problems of Polynomials

2020/09/06 by Jiawang Nie, Nie, Jiawang, Xindong Tang +3
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.2009.02809

openalex publication_date 2020/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper concerns the generalized Nash equilibrium problem of polynomials (GNEPP). We apply the Gauss-Seidel method and Lasserre type Moment-SOS relaxations to solve GNEPPs. The convergence of the Gauss-Seidel method is known for some special GNEPPs, such as generalized potential games (GPGs). We give a sufficient condition for GPGs and propose a numerical certificate, based on Putinar's Positivstellensatz. Numerical examples for both convex and nonconvex GNEPPs are given for demonstrating the efficiency of the proposed method.

Citations

• Decomposition algorithms for generalized potential games
• Generalized Nash equilibrium problems and Newton methods

Related

• Convex Generalized Nash Equilibrium Problems and Polynomial Optimization
• On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials
• Nash Equilibrium Problems of Polynomials
• Generalized Nash equilibrium problems with quasi-linear constraints
• Rational Generalized Nash Equilibrium Problems