Global Convergence of ADMM in Nonconvex Nonsmooth Optimization

Abstract

In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, $\varphi (x_0,\dots ,x_p,y)$, subject to coupled linear equality constraints. Our ADMM updates each of the primal variables $x_0,\dots ,x_p,y$, followed by updating the dual variable. We separate the variable $y$ from $x_i$'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, ${\ell }_q$ quasi-norm, Schatten-$q$ quasi-norm ($0<q<1$), minimax concave penalty (MCP), and smoothly clipped absolute deviation (SCAD) penalty. It also allows nonconvex constraints such as compact manifolds (e.g., spherical, Stiefel, and Grassman manifolds) and linear complementarity constraints. Also, the $x_0$-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 $\beta$. Indicated by this example and other analysis in this paper, ADMM might be a better choice than ALM for some nonconvex \emph{nonsmooth} problems, because ADMM is not only easier to implement, it is also more likely to converge for the concerned scenarios.

33 pages, 1 figure, Accepted by Journal of Scientific Computing

References in corpus (3)

• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Asynchronous Distributed Optimization using a Randomized Alternating Direction Method of Multipliers

Cited by in corpus (48)

• Distributed Nash Equilibrium Seeking under Partial-Decision Information via the Alternating Direction Method of Multipliers
• Hyperspectral Image Unmixing with Endmember Bundles and Group Sparsity Inducing Mixed Norms
• Improved Sparse Low-Rank Matrix Estimation
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Optimized Signal Distortion for PAPR Reduction of OFDM Signals with IFFT/FFT Complexity via ADMM Approaches
• Structured SUMCOR Multiview Canonical Correlation Analysis for Large-Scale Data
• Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• A General Truncated Regularization Framework for Contrast-Preserving Variational Signal and Image Restoration: Motivation and Implementation
• Convergent Block Coordinate Descent for Training Tikhonov Regularized Deep Neural Networks
• An Empirical Study of ADMM for Nonconvex Problems
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• How is Distributed ADMM Affected by Network Topology?
• Asynchronous ADMM for Distributed Non-Convex Optimization in Power Systems
• Randomized Primal-Dual Proximal Block Coordinate Updates
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• A Modularized Efficient Framework for Non-Markov Time Series Estimation
• Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
• Deterministic Approximate Methods for Maximum Consensus Robust Fitting
• Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs
• Nonisometric Surface Registration via Conformal Laplace-Beltrami Basis Pursuit
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectives
• Local Region Sparse Learning for Image-on-Scalar Regression
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Practical Algorithms for Learning Near-Isometric Linear Embeddings
• ADMM Based Privacy-preserving Decentralized Optimization
• A Local Analysis of Block Coordinate Descent for Gaussian Phase Retrieval
• The Application of Multi-block ADMM on Isotonic Regression Problems
• Fast L1-L2 minimization via a proximal operator
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Efficient Numerical Optimization For Susceptibility Artifact Correction Of EPI-MRI
• Simultaneous Detection of Multiple Appliances from Smart-meter Measurements via Multi-Label Consistent Deep Dictionary Learning and Deep Transform Learning
• Online Convolutional Sparse Coding with Sample-Dependent Dictionary
• Nonconvex Sparse Spectral Clustering by Alternating Direction Method of Multipliers and Its Convergence Analysis
• An Efficient ADMM-Based Algorithm to Nonconvex Penalized Support Vector Machines
• Learning Low-Complexity Autoregressive Models via Proximal Alternating Minimization
• $L^0$-regularized Variational Methods for Sparse Phase Retrieval
• On Convergence of Heuristics Based on Douglas-Rachford Splitting and ADMM to Minimize Convex Functions over Nonconvex Sets
• Nonlocal Myriad Filters for Cauchy Noise Removal
• Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local Minimizers
• Multi-instance Domain Adaptation for Vaccine Adverse Event Detection
• Gauging Variational Inference
• A Nonlinear Bregman Primal-Dual Framework for Optimizing Nonconvex Infimal Convolutions
• Continuous Relaxation of MAP Inference: A Nonconvex Perspective
• A Nonconvex Proximal Splitting Algorithm under Moreau-Yosida Regularization
• Estimation Rates for Sparse Linear Cyclic Causal Models