Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Automated tight Lyapunov analysis for first-order methods

Upadhyaya, Manu LU orcid ; Banert, Sebastian LU ; Taylor, Adrien B. and Giselsson, Pontus LU orcid (2024) In Mathematical Programming
Abstract
We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider (i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components, (ii) first-order methods that can be written as a linear system on state-space form in feedback interconnection with the subdifferentials of the functional components of the objective function, and (iii) quadratic Lyapunov inequalities that can be used to draw convergence conclusions. We present a necessary and sufficient condition for the existence of a quadratic Lyapunov inequality within a predefined class of... (More)
We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider (i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components, (ii) first-order methods that can be written as a linear system on state-space form in feedback interconnection with the subdifferentials of the functional components of the objective function, and (iii) quadratic Lyapunov inequalities that can be used to draw convergence conclusions. We present a necessary and sufficient condition for the existence of a quadratic Lyapunov inequality within a predefined class of Lyapunov inequalities, which amounts to solving a small-sized semidefinite program. We showcase our methodology on several first-order methods that fit the framework. Most notably, our methodology allows us to significantly extend the region of parameter choices that allow for duality gap convergence in the Chambolle–Pock method when the linear operator is the identity mapping. (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
in
Mathematical Programming
publisher
Springer Nature
external identifiers
  • scopus:85186177721
ISSN
1436-4646
DOI
10.1007/s10107-024-02061-8
project
Automatic Lyapunov analysis of optimization algorithms
language
English
LU publication?
yes
id
635b5baa-18b3-47f0-8be8-8c94b947e19f
date added to LUP
2024-02-26 17:05:29
date last changed
2024-03-20 15:19:25
@article{635b5baa-18b3-47f0-8be8-8c94b947e19f,
  abstract     = {{We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider (i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components, (ii) first-order methods that can be written as a linear system on state-space form in feedback interconnection with the subdifferentials of the functional components of the objective function, and (iii) quadratic Lyapunov inequalities that can be used to draw convergence conclusions. We present a necessary and sufficient condition for the existence of a quadratic Lyapunov inequality within a predefined class of Lyapunov inequalities, which amounts to solving a small-sized semidefinite program. We showcase our methodology on several first-order methods that fit the framework. Most notably, our methodology allows us to significantly extend the region of parameter choices that allow for duality gap convergence in the Chambolle–Pock method when the linear operator is the identity mapping.}},
  author       = {{Upadhyaya, Manu and Banert, Sebastian and Taylor, Adrien B. and Giselsson, Pontus}},
  issn         = {{1436-4646}},
  language     = {{eng}},
  month        = {{02}},
  publisher    = {{Springer Nature}},
  series       = {{Mathematical Programming}},
  title        = {{Automated tight Lyapunov analysis for first-order methods}},
  url          = {{http://dx.doi.org/10.1007/s10107-024-02061-8}},
  doi          = {{10.1007/s10107-024-02061-8}},
  year         = {{2024}},
}