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

2023/09/20 by Van Scoy, Bryan, Simpson-Porco, John W., Lessard, Laurent · 1 citation
#FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.2309.11365

Abstract

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.

Cited by

• Automated algorithm design for convex optimization problems with linear equality constraints

Related

• Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees
• Analysis of Optimization Algorithms via Integral Quadratic Constraints:\n Nonstrongly Convex Problems
• Automated tight Lyapunov analysis for first-order methods
• Accelerated primal-dual methods for linearly constrained convex optimization problems
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization