Convergence of multi-block Bregman ADMM for nonconvex composite problems

Abstract

The alternating direction method with multipliers (ADMM) has been one of most powerful and successful methods for solving various composite problems. The convergence of the conventional ADMM (i.e., 2-block) for convex objective functions has been justified for a long time, and its convergence for nonconvex objective functions has, however, been established very recently. The multi-block ADMM, a natural extension of ADMM, is a widely used scheme and has also been found very useful in solving various nonconvex optimization problems. It is thus expected to establish convergence theory of the multi-block ADMM under nonconvex frameworks. In this paper we present a Bregman modification of 3-block ADMM and establish its convergence for a large family of nonconvex functions. We further extend the convergence results to the $N$-block case ($N\ge 3$), which underlines the feasibility of multi-block ADMM applications in nonconvex settings. Finally, we present a simulation study and a real-world application to support the correctness of the obtained theoretical assertions.

arXiv comment25 pages, 2 figures

References in corpus (10)

• An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
• $L_{1/2}$ Regularization: Convergence of Iterative Half Thresholding Algorithm
• Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers
• Online Alternating Direction Method
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• Stable Principal Component Pursuit
• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• 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
• Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation

Cited by in corpus (13)

• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Alternating Direction Method of Multipliers for A Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
• A two-level distributed algorithm for nonconvex constrained optimization
• Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Dual Descent ALM and ADMM
• MOCCA: mirrored convex/concave optimization for nonconvex composite functions
• Bregman Parallel Direction Method of Multipliers for Distributed Optimization via Mirror Averaging
• Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications
• Nonconvex Regularization Based Sparse Recovery and Demixing with Application to Color Image Inpainting
• Zeroth-Order Stochastic Alternating Direction Method of Multipliers for Nonconvex Nonsmooth Optimization