Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
arXiv:1410.1390
Abstract
The alternating direction method of multipliers (ADMM) is widely used to solve large-scale linearly constrained optimization problems, convex or nonconvex, in many engineering fields. However there is a general lack of theoretical understanding of the algorithm when the objective function is nonconvex. In this paper we analyze the convergence of the ADMM for solving certain nonconvex consensus and sharing problems, and show that the classical ADMM converges to the set of stationary solutions, provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. For the sharing problems, we show that the ADMM is convergent regardless of the number of variable blocks. Our analysis does not impose any assumptions on the iterates generated by the algorithm, and is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.
arXiv commentAccepted by SIOPT
References in corpus (10)
- An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
- Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
- A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
- Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- Sparse Inverse Covariance Selection via Alternating Linearization Methods
- A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
- On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
- On the Global Linear Convergence of the ADMM with Multi-Block Variables
- Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization
Cited by in corpus (13)
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
- Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
- A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
- Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
- Convergence of multi-block Bregman ADMM for nonconvex composite problems
- A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
- Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
- Alternating Direction Method of Multipliers for A Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
- Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
- MOCCA: mirrored convex/concave optimization for nonconvex composite functions
- Alternating direction method of multipliers for penalized zero-variance discriminant analysis
- Global hard thresholding algorithms for joint sparse image representation and denoising