Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
From MaRDI portal
Publication:5210517
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 . The analysis of ADMM uses a universal primal equivalence with DRS that generalizes the known duality of the algorithms.
Recommendations
- Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
- A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM
- Convergence of ADMM for optimization problems with nonseparable nonconvex objective and linear constraints
- Tight global linear convergence rate bounds for Douglas-Rachford splitting
- Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence
- Split-Douglas-Rachford algorithm for composite monotone inclusions and split-ADMM
Cites work
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
- Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators
- Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
- Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
- Convex analysis and monotone operator theory in Hilbert spaces
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms
- Forward-backward quasi-Newton methods for nonsmooth optimization problems
- Further properties of the forward-backward envelope with applications to difference-of-convex programming
- Global convergence of ADMM in nonconvex nonsmooth optimization
- Global convergence of splitting methods for nonconvex composite optimization
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 5297600 (Why is no real title available?)
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1821400 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
- Nonlinear programming
- On alternating direction methods of multipliers: a historical perspective
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the local convergence of the Douglas-Rachford algorithm
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Peaceman-Rachford splitting for a class of nonconvex optimization problems
- Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Self equivalence of the alternating direction method of multipliers
- The method of alternating relaxed projections for two nonconvex sets
Cited in
(58)- Approximate ADMM algorithms derived from Lagrangian splitting
- Envelope functions: unifications and further properties
- General splitting methods with linearization for the split feasibility problem
- An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing
- QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
- Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
- Solving blind ptychography effectively via linearized alternating direction method of multipliers
- A unified Douglas-Rachford algorithm for generalized DC programming
- Fast and stable nonconvex constrained distributed optimization: the ELLADA algorithm
- Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms
- An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
- Improving ADMMs for solving doubly nonnegative programs through dual factorization
- The alternating direction method of multipliers for finding the distance between ellipsoids
- A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
- Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- Personalized optimization with user's feedback
- An iterative method based on ADMM for solving generalized Sylvester matrix equations
- Resolvent of the parallel composition and the proximity operator of the infimal postcomposition
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
- A three-operator splitting algorithm for nonconvex sparsity regularization
- Split-Douglas-Rachford algorithm for composite monotone inclusions and split-ADMM
- Matrix inference and estimation in multi-layer models*
- A general alternating-direction implicit framework with Gaussian process regression parameter prediction for large sparse linear systems
- Two-Phase Image Segmentation by Nonconvex Nonsmooth Models with Convergent Alternating Minimization Algorithms
- Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Euclidean space
- Training recurrent neural networks by sequential least squares and the alternating direction method of multipliers
- Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming
- A parameterized three-operator splitting algorithm for non-convex minimization problems with applications
- A Bregman-style improved ADMM and its linearized version in the nonconvex setting: convergence and rate analyses
- Splitting augmented Lagrangian-type algorithms with partial quadratic approximation to solve sparse signal recovery problems
- Extrapolated plug-and-play three-operator splitting methods for nonconvex optimization with applications to image restoration
- A partial Bregman ADMM with a general relaxation factor for structured nonconvex and nonsmooth optimization
- Nonconvex multi-period mean-variance portfolio optimization
- Exterior-point optimization for sparse and low-rank optimization
- Convex predictor-nonconvex corrector optimization strategy with application to signal decomposition
- A mirror inertial forward-reflected-backward splitting: convergence analysis beyond convexity and Lipschitz smoothness
- Sparse loss-aware ternarization for neural networks
- A partially feasible Jacobi-type distributed SQO method for two-block general linearly constrained smooth optimization
- Convergence rates for an inexact linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints
- Moreau envelope and proximal-point methods under the lens of high-order regularization
- Convergence of the preconditioned proximal point method and Douglas-Rachford splitting in the absence of monotonicity
- Parameter-free structure-texture image decomposition by unrolling
- A four-operator splitting algorithm for nonconvex and nonsmooth optimization
- A stochastic preconditioned Douglas-Rachford splitting method for saddle-point problems
- Non-convex pose graph optimization in SLAM via proximal linearized Riemannian ADMM
- A distributed Douglas-Rachford splitting method for solving linear constrained multi-block weakly convex problems
- Understanding the Douglas-Rachford splitting method through the lenses of Moreau-type envelopes
- Convergent plug-and-play with proximal denoiser and unconstrained regularization parameter
- Convergence of three-block ADMM for weakly convex optimization problems
- A progressive decoupling algorithm for minimizing the difference of convex and weakly convex functions
- A Bregman-type improved ADMM method with extrapolation and its linear variant for nonconvex and nonsmooth optimization
- A DRS-based path-following algorithm for linear programming
- Forward-backward algorithms for weakly convex problems
- The incremental aggregated Douglas-Rachford splitting method for large-scale optimization problem
- The variance reduced Douglas-Rachford splitting method for large-scale optimization problems
- A variable metric Douglas-Rachford splitting method for nonconvex composite optimization
This page was built for publication: Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5210517)
