Paper Info
Title
Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems
Abstract
In this paper, we develop a unified framework capable of certifying 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 develop a semidefinite programming (SDP) framework 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 ...
Year
DOI
Venue
2018
10.1137/17m1136845
Siam Journal on Optimization
Field
DocType
Volume
Second-order cone programming,Lyapunov function,Mathematical optimization,Quadratically constrained quadratic program,Nonlinear programming,Quadratic programming,Conic optimization,Convex optimization,Linear matrix inequality,Mathematics
Journal
28
Issue
Citations 
PageRank 
3
7
0.50
References 
Authors
16
3
Name
Order
Citations
PageRank
Mahyar Fazlyab1336.06
Alejandro Ribeiro22817221.08
Victor M. Preciado320529.44