A Lyapunov analysis of Korpelevich's extragradient method with fast and flexible extensions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909994852548608 |
|---|---|
| author | Upadhyaya, Manu Latafat, Puya Giselsson, Pontus |
| author_facet | Upadhyaya, Manu Latafat, Puya Giselsson, Pontus |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00119 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Lyapunov analysis of Korpelevich's extragradient method with fast and flexible extensions Upadhyaya, Manu Latafat, Puya Giselsson, Pontus Optimization and Control 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. |
| title | A Lyapunov analysis of Korpelevich's extragradient method with fast and flexible extensions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2502.00119 |