May 31, 2018 | Yu Wang · Wotao Yin · Jinshan Zeng†
This paper analyzes the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function subject to coupled linear equality constraints. The authors develop a convergence guarantee that covers a wide range of nonconvex functions, including piecewise linear functions, $\ell_q$ quasi-norms, Schatten-$q$ quasi-norms ($0 < q < 1$), minimax concave penalties (MCP), and smoothly clipped absolute deviations (SCAD). The analysis also allows for nonconvex constraints such as compact manifolds and linear complementarity constraints. The paper provides sufficient conditions for ADMM to converge on monotropic programs with three or more blocks, extending the theory to a broader class of nonconvex functions and sets.
The authors demonstrate, for the first time, that several ADMM algorithms applied to nonconvex models in statistical learning, optimization on manifolds, and matrix decomposition are guaranteed to converge. They show that ADMM can be a better choice than the augmented Lagrangian method (ALM) for some nonconvex nonsmooth problems because ADMM is easier to implement and more likely to converge.
The paper includes a detailed analysis of the convergence properties of ADMM, including the introduction of new techniques such as an induction technique for nonconvex, nonsmooth cases, restricted prox-regularity, and handling more general linear mappings. The main results are presented in Theorems 1 and 2, which establish the global convergence of ADMM under certain assumptions on the objective function and matrices. The paper also discusses the tightness of these assumptions and provides examples of nonconvex models where ADMM converges but ALM diverges.This paper analyzes the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function subject to coupled linear equality constraints. The authors develop a convergence guarantee that covers a wide range of nonconvex functions, including piecewise linear functions, $\ell_q$ quasi-norms, Schatten-$q$ quasi-norms ($0 < q < 1$), minimax concave penalties (MCP), and smoothly clipped absolute deviations (SCAD). The analysis also allows for nonconvex constraints such as compact manifolds and linear complementarity constraints. The paper provides sufficient conditions for ADMM to converge on monotropic programs with three or more blocks, extending the theory to a broader class of nonconvex functions and sets.
The authors demonstrate, for the first time, that several ADMM algorithms applied to nonconvex models in statistical learning, optimization on manifolds, and matrix decomposition are guaranteed to converge. They show that ADMM can be a better choice than the augmented Lagrangian method (ALM) for some nonconvex nonsmooth problems because ADMM is easier to implement and more likely to converge.
The paper includes a detailed analysis of the convergence properties of ADMM, including the introduction of new techniques such as an induction technique for nonconvex, nonsmooth cases, restricted prox-regularity, and handling more general linear mappings. The main results are presented in Theorems 1 and 2, which establish the global convergence of ADMM under certain assumptions on the objective function and matrices. The paper also discusses the tightness of these assumptions and provides examples of nonconvex models where ADMM converges but ALM diverges.