Linear convergence of the generalized Douglas–Rachford algorithm for feasibility problems

In this paper, we study the generalized Douglas–Rachford algorithm and its cyclic variants which include many projection-type methods such as the classical Douglas–Rachford algorithm and the alternating projection algorithm. Specifically, we establish several local linear convergence results for the algorithm in solving feasibility problems with finitely many closed possibly nonconvex sets under different assumptions. Our findings not only relax some regularity conditions but also improve linear convergence rates in the literature. In the presence of convexity, the linear convergence is global.     

On the local convergence of the Douglas–Rachford algorithm

We discuss the Douglas–Rachford algorithm to solve the feasibility problem for two closed sets A,B in \({\mathbb{R}^d}\) . We prove its local convergence to a fixed point when A,B are finite unions of convex sets. We also show that for more general nonconvex sets the scheme may fail to converge and start to cycle, and may then even fail to solve the feasibility problem.     

A simplified proof of weak convergence in Douglas–Rachford method

Douglas–Rachford method is a splitting algorithm for finding a zero of the sum of two maximal monotone operators. Weak convergence in this method to a solution of the underlying monotone inclusion problem in the general case remained an open problem for 30 years and was proved by the author 7 years ago. That proof was cluttered with technicalities because we considered the inexact version with summable errors. In this short communication we present a streamlined proof of this result.     

Global convergence of a non-convex Douglas–Rachford iteration

We establish a region of convergence for the proto-typical non-convex Douglas–Rachford iteration which finds a point on the intersection of a line and a circle. Previous work on the non-convex iteration Borwein and Sims (Fixed-point algorithms for inverse problems in science and engineering, pp. 93–109, 2011) was only able to establish local convergence, and was ineffective in that no explicit region of convergence could be given.     

Tight global linear convergence rate bounds for Douglas–Rachford splitting

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.     

A Douglas–Rachford splitting method for solving equilibrium problems

We propose a splitting method for solving equilibrium problems involving the sum of two bifunctions satisfying standard conditions. We prove that this problem is equivalent to find a zero of the sum of two appropriate maximally monotone operators under a suitable qualification condition. Our algorithm is a consequence of the Douglas–Rachford splitting applied to this auxiliary monotone inclusion. Connections between monotone inclusions and equilibrium problems are studied.     

On the Douglas–Rachford algorithm

Mathematical Programming - The Douglas–Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the...     

A note on the Douglas–Rachford splitting method for optimization problems involving hypoconvex functions

Recently, the convergence of the Douglas–Rachford splitting method (DRSM) was established for minimizing the sum of a nonsmooth strongly convex function and a nonsmooth hypoconvex function under the assumption that the strong convexity constant \(\beta \) is larger than the hypoconvexity constant \(\omega \). Such an assumption, implying the strong convexity of the objective function, precludes many interesting applications. In this paper, we prove the convergence of the DRSM for the case \(\beta =\omega \), under relatively mild assumptions compared with some existing work in the literature.     

On the minimal displacement vector of the Douglas–Rachford operator

The Douglas–Rachford algorithm can be represented as the fixed point iteration of a firmly nonexpansive operator. When the operator has no fixed points, the algorithm’s iterates diverge, but the difference between consecutive iterates converges to the so-called minimal displacement vector, which can be used to certify infeasibility of an optimization problem. In this paper, we establish new properties of the minimal displacement vector, which allow us to generalize some existing results.     

On the order of the operators in the Douglas–Rachford algorithm

The Douglas–Rachford algorithm is a popular method for finding zeros of sums of monotone operators. By its definition, the Douglas–Rachford operator is not symmetric with respect to the order of the two operators. In this paper we provide a systematic study of the two possible Douglas–Rachford operators. We show that the reflectors of the underlying operators act as bijections between the fixed points sets of the two Douglas–Rachford operators. Some elegant formulae arise under additional assumptions. Various examples illustrate our results.     

A unified Douglas–Rachford algorithm for generalized DC programming

Journal of Global Optimization - We consider a class of generalized DC (difference-of-convex functions) programming, which refers to the problem of minimizing the sum of two convex (possibly...     

A Cyclic Douglas–Rachford Iteration Scheme

In this paper, we present two Douglas–Rachford inspired iteration schemes which can be applied directly to N-set convex feasibility problems in Hilbert space. Our main results are weak convergence of the methods to a point whose nearest point projections onto each of the N sets coincide. For affine subspaces, convergence is in norm. Initial results from numerical experiments, comparing our methods to the classical (product-space) Douglas–Rachford scheme, are promising.     

A Remark on the Convergence of the Douglas–Rachford Iteration in a Non-convex Setting

Using a known construction of a Lyapunov function, it is shown that the Douglas–Rachford iteration with respect to a sphere and a line in a Hilbert space converges to the intersection point in a fashion which is stronger than uniform convergence on compact sets.