The Douglas--Rachford algorithm for a hyperplane and a doubleton

Abstract

The Douglas--Rachford algorithm is a popular algorithm for solving both convex and nonconvex feasibility problems. While its behaviour is settled in the convex inconsistent case, the general nonconvex inconsistent case is far from being fully understood. In this paper, we focus on the most simple nonconvex inconsistent case: when one set is a hyperplane and the other a doubleton (i.e., a two-point set). We present a characterization of cycling in this case which --- somewhat surprisingly --- depends on whether the ratio of the distance of the points to the hyperplane is rational or not. Furthermore, we provide closed-form expressions as well as several concrete examples which illustrate the dynamical richness of this algorithm.

References in corpus (10)

• Divide and concur: A general approach to constraint satisfaction
• Global convergence of a non-convex Douglas-Rachford iteration
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• Global Behavior of the Douglas-Rachford Method for a Nonconvex Feasibility Problem
• On Slater's condition and finite convergence of the Douglas-Rachford algorithm
• 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
• Dynamics of the Douglas-Rachford Method for Ellipses and p-Spheres
• Linear Convergence of Projection Algorithms