Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results

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. In this paper we show how the Douglas-Rachford envelope (DRE), introduced in 2014, can be employed to unify and considerably simplify the theory for devising global convergence guarantees for ADMM, DRS and PRS applied to nonconvex problems under less restrictive conditions, larger prox-stepsizes and over-relaxation parameters than previously known. In fact, our bounds are tight whenever the over-relaxation parameter ranges in $(0,2]$. The analysis of ADMM uses a universal primal equivalence with DRS that generalizes the known duality of the algorithms.

References in corpus (4)

• Global convergence of splitting methods for nonconvex composite optimization
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms

Cited by in corpus (12)

• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• QPALM: A Proximal Augmented Lagrangian Method for Nonconvex Quadratic Programs
• Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type linesearch algorithms
• Riemannian Smoothing Gradient Type Algorithms]{Riemannian Smoothing Gradient Type Algorithms for Nonsmooth Optimization Problem on Compact Riemannian Submanifold Embedded in Euclidean Space
• Powered Descent Guidance via First-Order Optimization with Expansive Projection
• Asynchronous distributed collision avoidance with intention consensus for inland autonomous ships
• The Alternating Direction Method of Multipliers for Finding the Distance between Ellipsoids
• Distributed nonconvex optimization for control of water networks with time-coupling constraints
• A new envelope function for nonsmooth DC optimization
• Decentralized Real-Time Iterations for Distributed NMPC
• A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness
• Distributed MPC for autonomous ships on inland waterways with collaborative collision avoidance