A Lyapunov analysis of Korpelevich's extragradient method with fast and flexible extensions

2025/01/31 by Upadhyaya, Manu, Latafat, Puya, Giselsson, Pontus
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2502.00119

Abstract

We present a Lyapunov analysis of Korpelevich's extragradient method and establish an O(1/k) last-iterate convergence rate. Building on this, we propose flexible extensions that combine extragradient steps with user-specified directions, guided by a line-search procedure derived from the same Lyapunov analysis. These methods retain global convergence under practical assumptions and can achieve superlinear rates when directions are chosen appropriately. Numerical experiments highlight the simplicity and efficiency of this approach.

Related

• Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments
• Accelerated Extragradient-Type Methods -- Part 2: Generalization and Sublinear Convergence Rates under Co-Hypomonotonicity
• Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates
• Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization
• Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees