First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems
Authors: Michael I. Jordan, Tianyi Lin, Manolis Zampetakis; Volume 24, Issue 38, Pages 1-46, 2023.
Abstract
This paper focuses on the computation of equilibria in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) where the strategy sets for each player are determined by equality and inequality constraints that may depend on the choices made by rival players. While the convergence properties of certain algorithms have been extensively studied in terms of asymptotic global convergence and local convergence rate, the analysis of iteration complexity is still in its early stages. In this paper, we propose two first-order algorithms, namely the quadratic penalty method (QPM) and the augmented Lagrangian method (ALM), both utilizing an accelerated mirror-prox algorithm as the solver in each inner loop. We establish the nonasymptotic convergence rate for these algorithms and provide a global convergence guarantee for solving monotone and strongly monotone NGNEPs. Furthermore, we present complexity bounds expressed in terms of the number of gradient evaluations. Experimental results demonstrate the effectiveness of our algorithms in practical settings.
[abs]