On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials

DOI10.1007/S10915-023-02138-0zbMATH Open1519.91013arXiv2208.03931OpenAlexW4321183763MaRDI QIDQ6159023FDOQ6159023

Authors: Kisun Lee, Xindong Tang 

Publication date: 20 June 2023

Published in: Journal of Scientific Computing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2208.03931

Recommendations

• Convex generalized Nash equilibrium problems and polynomial optimization
• The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
• Solving generalized Nash equilibrium problem with equality and inequality constraints
• Methods for solving generalized Nash equilibrium
• Computing generalized Nash equilibria by polynomial programming

zbMATH Keywords

polynomial optimizationgeneralized Nash equilibrium problemnumerical algebraic geometrypolyhedral homotopymoment-SOS relaxation

Mathematics Subject Classification ID

Numerical algebraic geometry (65H14) Equilibrium refinements (91A11) Polynomial optimization (90C23)

Cites Work

• HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Algorithm 795
• HomotopyContinuation.jl: a package for homotopy continuation in Julia
• Augmented Lagrangian methods for the solution of generalized Nash equilibrium problems
• Generalized Nash equilibrium problems
• Global optimization with polynomials and the problem of moments
• Introduction to Interval Analysis
• Generalized Nash games and quasi-variational inequalities
• On generalized Nash games and variational inequalities
• Nash equilibria: the variational approach
• GloptiPoly 3: moments, optimization and semidefinite programming
• Title not available (Why is that?)
• A Social Equilibrium Existence Theorem*
• Existence of an Equilibrium for a Competitive Economy
• Penalty Methods for the Solution of Generalized Nash Equilibrium Problems
• Relaxation methods for generalized Nash equilibrium problems with inexact line search
• On the solution of the KKT conditions of generalized Nash equilibrium problems
• Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions
• Approximations of Nash equilibria
• Distributed Power Allocation With Rate Constraints in Gaussian Parallel Interference Channels
• Optimality conditions and finite convergence of Lasserre's hierarchy
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• The number of roots of a system of equations
• Algorithm 921: alphaCertified: certifying solutions to polynomial systems
• Positive polynomials in control.
• An introduction to polynomial and semi-algebraic optimization
• Basic Algebraic Geometry 2
• Certifying convergence of Lasserre's hierarchy via flat truncation
• The BKK root count in $\mathbf {C}^n$
• Nonlinear programming
• Optimization over polynomials: selected topics
• Trace test
• Euclidean distance degree and mixed volume
• Exact penalization of generalized Nash equilibrium problems
• The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
• Convex generalized Nash equilibrium problems and polynomial optimization

Cited In (10)

• Implementing real polyhedral homotopy
• Nash equilibrium problems of polynomials
• A differentiable homotopy approach for solving polynomial optimization problems and noncooperative games
• Computing generalized Nash equilibria by polynomial programming
• The Gauss-Seidel method for generalized Nash equilibrium problems of polynomials
• Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets
• LATIN 2004: Theoretical Informatics
• Solving generalized Nash equilibrium problem with equality and inequality constraints
• Convex generalized Nash equilibrium problems and polynomial optimization
• Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints

This page was built for publication: On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159023)