An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems

2025/05/27 by Peng Liu, Liang Chen, Liu, Peng +3
Computer Science · Engineering · #Blind Source Separation Techniques #FOS: Mathematics #Machine Learning and ELM #Optical Systems and Laser Technology #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2505.20991

openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

As an extension of the alternating direction method of multipliers (ADMM), the semi-proximal ADMM (sPADMM) has been widely used in various fields due to its flexibility and robustness. In this paper, we first show that the two-block sPADMM algorithm can achieve an O(1/√(K)) non-ergodic convergence rate. Then we propose an accelerated sPADMM (AsPADMM) algorithm by introducing extrapolation techniques and incrementing penalty parameters. The proposed AsPADMM algorithm is proven to converge globally to an optimal solution with a non-ergodic convergence rate of O(1/K). Furthermore, the AsPADMM can be extended and combined with the symmetric Gauss-Seidel decomposition to achieve an accelerated ADMM for multi-block problems. Finally, we apply the proposed AsPADMM to solving the multi-block subproblems in difference-of-convex algorithms for robust low-rank tensor completion problems and mixed sparse optimization problems. The numerical results suggest that the acceleration techniques bring about a notable improvement in the convergence speed.

Citations

• HPR-LP: An implementation of an HPR method for solving linear programming
• Accelerating preconditioned ADMM via degenerate proximal point mappings
• An Accelerated Proximal Alternating Direction Method of Multipliers for Optimal Decentralized Control of Uncertain Systems
• Lagrangian-based methods in convex optimization: prediction-correction frameworks with non-ergodic convergence rates
• Moreau Envelope Augmented Lagrangian Method for Nonconvex Optimization with Linear Constraints
• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
• An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for Linear Programming
• A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization
• Equivalent Lipschitz surrogates for zero-norm and rank optimization problems
• Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm
• On the Equivalence of Inexact Proximal ALM and ADMM for a Class of Convex Composite Programming
• Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis
• A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
• Accelerated Alternating Direction Method of Multipliers: an Optimal O(1/K) Nonergodic Analysis
• Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
• Computing B-Stationary Points of Nonsmooth DC Programs
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions
• Convergence rate analysis of several splitting schemes
• An Accelerated Linearized Alternating Direction Method of Multipliers
• Parallel Multi-Block ADMM with o(1/k) Convergence
• Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
• Monotone Operators and the Proximal Point Algorithm
• Multiplier and gradient methods

Related

• Fast Proximal Linearized Alternating Direction Method of Multiplier with Parallel Splitting
• Parallel Multi-Block ADMM with o(1/k) Convergence
• Accelerated Symmetric ADMM and Its Applications in Signal Processing
• Accelerated Alternating Direction Method of Multipliers: an Optimal O(1/K) Nonergodic Analysis
• An inexact version of the symmetric proximal ADMM for solving separable convex optimization