Seminar Details
2023-02-14 (14h) : Tight Lyapunov function existence analysis for first-order methods
At Euler building(room a.002)
Organized by Mathematical Engineering
Speakers :
Gisselson Pontus (Lund University)
,
and
Updhyaya Manu (Lund University)
Abstract :
We present a unifying framework for establishing linear convergence rates for common first-order methods used to solve convex optimization problems. In particular, we consider i) classes of convex optimization problems of finite sum form with (possibly strongly) convex and (possibly) smooth functional components, and ii) first-order methods that can be written in so-called state-space form, i.e., as a linear system in feedback interconnection with the subdifferentials of the functional components of the objective function. The validity of a given target linear convergence rate is established by deriving a necessary and sufficient condition for verifying the existence of a quadratic Lyapunov function for the algorithm and problem class under consideration for the chosen rate, which amounts to the feasibility of a small-sized semidefinite program. This allows us to find the smallest linear convergence rate for which such a quadratic Lyapunov function exists, by bisection search, yielding a tight procedure. The approach is numerically exemplified on several algorithmic schemes.