Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems

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.

Accepted by SIOPT

References in corpus (4)

• A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
• Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers
• Sparse Inverse Covariance Selection via Alternating Linearization Methods
• On the Global Linear Convergence of the ADMM with Multi-Block Variables

Cited by in corpus (12)

• 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
• Global hard thresholding algorithms for joint sparse image representation and denoising