Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity
math.OC
Submitted: 2025-03-26
Updated: 2026-11-11
Code: https://github.com/ComputationalRobotics/admmsdp-linearconv
License: http://creativecommons.org/licenses/by/4.0/
The gist: We investigate the local linear convergence properties of the Alternating Direction Method of Multipliers (ADMM) when applied to Semidefinite Programming (SDP).
Terminology
Abstract
We investigate the local linear convergence properties of the Alternating Direction Method of Multipliers (ADMM) when applied to Semidefinite Programming (SDP). A longstanding belief suggests that ADMM is only capable of solving SDPs to moderate accuracy, primarily due to its sublinear worst-case complexity and empirical observations of slow convergence. We challenge this notion by introducing a new sufficient condition for local linear convergence: as long as the converged primal-dual optimal solutions satisfy strict complementarity, ADMM attains local linear convergence, independent of nondegeneracy conditions. Our proof is based on a direct local linearization of the ADMM operator and a refined error bound for the projection onto the positive semidefinite cone, improving previous bounds and revealing the anisotropic nature of projection residuals. Extensive numerical experiments confirm the significance of our theoretical results, demonstrating that ADMM achieves local linear convergence and computes high-accuracy solutions in a variety of SDP instances, including those cases where nondegeneracy fails. Furthermore, we identify where ADMM struggles, linking these difficulties with near violations of strict complementarity-a phenomenon that parallels recent findings in linear programming.
Sources
- On the convergence rate of the Douglas-Rachford splitting algorithm
- On the Asymptotic Superlinear Convergence of the Augmented Lagrangian Method for Semidefinite Programming with Multiple Solutions
- Building Rome with Convex Optimization
- A Low-Rank ADMM Splitting Approach for Semidefinite Programming
- Sparse Polynomial Optimization with Unbounded Sets
- Global Contact-Rich Planning with Sparsity-Rich Semidefinite Relaxations
- An Overview and Comparison of Spectral Bundle Methods for Primal and Dual Semidefinite Programs
- A Bundle-based Augmented Lagrangian Framework: Algorithm, Convergence, and Primal-dual Principles
- A feasible method for general convex low-rank SDP problems
- Linear Convergence and Error Bounds for Optimization Without Strong Convexity
- Solving Low-Rank Semidefinite Programs via Manifold Optimization
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise