2017/05/10 by Mahyar Fazlyab, Fazlyab, Mahyar, Alejandro Ribeiro +5 · 3 citations
Engineering · Mathematics · Computer Science · #Sparse and Compressive Sensing Techniques #Advanced Optimization Algorithms Research #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.1705.03615
In this paper, we develop a unified framework able to certify both\nexponential and subexponential convergence rates for a wide range of iterative\nfirst-order optimization algorithms. To this end, we construct a family of\nparameter-dependent nonquadratic Lyapunov functions that can generate\nconvergence rates in addition to proving asymptotic convergence. Using Integral\nQuadratic Constraints (IQCs) from robust control theory, we propose a Linear\nMatrix Inequality (LMI) to guide the search for the parameters of the Lyapunov\nfunction in order to establish a rate bound. Based on this result, we formulate\na Semidefinite Programming (SDP) whose solution yields the best convergence\nrate that can be certified by the class of Lyapunov functions under\nconsideration. We illustrate the utility of our results by analyzing the\ngradient method, proximal algorithms and their accelerated variants for\n(strongly) convex problems. We also develop the continuous-time counterpart,\nwhereby we analyze the gradient flow and the continuous-time limit of\nNesterov's accelerated method.\n