An Interconnected Systems Approach to Convergence Analysis of Discrete-Time Primal-Dual Algorithms
Spencer Kelly, John W. Simpson-Porco · 2024
We study the geometric convergence rate of discrete-time primal-dual algorithms for solving strongly-convex equality-constrained optimization problems. Our approach separates the primal-dual algorithm into an interconnection of two exponentially stable systems, and a composite Lyapunov approach is used to establish stability of the interconnection and provide new bounds on the geometric rate of convergence. Analogous convergence results are developed for two variations of the primal-dual algorithm: an extrapolated version which accelerates convergence, and an inner-loop version which interpolates between the vanilla primal-dual method and dual ascent. The obtained bounds are compared and contrasted with existing bounds from the literature.