  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.
