Automated Lyapunov Analysis of Primal-Dual Optimization Algorithms: An Interpolation Approach

Autor:	Van Scoy, Bryan, Simpson-Porco, John W., Lessard, Laurent
Rok vydání:	2023
Předmět:	Mathematics - Optimization and Control Electrical Engineering and Systems Science - Systems and Control
Druh dokumentu:	Working Paper
Popis:	Primal-dual algorithms are frequently used for iteratively solving large-scale convex optimization problems. The analysis of such algorithms is usually done on a case-by-case basis, and the resulting guaranteed rates of convergence can be conservative. Here we consider a class of first-order algorithms for linearly constrained convex optimization problems, and provide a linear matrix inequality (LMI) analysis framework for certifying worst-case exponential convergence rates. Our approach builds on recent results for interpolation of convex functions and linear operators, and our LMI directly constructs a Lyapunov function certifying the guaranteed convergence rate. By comparing to rates established in the literature, we show that our approach can certify significantly faster convergence for this family of algorithms. Comment: 6 pages, 2 figures, to appear at IEEE Conference on Decision and Control 2023
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2309.11365 Zobrazit plný text záznamu View this record from Arxiv