On the Finite Convergence of the Douglas--Rachford Algorithm for Solving (Not Necessarily Convex) Feasibility Problems in Euclidean Spaces

DOI10.1137/16M1071079zbMath1365.90194arXiv1604.04657MaRDI QIDQ5737718

Heinz H. Bauschke, Minh N. Dao

Publication date: 30 May 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

global convergencepolyhedronprojectorfinite convergencefeasibility problemDouglas-Rachford algorithmepigraphhalfspacereflectoraveraged alternating reflections

Mathematics Subject Classification ID

Convex programming (90C25) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Rate of convergence, degree of approximation (41A25) Decomposition methods (49M27)

Related Items

Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems ⋮ Finitely convergent deterministic and stochastic iterative methods for solving convex feasibility problems ⋮ A remark on the convergence of the Douglas-Rachford iteration in a non-convex setting ⋮ The Douglas-Rachford algorithm for convex and nonconvex feasibility problems ⋮ Union averaged operators with applications to proximal algorithms for MIN-convex functions ⋮ The Douglas-Rachford algorithm for a hyperplane and a doubleton ⋮ A Lyapunov function construction for a non-convex Douglas-Rachford iteration ⋮ A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting ⋮ Finitely convergent iterative methods with overrelaxations revisited ⋮ A feasibility approach for constructing combinatorial designs of circulant type ⋮ Constraint reduction reformulations for projection algorithms with applications to wavelet construction ⋮ Linear Convergence of Projection Algorithms ⋮ SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD ⋮ Adaptive Douglas--Rachford Splitting Algorithm for the Sum of Two Operators ⋮ Solving Nonconvex Feasibility Problem on a Sphere and a Closed Ball by Douglas–Rachford Algorithm ⋮ Convergence of an Inertial Shadow Douglas-Rachford Splitting Algorithm for Monotone Inclusions

Cites Work

• Unnamed Item
• On the order of the operators in the Douglas-Rachford algorithm
• Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
• On Slater's condition and finite convergence of the Douglas-Rachford algorithm for solving convex feasibility problems in Euclidean spaces
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Linear and strong convergence of algorithms involving averaged nonexpansive operators
• On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints
• Iterative methods for fixed point problems in Hilbert spaces
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Hilbertian convex feasibility problem: Convergence of projection methods
• Reflection-projection method for convex feasibility problems with an obtuse cone
• The Douglas-Rachford algorithm for the case of the sphere and the line
• Tight global linear convergence rate bounds for Douglas-Rachford splitting
• The Douglas-Rachford algorithm in the affine-convex case
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
• Global convergence of a non-convex Douglas-Rachford iteration
• On the local convergence of the Douglas-Rachford algorithm
• Fundamentals of Computerized Tomography
• Linear convergence of the Douglas–Rachford method for two closed sets
• Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study
• The Douglas–Rachford Algorithm in the Absence of Convexity
• On Weak Convergence of the Douglas–Rachford Method
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Activity Identification and Local Linear Convergence of Douglas–Rachford/ADMM under Partial Smoothness
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• On Projection Algorithms for Solving Convex Feasibility Problems
• Convergence Rate Analysis of Several Splitting Schemes
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• Convex analysis and monotone operator theory in Hilbert spaces