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

• 成果类型: Article; Early Access
• 署名作者: Upadhyaya, Manu; Latafat, Puya; Giselsson, Pontus
• 署名单位: Lund University; IMT School for Advanced Studies Lucca
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02322-0
• 发表日期: 2026-01-28
• 关键词: monotone inclusions; extragradient method; Lyapunov analysis; superlinear convergence; BACKWARD SPLITTING METHOD; proximal point algorithm; variational-inequalities; saddle-point; monotone; CONVERGENCE; cournot

摘要

We develop a Lyapunov-based analysis of Korpelevich's extragradient method and show that it achieves an o(1/k) last-iterate convergence rate of the constructed Lyapunov function. This Lyapunov function simultaneously upper bounds several standard measures of optimality, which allows our analysis to sharpen existing last-iterate convergence guarantees for these measures. Moreover, the same analysis enables the design of a class of flexible extensions of the extragradient method in which extragradient steps are adaptively blended with user-specified directions via a Lyapunov-guided line-search procedure. These extensions retain global convergence under practical assumptions and can attain superlinear rates when the directions are chosen appropriately. Numerical experiments confirm the simplicity and efficiency of the proposed framework.