Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers

Abstract

In this paper, we consider solving multiple-block separable convex minimization problems using alternating direction method of multipliers (ADMM). Motivated by the fact that the existing convergence theory for ADMM is mostly limited to the two-block case, we analyze in this paper, both theoretically and numerically, a new strategy that first transforms a multi-block problem into an equivalent two-block problem (either in the primal domain or in the dual domain) and then solves it using the standard two-block ADMM. In particular, we derive convergence results for this two-block ADMM approach to solve multi-block separable convex minimization problems, including an improved O(1/ε) iteration complexity result. Moreover, we compare the numerical efficiency of this approach with the standard multi-block ADMM on several separable convex minimization problems which include basis pursuit, robust principal component analysis and latent variable Gaussian graphical model selection. The numerical results show that the multiple-block ADMM, although lacks theoretical convergence guarantees, typically outperforms two-block ADMMs.

References in corpus (2)

• Latent variable graphical model selection via convex optimization
• Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection

Cited by in corpus (19)

• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Non-convex Robust PCA
• 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
• Parallel Multi-Block ADMM with o(1/k) Convergence
• Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
• Parallel Direction Method of Multipliers
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• On the Sublinear Convergence Rate of Multi-Block ADMM
• On the Global Linear Convergence of the ADMM with Multi-Block Variables
• An Alternating Direction Method Approach to Cloud Traffic Management
• Policy Synthesis for Factored MDPs with Graph Temporal Logic Specifications
• Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Inexact indefinite proximal ADMMs for 2-block separable convex programs and applications to 4-block DNNSDPs
• A corrected semi-proximal ADMM for multi-block convex optimization and its application to DNN-SDPs
• Estimation of Graphical Models through Structured Norm Minimization
• Convergence of the Augmented Decomposition Algorithm
• Distributed and Asynchronous Algorithms for N-block Convex Optimization with Coupling Constraints