2018/03/29 by Mahyar Fazlyab, Manfred Morari, Fazlyab, Mahyar +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Algebraic Geometry (math.AG) #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1803.10928
openalex publication_date 2018/03/29 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
In this paper, we propose a framework based on sum-of-squares programming to\ndesign iterative first-order optimization algorithms for smooth and strongly\nconvex problems. Our starting point is to develop a polynomial matrix\ninequality as a sufficient condition for exponential convergence of the\nalgorithm. The entries of this matrix are polynomial functions of the unknown\nparameters (exponential decay rate, stepsize, momentum coefficient, etc.). We\nthen formulate a polynomial optimization, in which the objective is to optimize\nthe exponential decay rate over the parameters of the algorithm. Finally, we\nuse sum-of-squares programming as a tractable relaxation of the proposed\npolynomial optimization problem. We illustrate the utility of the proposed\nframework by designing a first-order algorithm that shares the same structure\nas Nesterov's accelerated gradient method.\n