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.

25 pages, 2 figures

References in corpus (2)

• Online Alternating Direction Method
• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems

Cited by in corpus (4)

• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• 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
• Nonconvex Regularization Based Sparse Recovery and Demixing with Application to Color Image Inpainting