Global Behavior of the Douglas-Rachford Method for a Nonconvex Feasibility Problem

Abstract

In recent times the Douglas-Rachford algorithm has been observed empirically to solve a variety of nonconvex feasibility problems including those of a combinatorial nature. For many of these problems current theory is not sufficient to explain this observed success and is mainly concerned with questions of local convergence. In this paper we analyze global behavior of the method for finding a point in the intersection of a half-space and a potentially non-convex set which is assumed to satisfy a well-quasi-ordering property or a property weaker than compactness. In particular, the special case in which the second set is finite is covered by our framework and provides a prototypical setting for combinatorial optimization problems.

References in corpus (1)

• Divide and concur: A general approach to constraint satisfaction

Cited by in corpus (9)

• Circumcentering the Douglas--Rachford method
• Adaptive Douglas-Rachford splitting algorithm for the sum of two operators
• A new projection method for finding the closest point in the intersection of convex sets
• 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
• Douglas--Rachford Splitting and ADMM for Pathological Convex Optimization
• A feasibility approach for constructing combinatorial designs of circulant type
• The Douglas--Rachford algorithm for a hyperplane and a doubleton
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration