On Slater's condition and finite convergence of the Douglas-Rachford algorithm

Abstract

The Douglas-Rachford algorithm is a classical and very successful method for solving optimization and feasibility problems. In this paper, we provide novel conditions sufficient for finite convergence in the context of convex feasibility problems. Our analysis builds upon, and considerably extends, pioneering work by Spingarn. Specifically, we obtain finite convergence in the presence of Slater's condition in the affine-polyhedral and in a hyperplanar-epigraphical case. Various examples illustrate our results. Numerical experiments demonstrate the competitiveness of the Douglas-Rachford algorithm for solving linear equations with a positivity constraint when compared to the method of alternating projections and the method of reflection-projection.

References in corpus (1)

• The Douglas-Rachford algorithm in the affine-convex case

Cited by in corpus (12)

• Adaptive Douglas-Rachford splitting algorithm for the sum of two operators
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• The Douglas-Rachford algorithm in the affine-convex case
• A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• Linear Convergence of Projection Algorithms
• The Douglas--Rachford algorithm for a hyperplane and a doubleton
• On the order of the operators in the Douglas-Rachford algorithm
• Local Convergence Properties of Douglas--Rachford and ADMM
• Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition
• Projection Algorithms for Finite Sum Constrained Optimization
• Convergence analysis of variants of the averaged alternating modified reflections method