Solving Monotone Linear-Quadratic Generalized Nash Equilibrium Problems via Quadratic Programming
TL;DR
Theoretical analysis and numerical experiments show the proposed methods substantially outperform the existing approaches to solve monotone linear-quadratic v-GNE problems.
Abstract
We consider generalized Nash equilibrium problems among $N$ players with convex quadratic costs and shared affine constraints, assuming only that the game's pseudogradient is merely monotone. We show that computing a variational generalized Nash equilibrium (v-GNE) is equivalent to solving a single convex quadratic program (QP) derived from the players'joint Karush--Kuhn--Tucker conditions. Building on this, we show that the regularization of such a QP yields an $\varepsilon$-approximated v-GNE with suboptimality vanishing linearly in the regularization parameter. Next, we propose an accelerated proximal-point scheme and an accelerated projected-gradient method, both attaining an $\mathcal O(1/k^2)$-approximated v-GNE at the $k$-th iteration. We also demonstrate that an invertible Jacobian of the game allows for reduction to a lower-dimensional QP. Theoretical analysis and numerical experiments show the proposed methods substantially outperform the existing approaches to solve monotone linear-quadratic v-GNE problems.