  In this paper, we develop a unified framework able to certify both
exponential and subexponential convergence rates for a wide range of iterative
first-order optimization algorithms. To this end, we construct a family of
parameter-dependent nonquadratic Lyapunov functions that can generate
convergence rates in addition to proving asymptotic convergence. Using Integral
Quadratic Constraints (IQCs) from robust control theory, we propose a Linear
Matrix Inequality (LMI) to guide the search for the parameters of the Lyapunov
function in order to establish a rate bound. Based on this result, we formulate
a Semidefinite Programming (SDP) whose solution yields the best convergence
rate that can be certified by the class of Lyapunov functions under
consideration. We illustrate the utility of our results by analyzing the
gradient method, proximal algorithms and their accelerated variants for
(strongly) convex problems. We also develop the continuous-time counterpart,
whereby we analyze the gradient flow and the continuous-time limit of
Nesterov's accelerated method.

Optimization and Control