Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights

Abstract

In this paper, we establish the convergence of the proximal alternating direction method of multipliers (ADMM) and block coordinate descent (BCD) for nonseparable minimization models with quadratic coupling terms. The novel convergence results presented in this paper answer several open questions that have been the subject of considerable discussion. We firstly extend the 2-block proximal ADMM to linearly constrained convex optimization with a coupled quadratic objective function, an area where theoretical understanding is currently lacking, and prove that the sequence generated by the proximal ADMM converges in point-wise manner to a primal-dual solution pair. Moreover, we apply randomly permuted ADMM (RPADMM) to nonseparable multi-block convex optimization, and prove its expected convergence for a class of nonseparable quadratic programming problems. When the linear constraint vanishes, the 2-block proximal ADMM and RPADMM reduce to the 2-block cyclic proximal BCD method and randomly permuted BCD (RPBCD). Our study provides the first iterate convergence result for 2-block cyclic proximal BCD without assuming the boundedness of the iterates. We also theoretically establish the expected iterate convergence result concerning multi-block RPBCD for convex quadratic optimization. In addition, we demonstrate that RPBCD may have a worse convergence rate than cyclic proximal BCD for 2-block convex quadratic minimization problems. Although the results on RPADMM and RPBCD are restricted to quadratic minimization models, they provide some interesting insights: 1) random permutation makes ADMM and BCD more robust for multi-block convex minimization problems; 2) cyclic BCD may outperform RPBCD for "nice" problems, and therefore RPBCD should be applied with caution when solving general convex optimization problems.

References in corpus (9)

• On the Linear Convergence of the Alternating Direction Method of Multipliers
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints
• On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
• An Alternating Direction Method Approach to Cloud Traffic Management
• A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions

Cited by in corpus (7)

• Decentralized Charging Control of Electric Vehicles in Residential Distribution Networks
• Randomized Primal-Dual Proximal Block Coordinate Updates
• Inexact alternating direction multiplier methods for separable convex optimization
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
• Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity
• Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications