A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm

Abstract

The Douglas-Rachford projection algorithm is an iterative method used to find a point in the intersection of closed constraint sets. The algorithm has been experimentally observed to solve various nonconvex feasibility problems which current theory cannot sufficiently explain. In this paper, we prove convergence of the Douglas-Rachford algorithm in a potentially nonconvex setting. Our analysis relies on the existence of a Lyapunov-type functional whose convexity properties are not tantamount to convexity of the original constraint sets. Moreover, we provide various nonconvex examples in which our framework proves global convergence of the algorithm.

31 pages, 4 figures

References in corpus (2)

• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces

Cited by in corpus (5)

• 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 for a hyperplane and a doubleton
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration
• A proximal subgradient algorithm with extrapolation for structured nonconvex nonsmooth problems