Douglas-Rachford splitting and ADMM for nonconvex optimization: new convergence results and accelerated versions
Authors:
Preprint
Abstract
Although originally designed and analyzed for convex problems, the alternating direction method of multipliers (ADMM) and its close relatives, Douglas-Rachford Splitting (DRS) and Peaceman-Rachford Splitting (PRS), have been observed to perform remarkably well when applied to certain classes of structured nonconvex optimization problems. However, partial global convergence results in the nonconvex setting have only recently emerged. The goal of this work is two-fold: first, we show how the Douglas-Rachford Envelope (DRE), introduced by the authors in 2014, can be employed to devise global convergence guarantees for ADMM, DRS, PRS applied to nonconvex problems under less restrictive conditions, larger prox-stepsizes and over-relaxation parameters than what was previously known. Other than greatly simplify the theory, exploiting properties of the DRE we propose new globally convergent algorithmic schemes that greatly accelerates convergence. For instance, the new schemes can accommodate for quasi-Newton directions such as (L-) BFGS or extend extrapolation steps \`a-la-Nesterov to fully nonconvex problems.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Global Convergence of ADMM in Nonconvex Nonsmooth OptimizationJournal of Scientific Computing, 2018
- Forward-Backward Envelope for the Sum of Two Nonconvex Functions: Further Properties and Nonmonotone Linesearch AlgorithmsSIAM Journal on Optimization, 2018
- Peaceman–Rachford splitting for a class of nonconvex optimization problemsComputational Optimization and Applications, 2017
- Forward–backward quasi-Newton methods for nonsmooth optimization problemsComputational Optimization and Applications, 2017
- Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex ProblemsSIAM Journal on Optimization, 2016
- Proximal alternating linearized minimization for nonconvex and nonsmooth problemsMathematical Programming, 2013