The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials

Jiawang Nie; Xindong Tang; Lingling Xu

doi:10.1007/s10589-020-00242-7

The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials

Jiawang Nie^*, Xindong Tang, Lingling Xu

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

5 Citations (Scopus)

Abstract

This paper concerns the generalized Nash equilibrium problem of polynomials (GNEPP). We apply the Gauss–Seidel method and 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.

Original language	English
Pages (from-to)	529–557
Number of pages	29
Journal	Computational Optimization and Applications
Volume	78
Early online date	12 Nov 2020
DOIs	https://doi.org/10.1007/s10589-020-00242-7
Publication status	Published - Jan 2021

User-Defined Keywords

Generalized Nash equilibrium problem
Gauss–Seidel method
Polynomial
Generalized potential game
Moment-SOS hierarchy

Access to Document

10.1007/s10589-020-00242-7

Cite this

@article{2580edcf9759428ea1bf93d0078cea1d,

title = "The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials",

abstract = "This paper concerns the generalized Nash equilibrium problem of polynomials (GNEPP). We apply the Gauss–Seidel method and 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{\textquoteright}s Positivstellensatz. Numerical examples for both convex and nonconvex GNEPPs are given for demonstrating the efficiency of the proposed method. ",

keywords = "Generalized Nash equilibrium problem, Gauss–Seidel method, Polynomial, Generalized potential game, Moment-SOS hierarchy",

author = "Jiawang Nie and Xindong Tang and Lingling Xu",

year = "2021",

month = jan,

doi = "10.1007/s10589-020-00242-7",

language = "English",

volume = "78",

pages = "529–557",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer Netherlands",

}

TY - JOUR

T1 - The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials

AU - Nie, Jiawang

AU - Tang, Xindong

AU - Xu, Lingling

PY - 2021/1

Y1 - 2021/1

N2 - This paper concerns the generalized Nash equilibrium problem of polynomials (GNEPP). We apply the Gauss–Seidel method and 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.

AB - This paper concerns the generalized Nash equilibrium problem of polynomials (GNEPP). We apply the Gauss–Seidel method and 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.

KW - Generalized Nash equilibrium problem

KW - Gauss–Seidel method

KW - Polynomial

KW - Generalized potential game

KW - Moment-SOS hierarchy

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-85095991077&partnerID=MN8TOARS

U2 - 10.1007/s10589-020-00242-7

DO - 10.1007/s10589-020-00242-7

M3 - Journal article

SN - 0926-6003

VL - 78

SP - 529

EP - 557

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

ER -

The Gauss–Seidel method for generalized Nash equilibrium problems of polynomials

Abstract

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this