Minimax Theory and its Applications 09 (2024), No. 1, 055--084
Copyright Heldermann Verlag 2024
Linear and Superlinear Convergence of a Potential Reduction Algorithm for Generalized Nash Equilibrium Problems
Axel Dreves
Dept. of Aerospace Engineering, nst. for Applied Mathematics and Scientific Computing, Universität der Bundeswehr, München - Neubiberg, Germany
axel.dreves@unibw.de
We present a detailed convergence analysis of the potential reduction algorithm for generalized Nash equilibrium problems (GNEPs), that is known to be a robust method for solving those problems. We prove Q-linear convergence of the merit function and R-linear convergence of the distance of the iterates to the set of KKT-points of the GNEP. Furthermore, we show that the stepsize is bounded from below, implying finite termination of the method for prescribed accuracy. Using a non-fixed linesearch parameter we prove superlinear convergence. Further, we give additional assumptions to transfer the convergence rates to an inexact potential reduction algorithm. By our analysis, we also discover indicators that could be used to estimate the active set at an accumulation point, and hence at a generalized Nash equilibrium, which might be exploited numerically.
Keywords: Generalized Nash equilibrium problem, potential reduction algorithm, linear convergence, superlinear convergence.
MSC: 90C30, 90C51, 91A10, 65B99.
[ Fulltext-pdf (220 KB)] for subscribers only.