On the local convergence of the Douglas-Rachford algorithm

DOI10.1007/S00013-014-0652-2MaRDI QIDQ2510692zbMATH OpenOpenAlexFDO

Authors Heinz H. Bauschke, Dominikus Noll

Publication date 1 August 2014

Published in Archiv der Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6188

zbMATH Keywords

convergencestabilitydiscrete dynamical systemfixed-pointnonconvex feasibility problem

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Iterative procedures involving nonlinear operators (47J25) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Abstract: We discuss the Douglas-Rachford algorithm to solve the feasibility problem for two closed sets $A,B$ in $mathbb{R}^d$. We prove its local convergence to a fixed point when $A,B$ are finite unions of convex sets. We also show that for more general nonconvex sets the scheme may fail to converge and start to cycle, and may then even fail to solve the feasibility problem.

Recommendations

• The Douglas-Rachford algorithm in the absence of convexity
• A cyclic Douglas-Rachford iteration scheme
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• The Douglas-Rachford algorithm for a hyperplane and a doubleton
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems

Cites work

• scientific article; zbMATH DE number 3310599 (Why is no real title available?)
• Convergence of sequential and asynchronous nonlinear paracontractions
• Convex analysis and monotone operator theory in Hilbert spaces
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• On cluster points of alternating projections
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
• Recent results on Douglas-Rachford methods.
• Restricted normal cones and the method of alternating projections: theory
• Searching with iterated maps
• Splitting Algorithms for the Sum of Two Nonlinear Operators

Cited in

(42)

• A new projection method for finding the closest point in the intersection of convex sets
• Method of alternating projections for the general absolute value equation
• A remark on the convergence of the Douglas-Rachford iteration in a non-convex setting
• Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems
• On Slater's condition and finite convergence of the Douglas-Rachford algorithm for solving convex feasibility problems in Euclidean spaces
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization
• Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
• Union averaged operators with applications to proximal algorithms for MIN-convex functions
• Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
• A convergent relaxation of the Douglas-Rachford algorithm
• Algorithms based on unions of nonexpansive maps
• Global convergence of splitting methods for nonconvex composite optimization
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• General splitting methods with linearization for the split feasibility problem
• Convergence analysis of Douglas-Rachford splitting method for ``strongly + weakly convex programming
• The Douglas-Rachford algorithm for the case of the sphere and the line
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Circumcentering the Douglas-Rachford method
• Solving graph coloring problems with the Douglas-Rachford algorithm
• Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
• The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces
• scientific article; zbMATH DE number 7195209 (Why is no real title available?)
• Local convergence analysis for the REQP algorithm using conjugate basis matrices
• Recent results on Douglas-Rachford methods.
• The Douglas-Rachford algorithm in the absence of convexity
• Linear convergence of the Douglas-Rachford method for two closed sets
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging
• The cyclic Douglas-Rachford method for inconsistent feasibility problems
• The Douglas-Rachford algorithm in the affine-convex case
• An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
• The Douglas-Rachford algorithm for a hyperplane and a doubleton
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• A cyclic Douglas-Rachford iteration scheme
• Alternating projections with applications to Gerchberg-Saxton error reduction
• New Douglas-Rachford algorithmic structures and their convergence analyses
• The Douglas-Rachford algorithm converges only weakly
• On the global optimization properties of finite-difference local descent algorithms
• Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration
• Norm convergence of realistic projection and reflection methods

Describes a project that uses

Uses Software

• GeoGebra

This page was built for publication: On the local convergence of the Douglas-Rachford algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2510692)