Global Convergence of ADMM in Nonconvex Nonsmooth Optimization

By Yu Wang, Wotao Yin, Jinshan Zeng. 2015

1,382 citations recorded by the source corpus.

In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, ϕ(x0,…,xp,y)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi (x_0,\ldots ,x_p,y)$$\end{document}, subject to coupled linear equality constraints. Our ADMM updates each of the primal variables x0,…,xp,y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_0,\ldots ,x_p,y$$\end{document}, followed by updating the dual variable. We separate the variable y from xi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_i$$\end{document}’s as it has a special role in our analysis. The developed convergence guarantee covers a variety of nonconvex functions such as piecewise linear functions, ℓq\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _q$$\end{document} quasi-norm, Schatten-q quasi-norm (0<q<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0<q<1$$\end{document}), minimax concave penalty (MCP), and smoothly clipped absolute deviation penalty. It also allows nonconvex constraints such as compact manifolds (e.g., spherical, Stiefel, and Grassman manifolds) and linear complementarity constraints. Also, the x0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_0$$\end{document}-block can be almost any lower semi-continuous function. By applying our analysis, we show, for the first time, that several ADMM algorithms applied to solve nonconvex models in statistical learning, optimization on manifold, and matrix decomposition are guaranteed to converge. Our results provide sufficient conditions for ADMM to converge on (convex or nonconvex) monotropic programs with three or more blocks, as they are special cases of our model. ADMM has been regarded as a variant to the augmented Lagrangian method (ALM). We present a simple example to illustrate how ADMM converges but ALM diverges with bounded penalty parameter β\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}. Indicated by this example and other analysis in this paper, ADMM might be a better choice than ALM for some nonconvex nonsmooth problems, because ADMM is not only easier to implement, it is also more likely to converge for the concerned scenarios.

Subfields: Computational Mechanics, Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Learning Privately over Distributed Features: An ADMM Sharing Approach (2019, background): “Note that Assumption 2.1 is adopted in Sarwate and Chaudhuri (2013) and Wang et al. (2019).”
ADMM Based Privacy-Preserving Decentralized Optimization (2017, background): “Secondly, the convergence of ADMM has been established for non-convex and non-smooth objective function [37].”
An introduction to continuous optimization for imaging (2016, methodology): “However, the method should also converge if this is not satisfied in a bounded set, which is the case for q-norms with q < 1 (Wang et al. 2015): in this case we should select one solution of the proximity operator, which is now possibly multivalued (yet still a monotone operator).”
ADMM-CSNet: A Deep Learning Approach for Image Compressive Sensing (2020, background): “Although ADMM is efficient and favorable with convergence guarantee [28], [30], it commonly takes hundreds of iterations to converge and it is also non-trivial to set the hyper-parameters of ADMM”
Extremely Low Bit Neural Network: Squeeze the Last Bit Out with ADMM (2017, background): “Although ADMM has been originally developed for convex problems, there has been much recent interest in applying it to the nonconvex nonsmooth problems, with the analysis of convergence available in some cases [34].”
Denoising Prior Driven Deep Neural Network for Image Restoration (2018, positive): “For fðxÞ :1⁄4 argminuf2 kx uk2 þ dMðxÞ þ b2 kv uk2g, It is discussed in [58] that (10) holds and thus (9) holds in the asymptotic sense.”
Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “We will use inequality (4) to show the sufficient descent of a Lyapunov function L, which was used in [33] and extended in [34].”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, background): “, [3], [4], [10], [42], [44]), we are not aware of previous analyses including projection-free methods for convex sets and smooth non convex objectives.”
One Network to Solve Them All — Solving Linear Inverse Problems Using Deep Projection Models (2017, methodology): “Based on the theorems for the convergence of non-convex ADMM [47], we provide the following theorem to the proposed ADMM framework.”
Structure-Revealing Low-Light Image Enhancement Via Robust Retinex Model (2018, background): “of ADM for non-convex optimization problems [30], [31].”
Fast and Robust Iterative Closest Point (2020, methodology): “In addition, the convergence of IRLS and ADMM for non-convex (cid:96) p -norm minimization requires strong assumptions about the problem such as the Kurdyka-Łojasiewicz property [60], [61], whereas our MM solver is guaranteed to converge.”