Linear Convergence of the Douglas-Rachford Method for Two Closed Sets

Introduction

Let $A$ and $B$ be two closed subsets of $X$. The basic feasibility problem is to

This problem has long been considered very important in the natural sciences and engineering. The reference is often considered a classic survey of methods for solving (2). Among them, the Douglas–Rachford method has attracted increasing attention, mainly because of its good performance.

To describe this method, we first recall that the distance function to a closed subset $A$ of $X$ is $d_{A}(x):=\inf_{a\in A}\|x-a\|$; the projector $P_{A}$ and reflector $R_{A}$ are the set-valued mappings defined respectively by

When $P_{A}(x)=\{a\}$ is a singleton, we simply write $a=P_{A}x$.

The Douglas-Rachford operator $T:X\rightrightarrows X$ for two sets $A$ and $B$ is then defined by

Clearly when $A$ and $B$ are convex, $T$ is single-valued.

If the DR sequence converges to a fixed point ${\overline{x}}$, then there exists an element of $P_{A}{\overline{x}}$ that is a solution of (2). Thus, DR can be used to solve (2).

Recently, Hesse and Luke have obtained an interesting result about the local $R$-linear convergence for DR of two sets in nonconvex settings. In particular, the authors proved that: “if $A$ is an affine subspace and $B$ is a superregular set (see Definition 2.6), and the system $\{A,B\}$ is strongly regular (see (10)), then the DR sequence converges locally to the intersection $A\cap B$ with $R$-linear rate” (see [15, Theorem 3.18]).

We will complement the above statement with several new results:

If $A$ and $B$ are two superregular sets, and the system $\{A,B\}$ is strongly regular (see (10)), then the DR sequence converges locally with $R$-linear rate to the intersection $A\cap B$ (see Theorem 4.3).

If $A$ and $B$ are two superregular sets, and the system $\{A,B\}$ is affine-hull regular (see (11)), then the DR sequence converges locally with $R$-linear rate to a fixed point ${\overline{x}}$ of $T$ and that $P_{A}{\overline{x}}\equiv P_{B}{\overline{x}}\in A\cap B$, which solves the feasibility problem (2) (see Theorem 4.7).

If $A$ and $B$ are two convex sets such that $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$, then for every starting point, the DR sequence converges with $R$-linear rate to a fixed point of $T$ and that $P_{A}{\overline{x}}\equiv P_{B}{\overline{x}}\in A\cap B$, which solves the feasibility problem (2) (see Theorem 4.14).

(R1) is more general than [15, Theorem 3.18] (see Example 4.6).

(R2) is more general than (R1) (see Example 4.9).

In (R1), the limit point ${\overline{x}}$ of the DR sequence is indeed a solution of the feasibility problem (2).

In (R2) and (R3), although the limit point ${\overline{x}}$ may not be a solution of (2), the “shadow” $P_{A}{\overline{x}}\equiv P_{B}{\overline{x}}\in A\cap B$ is actually a solution. Notice that, we implicitly assume that both projectors $P_{A}$ and $P_{B}$ are computable. Therefore, as long as the limit point ${\overline{x}}$ is obtained, the shadows $P_{A}{\overline{x}}$ and $P_{B}{\overline{x}}$ are computable.

In (R2) and (R3), the limit point ${\overline{x}}$ is a fixed point of the DR operator and surprisingly, $P_{A}{\overline{x}}\equiv P_{B}{\overline{x}}$ is a singleton. However, for a general DR fixed point ${\overline{x}}$, $P_{A}{\overline{x}}$ does not necessarily coincide with $P_{B}{\overline{x}}$ (see Example 5.3) and that neither of them is necessarily singleton.

Although the theory of DR for two convex sets is well-known, the rate of convergence for this case has only been observed partially before: the case of two affine subspaces , the case of one convex set and one affine subspace . We would like to mention that (R3) is the first to address the $R$-linear convergence of DR for two closed convex sets. This result is also re-established in [10, Section 4] within the context of averaged nonexpansive operators.

The paper is organized as follows. Section 2 contains preliminary results. In Section 3, we present an affine reduction property of DR operator. Section 4 then presents the main results of the paper. Finally, concluding remarks are given in Section 5.

Preliminary results

In this section, we recall some preliminary concepts and results.

Recall that the proximal normal cone (see, e.g., [22, Example 6.16] or [21, eq. (2.80)]) to a set $A$ at a point $x$ is defined by $N^{\rm prox}_{A}(x):=\operatorname{cone}(P^{-1}_{A}x-x)$. The Mordukhovich (or limiting) normal cone (see, e.g., [21, Theorem 1.6]) is given by

Let $L$ be an affine subspace containing $A$, then the (limiting) normal cone of $A$ restricted to $L$ is given by

Clearly, $N^{L}_{A}(x)\subseteq N_{A}(x)$. Indeed, the concept of restricted normal cone was developed in in more general settings.

Let $A$ and $B$ be two subsets of $X$ and let $w\in A\cap B$. We say that the system $\{A,B\}$ is strongly regular at $w$ if

Let $L:=\operatorname{aff}(A\cup B)$, we say that the system $\{A,B\}$ is affine-hull regular at $w$ if

In order to quantify the rate of convergence, we need the following quantity for two closed cones $N_{1}$ and $N_{2}$ of $X$ (cf., the CQ-number )

which is related to strong/affine-hull regularity as showed below (a simple proof is included since it uses only the definitions).

Let $A$ and $B$ be two closed sets and let $w\in A\cap B$. Then the following hold

$\{A,B\}$ is strongly regular at $w$ if and only if $\overline{\theta}(N_{A}(w),N_{B}(w))<1$.

$\{A,B\}$ is affine-hull regular at $w$ if and only if \overline{\theta}\big{(}N^{L}_{A}(w),N^{L}_{B}(w)\big{)}<1, where $L:=\operatorname{aff}(A\cup B)$.

(ii): We may assume $w=0$, thus $L=\operatorname{aff}(A\cup B)=\operatorname{span}(A\cup B)$ is a subspace. Then restrict the consideration to the subspace $L$. $\hfill\quad\square$

Indeed, strong regularity (or more general, uniform regularity) can be characterized by different quantities . Thorough discussions can be found in and the references therein.

Finally, we finish this section by recalling linear regularity property of set systems , which plays an important role in convex and variational analysis. Its connection to strong regularity is also stated below.

We say that the system of sets $\{A,B\}$ is $\mu$-linear regular on $S$ if

We also say that $\mu$ is a linear regularity modulus.

2 Regularity of sets and quasi firm nonexpansiveness

It is well-known that if $A$ and $B$ are convex, then their DR operator $T$ is firmly nonexpansive (see, e.g., [6, Proposition 4.21]). In particular, the following holds

If $A$ and $B$ are not convex, however, (15) is not necessarily true.

Nevertheless, we will show that an analogous estimation for $T$ holds locally under certain regularity assumptions on the sets $A$ and $B$ (see Proposition 2.10). First, we recall some technical definitions.

Let $A$ be a closed subset of $X$. We say that $A$ is $(\varepsilon,\delta)$-regular at $w$ if $\varepsilon\geq 0$, $\delta>0$ and

We say that $A$ is superregular at $w$ if for every $\varepsilon>0$, there exists $\delta>0$ such that $A$ is $(\varepsilon,\delta)$-regular at $w$.

Superregularity was first introduced in [19, Definition 4.3]. It is somewhat between Clarke regularity and amenability or prox-regularity. This concept is further generalized in [8, Definition 8.1] and [15, Definition 2.9]. Importantly, all convex sets are superregular. More discussion and examples can be found in .

A mapping $\Phi:X\rightrightarrows X$ is said to be $(\Omega,\gamma)$-quasi firmly nonexpansive on $U$ if for all $x\in U$, $x_{+}\in\Phi x$, and ${\overline{x}}\in P_{\Omega}x$, we have

One would notice that when $\gamma=1$, quasi firm expansiveness is a variant of the quasi nonexpansiveness in [6, Definition 4.1]. In addition, the latter is a restriction of Fejér monotonicity [6, Chapter 5]. Besides, the $\gamma$-quasi firm expansiveness is a simplification of the $(\Omega,\varepsilon)$-firm nonexpansiveness [15, Definition 2.3(ii)]: a mapping $\Phi:X\rightrightarrows X$ is said to be $(\Omega,\varepsilon)$-firmly nonexpansive on $U$ if

Although the following argument is simplified from , details are included for the readers’ convenience.

Let $A$ and $B$ be two closed sets. Let $\delta>0$, $\varepsilon\in[0,\tfrac{1}{4})$. Assume $A$ is $(\varepsilon,2\delta)$-regular at $w\in A\cap B$. Then the following hold:

(ii): Applying Fact 2.8(ii) to $A$ being $(\varepsilon,2\delta)$-regular at $w$, we have

For every $b\in P_{B}R_{A}x$, let $u\in R_{A}x$ such that $b\in P_{B}u$. So

Let $A$ and $B$ be two closed sets and let $T$ be the DR operator (5). Let $\delta>0$, $\varepsilon_{1},\varepsilon_{2}\in[0,\tfrac{1}{4})$. Assume further that $A$ and $B$ are $(\varepsilon_{1},2\delta)$- and $(\varepsilon_{2},3\delta)$-regular at $w\in A\cap B$, respectively. Define also

Next, using the parallelogram law, we obtain

(ii): Take any ${\overline{x}}\in P_{\Omega}x$, we have

Finally, we include an $R$-linear convergence result of Fejér monotonicity type with an elementary proof for completeness.

Let $\Phi:X\rightrightarrows X$ be an operator, let $\Omega$ be a closed subset of $X$ and $w\in\Omega$. Assume that there are $\delta>0$ and $\kappa\in[0,1)$ such that

It is easy to check that (32) holds for $n=0$. Now, suppose (32) holds for $0,\ldots,n-1$, we will show it also holds for $n$. Indeed,

Affine reduction

The main result of this section is Theorem 3.3, in which we prove an interesting property of DR for two closed sets. First, we recall some properties of affine subspaces. Recall that two affine subspaces $L_{1}$ and $L_{2}$ are parallel if there exists $z\in X$ such that $L_{1}=z+L_{2}$. The proof of the following lemma is elementary, thus, omitted.

Let $L$ be an affine subspace of $X$ and let $\Omega\subseteq L$ be closed. Then the following hold

For every $x\in X$ and $z\in R_{\Omega}x$, we have: $x-P_{L}x=P_{L}z-z$.

Let $A$ and $B$ be two closed sets with $L:=\operatorname{aff}(A\cup B)$, and let $T$ be the DR operator (5). Let $x_{0}\in X$ and $x_{1}\in Tx_{0}$. Define also $y_{0}=P_{L}x_{0}$ and $y_{1}=P_{L}x_{1}$. Then

Proof. Since $x_{1}\in Tx_{0}$, we find $z\in R_{A}x_{0}$ and $w\in R_{B}z$ such that $x_{1}=\tfrac{1}{2}(x_{0}+w)$. Employing Lemma 3.1(i), we have

Now since $P_{L}$ is an affine operator (see Lemma 3.1(iii)), we have

To prove the second part, we employ Lemma 3.1(ii) twice to obtain

So, x_{1}-y_{1}=\frac{1}{2}(x_{0}+w)-P_{L}\big{(}\frac{1}{2}(x_{0}+w)\big{)}=\frac{1}{2}(x_{0}-P_{L}x_{0})+\frac{1}{2}(w-P_{L}w)=x_{0}-y_{0}. $\hfill\quad\square$

Proof. (i)&(ii): apply Lemma 3.2 inductively.

This also implies $y_{n}-{\overline{y}}=x_{n}-{\overline{x}}$. Thus, the rates of convergence are identical.

Next, since $P_{L}(\cdot)$ is continuous, we have ${\overline{y}}=P_{L}{\overline{x}}$. On the other hand, ${\overline{y}}\in A\subseteq L$, so ${\overline{y}}=P_{A}{\overline{x}}$ is a singleton. Similarly, ${\overline{y}}=P_{B}{\overline{x}}$. Thus, we obtain (41). $\hfill\quad\square$

Main results

This section contains the main results of the paper which are divided into three parts.

In this part, we establish the $R$-linear convergence of DR for two sets $A$ and $B$ locally around $w\in A\cap B$ under two assumptions

$\{A,B\}$ is strongly regular at $w$ (see (10)); and

$A$ and $B$ are superregular at $w$ (see Definition 2.6).

The result of this section (Theorem 4.3 below) is an improvement of [15, Theorem 3.18] where the authors proved the local $R$-linear convergence assuming one set is superregular and the other is an affine subspace.

Let $A$ and $B$ be two closed sets. Assume that $\{A,B\}$ is strongly regular at $w\in A\cap B$, or equivalently (see Lemma 2.3),

Then for every $\theta\in(\overline{\theta},1)$, there exist $\delta>0$ such that

Proof. Suppose on the contrary that there exist sequences $a_{n}\in A$, $b_{n}\in B$, $a_{n}\to w$, $b_{n}\to w$, $u_{n}\in N^{\rm prox}_{A}(a_{n})$, $v_{n}\in N^{\rm prox}_{B}$ such that

By dividing by $\|u_{n}\|.\|v_{n}\|$, we can assume that $u_{n}$, $v_{n}$ are unit vectors. So let $u$ and $v$ be accumulation (unit) vectors of $u_{n}$ and $v_{n}$ respectively, we have $u\in N_{A}(w)$, $v\in N_{B}(w)$, and $\left\langle{u},{v}\right\rangle\leq-\theta$. So by the definition of $\overline{\theta}$,

which is a contradiction. $\hfill\quad\square$

The following lemma provides the main ingredient.

Let $A$ and $B$ be two closed sets, and let $T$ be the DR operator (5). Assume further that $A$ is superregular at $w$, and that $\{A,B\}$ is strongly regular at $w$, or equivalently,

where $a\in P_{A}x$ is such that $x_{+}\in P_{B}(2a-x)+x-a$.

Proof. Take an arbitrary $\overline{\theta}<\theta<1$, $\varepsilon\in[0,\tfrac{1}{4})$ and define $\Omega:=A\cap B$. By the superregularity of $A$, Lemma 4.1, Fact 2.5, we find $\delta>0$ and $\mu\geq 1$ such that

$A$ is $(\varepsilon,2\delta)$-regular at $w$;

On the other hand, triangle and Cauchy-Schwarz inequalities imply

which yields (48) with $\lambda:=\tfrac{\sqrt{1-\theta}}{\mu}\in[0,1)$. $\hfill\quad\square$

Let $A$ and $B$ be two closed sets, and let $T$ be the DR operator (5). Assume further that $A$ and $B$ are superregular at $w\in A\cap B$, and that $\{A,B\}$ is strongly regular at $w$, or equivalently,

Take $\varepsilon_{1},\varepsilon_{2}\in[0,\tfrac{1}{4})$ small and shrink $\delta$ if necessary, we assume that $A$ is $(\varepsilon_{1},2\delta)$-regular at $w$ and that $B$ is $(\varepsilon_{2},3\delta)$-regular at $w$.

Note that $\kappa^{2}=\tfrac{1+(1+2\varepsilon_{1})^{2}(1+2\varepsilon_{2})^{2}}{2}-\lambda^{2}\in[0,1)$ if $\varepsilon_{1},\varepsilon_{2}$ was chosen small enough.

This assures assumption (30) in Proposition 2.11 holds. Thus, the conclusion now follows from Proposition 2.11. $\hfill\quad\square$

From the proofs of Proposition 2.11, Lemma 4.2, and Theorem 4.3, we derive a formula for the $R$-linear rate $\kappa$ as follows:

Suppose that there are $\delta,\varepsilon_{1},\varepsilon_{2}>0$, $\theta\in[0,1)$, and $\mu\geq 1$ such that

$A$ is $(\varepsilon_{1},2\delta)$-regular at $w$;

$B$ is $(\varepsilon_{2},3\delta)$-regular at $w$;

$\kappa^{2}:=\tfrac{1+(1+2\varepsilon_{1})^{2}(1+2\varepsilon_{2})^{2}}{2}-\tfrac{1-\theta}{5\mu^{2}}\in[0,1)$.

Theorem 4.3 is more general than [15, Theorem 3.18]. However, in the case that $A$ is an affine subspace, we obtain a smaller bound for the $R$-linear rate. Details are given in the following result (notice that the rate $\kappa$ in Theorem 4.5(iv) is smaller than $\kappa$ in Remark 4.4(v)).

([15, Theorem 3.18]) Let $A$ be an affine subspace, let $B$ be a closed set, and let $T$ be the DR operator (5). Suppose that there are $\delta,\varepsilon,>0$, $\theta\in[0,1)$, and $\mu\geq 1$ such that

$B$ is $(\varepsilon_{2},3\delta)$-regular at $w$;

$\kappa^{2}:=\tfrac{1+(1+2\varepsilon_{1})^{2}(1+2\varepsilon_{2})^{2}}{2}-\tfrac{1-\theta}{\mu^{2}}\in[0,1)$.

Notice that since $A$ is an affine subspace and $\Omega\subset A$, we have $d_{\Omega}(2a-x)=d_{\Omega}(x)$. So (63) implies

The rest of the proof is analogous to that of Theorem 4.3. $\hfill\quad\square$

2 DR under affine-hull regularity

In this part, we establish the $R$-linear convergence of DR for two sets $A$ and $B$ locally around $w\in A\cap B$ under two assumptions

$\{A,B\}$ is affine-hull regular at $w$ (see (10)); and

$\{A,B\}$ is superregular at $w$ (see (11)).

Using Remark 3.4 and Theorem 3.3, our strategy is to rely on the behavior of DR on the affine-hull $L=\operatorname{aff}(A\cup B)$.

Let $A$ and $B$ be two closed sets with $L:=\operatorname{aff}(A\cup B)$, and let $T$ be the DR operator (5). Assume further that $A$ and $B$ are superregular at $w\in A\cap B$, and that $\{A,B\}$ is affine-hull regular at $w$, i.e.,

i.e., $P_{A}{\overline{x}}\equiv P_{B}{\overline{x}}$ solves the feasibility problem (2).

Finally, this last relation implies ${\overline{x}}\in\operatorname{Fix}T$. $\hfill\quad\square$

Theorem 4.7 proves that, the region of convergence is actually larger than a ball around $w$. In fact, the region of convergence is the cylinder generated by some ball around $w$ and $(L-w)^{\bot}$, the orthogonal complement of $L-w$.

3 DR for two convex sets

We now study the case that both sets $A$ and $B$ are convex. Because of convexity, we claim that all of the assumptions required for $R$-linear convergence will be fulfilled using only the standard qualification condition of convex analysis

([8, Theorem 3.13]) Let $A$ and $B$ be two closed convex sets. The following are equivalent:

$\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$.

$\{A,B\}$ is affine-hull regular at $w$ for all $w\in A\cap B$.

$\{A,B\}$ is affine-hull regular at $w$ for some $w\in A\cap B$.

([2, Proposition 4.6.1]) Let $A$ and $B$ be closed convex subsets of $X$ such that

Then for every bounded set $S$, there exists $\mu\geq 1$ such that $\{A,B\}$ is $\mu$-linear regular on $S$.

Let $A$ and $B$ be two closed convex sets such that $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$. Then

Proof. Denote $L:=\operatorname{aff}(A\cup B)$. “$\supseteq$”: clear. “$\subseteq$”: Let $x\in L\cap\operatorname{Fix}T$. Since $P_{A}$, $P_{B}$ are single-valued, let $a:=P_{A}x$, $b:=P_{B}(2a-x)$. So we have

Since $x$ is a fixed point of $T$, $x=Tx=x+b-a$. So $a=b\in A\cap B$. Thus, it follows from (71) that $x-a\in N^{L}_{A}(a)$ and $a-x\in N^{L}_{B}(a)$. Employing Fact 4.10, we have $x-a\in N^{L}_{A}(a)\cap(-N^{L}_{B}(a))=\{0\}$. Hence, $x=a=b\in A\cap B$. $\hfill\quad\square$

We are then ready to present the main result of this section.

Let $A$ and $B$ be two closed convex sets with $L:=\operatorname{aff}(A\cup B)$, and let $T$ be the DR operator (5). Assume also that

Remarks and examples

One can check that $\{A,B\}$ is strongly regular at every point in the intersection $A\cap B$.

Notice that the results in are not applicable because neither $A$ nor $B$ is an affine subspace. Theorem 4.14, on the other hand, does apply and yield convergence for the DR with even global $R$-linear rate.

We now use Remark 4.4 to compute the rate: first, notice that $\{A,B\}$ is (globally) linearly regular with modulus $\mu=\tfrac{1}{\sin\tfrac{\pi}{8}}=\tfrac{2}{\sqrt{2-\sqrt{2}}}$.Next, we set $\varepsilon_{1}=\varepsilon_{2}=0$, $\delta=+\infty$, and $\theta=\tfrac{\sqrt{2}}{2}$. Then, the rate is

Thus, $\kappa=\sqrt{\tfrac{17+2\sqrt{2}}{20}}$. Despite the conjecture that the actual rate could be smaller, our obtained rate $\kappa$ is the only rate known so far!

Acknowledgment

The author was partially supported by an internal grant of University of Massachusetts Lowell. This research was initiated during the author’s stay at University of British Columbia (Kelowna, Canada). The author is grateful to Heinz Bauschke and Xianfu Wang (UBC Kelowna, Canada) for their support. The author also thanks the editors and the referees for their constructive comments.

References