Analysis of accelerated ADMM methods via integral quadratic constraints

This thesis focuses on the Alternating Direction Method of Multipliers (ADMM), a widely used first-order optimization algorithm for large-scale, distributed, and non-smooth convex problems. The core idea is to study ADMM and its accelerated variants using a control-theoretic framework by formulating them as discrete-time linear systems in feedback with monotone operators. This structure allows the use of Integral Quadratic Constraints (IQCs) to analyze and certify their convergence behavior. We introduce a formulation of Accelerated ADMM (A-ADMM) as a Lur’e system, which enables a systematic IQC-based convergence analysis. By exploring different IQC representations, we demonstrate how the choice of constraint affects the tightness of the analysis. Most importantly, this approach allows us to derive an explicit bound on the worst-case linear convergence rate of A-ADMM—to our knowledge, the first such bound available for this class of accelerated methods. Building on this insight, we propose a new variant of A-ADMM that introduces a momentum-like step-size parameter into the update equations. This modification preserves the simplicity of the original ADMM structure while improving performance. The parameter is selected through a grid search guided by the IQC conditions, removing the need for manual tuning. Finally, a case study on the Lasso regression problem illustrates the effectiveness of the proposed method. The results show that our algorithm consistently outperforms standard ADMM and earlier accelerated variants in terms of both objective value and residual convergence. Overall, this work combines control-theoretic tools with algorithm design to advance the performance and understanding of accelerated splitting methods for structured convex optimization.