On the Duality Gap Convergence of ADMM Methods

2015/08/15 by Da Tang, Tong Zhang, Tang, Da +1
Computer Science · Engineering · Mathematics · #Advanced Numerical Methods in Computational Mathematics #FOS: Mathematics #Matrix Theory and Algorithms #Numerical methods in inverse problems #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1508.03702

openalex publication_date 2015/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper provides a duality gap convergence analysis for the standard ADMM as well as a linearized version of ADMM. It is shown that under appropriate conditions, both methods achieve linear convergence. However, the standard ADMM achieves a faster accelerated convergence rate than that of the linearized ADMM. A simple numerical example is used to illustrate the difference in convergence behavior.

Citations

• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Related

• On the (linear) convergence of Generalized Newton Inexact ADMM
• Linear Convergence and Metric Selection for Douglas-Rachford Splitting\n and ADMM
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis
• Accelerated ADMM: Automated Parameter Tuning and Improved Linear Convergence