Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Upadhyaya, Manu LU orcid ; Latafat, Puya and Giselsson, Pontus LU orcid (2026) In Mathematical Programming
Abstract

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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
epub
subject
keywords
Extragradient method, Lyapunov analysis, Monotone inclusions, Superlinear convergence
in
Mathematical Programming
publisher
Springer Nature
external identifiers
  • scopus:105029179059
ISSN
0025-5610
DOI
10.1007/s10107-025-02322-0
language
English
LU publication?
yes
id
a9371abc-b458-41f0-abba-9bfa055b0baa
date added to LUP
2026-02-20 14:34:45
date last changed
2026-02-20 14:35:57
@article{a9371abc-b458-41f0-abba-9bfa055b0baa,
  abstract     = {{<p>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.</p>}},
  author       = {{Upadhyaya, Manu and Latafat, Puya and Giselsson, Pontus}},
  issn         = {{0025-5610}},
  keywords     = {{Extragradient method; Lyapunov analysis; Monotone inclusions; Superlinear convergence}},
  language     = {{eng}},
  publisher    = {{Springer Nature}},
  series       = {{Mathematical Programming}},
  title        = {{A Lyapunov analysis of Korpelevich’s extragradient method with fast and flexible extensions}},
  url          = {{http://dx.doi.org/10.1007/s10107-025-02322-0}},
  doi          = {{10.1007/s10107-025-02322-0}},
  year         = {{2026}},
}