Linear and strong convergence of algorithms involving averaged nonexpansive operators

Overview

Throughout this paper, $X$ is a real Hilbert space with inner product $\left\langle{\cdot},{\cdot}\right\rangle$ and induced norm $\|\cdot\|$. The convex feasibility problem asks to find a point in the intersection of convex sets. This is an important problem in mathematics and engineering; see, e.g., , , , , , , , , and the references therein.

Oftentimes, the convex sets are given as fixed point sets of projections or (more generally) averaged nonexpansive operators. In this case, weak convergence to a solution is guaranteed but the question arises under which circumstances can we guarantee strong or even linear convergence. The situation is quite clear for projection algorithms; see, e.g., and also .

The aim of this paper is to provide verifiable sufficient conditions for strong and linear convergence of algorithms based on iterating convex combinations of averaged nonexpansive operators.

Our results can be nontechnically summarized as follows: If each operator is well behaved and the fixed point sets relate well to each other, then the algorithm converges strongly or linearly.

Specifically, we obtain the following main results on iterations of averaged nonexpansive mappings:

If each operator is boundedly linearly regular and the family of corresponding fixed point sets is boundedly linearly regular, then quasicyclic averaged algorithms converge linearly (Theorem 6.1).

If each operator is boundedly regular and the family of corresponding fixed point sets is boundedly regular, then cyclic algorithms converge strongly (Theorem 7.11).

If each operator is boundedly regular and the family of corresponding fixed point sets is innately boundedly regular, then random sequential algorithms converge strongly (Theorem 7.14).

We also focus in particular on algorithms featuring the Douglas–Rachford splitting operator and obtain new convergence results on the Borwein–Tam method and the cyclically anchored Douglas–Rachford algorithm.

The remainder of the paper is organized as follows. In Sections 2 and 3, we discuss (boundedly) linearly regular and averaged nonexpansive operators. The bounded linear regularity of the Douglas–Rachford operator in the transversal case is obtained in Section 4. In Section 5, we recall the key notions of Fejér monotonticity and regularity of collections of sets. Our main convergence result on quasicyclic algorithms is presented in Section 6. In Section 7, we turn to strong convergence results for cyclic and random algorithms. Applications and numerical results are provided in Section 8. Notation in this paper is quite standard and follows mostly .

Operators that are (boundedly) linearly regular

Our linear convergence results depend crucially on the concepts of (bounded) linear regularity which we introduce now.

Let $T\colon X\to X$ be such that $\operatorname{Fix}T\neq\varnothing$. We say that:

$T$ is linearly regular with constant $\kappa\geq 0$ if

note that in general $\kappa$ depends on $\rho$, which we sometimes indicate by writing $\kappa=\kappa(\rho)$.

Let $C$ be a nonempty closed convex subset of $X$ and let $\lambda\in\left]0,2\right]$. Then $T=(1-\lambda)\operatorname{Id}+\lambda P_{C}$ is linearly regular with constant $\lambda^{-1}$.

Proof. Indeed, $\operatorname{Fix}T=C$ and $(\forall x\in X)$ $d_{C}(x)=\|x-P_{C}x\|=\lambda^{-1}\|x-Tx\|$. $\hfill\quad\blacksquare$

The following example shows that an operator may be boundedly linearly regular yet not linearly regular. This illustrates that the converse of the implication (3) fails.

Then $T$ is boundedly linearly regular with $\kappa(\rho)=\max\{\rho,1\}$; however, $T$ is not linearly regular.

Proof. Let $x\in X$. Since $\operatorname{Fix}T=\{0\}$, we deduce

If $x\notin\operatorname{Fix}T$, then $d_{\operatorname{Fix}T}(x)/|x-Tx|=\max\{|x|,1\}$ and the result follows. $\hfill\quad\blacksquare$

Let $T\colon X\to X$ be linear and nonexpansive with $\operatorname{ran}(\operatorname{Id}-T)$ closed. Then $T$ is linearly regular.

Proof. Set $A=\operatorname{Id}-T$. Then $A$ is maximally monotone by [8, Example 20.26], and $(\operatorname{Fix}T)^{\perp}=(\ker A)^{\perp}=\overline{\operatorname{ran}}\,A^{*}=\overline{\operatorname{ran}}\,A=\overline{\operatorname{ran}}\,(\operatorname{Id}-T)=\operatorname{ran}(\operatorname{Id}-T)$ using [8, Proposition 20.17]. By the Closed Graph Theorem (see, e.g., [17, Theorem 8.18]), there exists $\beta>0$ such that

Now let $x\in X$ and split $x$ into $x=y+z$, where $y=P_{\ker A}x=P_{\operatorname{Fix}T}x$ and $z=P_{(\ker A)^{\perp}}x=P_{\operatorname{ran}A}x=P_{\operatorname{ran}(\operatorname{Id}-T)}x$. Then

and the result follows. $\hfill\quad\blacksquare$

Let $U$ and $V$ be closed subspaces of $X$ such that $U+V$ is closed, and set $T=P_{V}P_{U}+P_{V^{\perp}}P_{U^{\perp}}$. Then $\operatorname{Fix}T=(U\cap V)+(U^{\perp}\cap V^{\perp})$, and $\operatorname{ran}(\operatorname{Id}-T)=(U+V)\cap(U^{\perp}+V^{\perp})$ is closed; consequently, $T$ is linearly regular.

Proof. The formula for $\operatorname{Fix}T$ is in, e.g., . On the one hand, it is well known (see, e.g., [8, Corollary 15.35]) that $U^{\perp}+V^{\perp}$ is closed as well. On the other hand, [11, Corollary 2.14] implies that $\operatorname{ran}(\operatorname{Id}-T)=(U+V)\cap(U^{\perp}+V^{\perp})$. Altogether, $\operatorname{ran}(\operatorname{Id}-T)$ is closed. Finally, apply Theorem 2.4. $\hfill\quad\blacksquare$

Proof. Let $x\in X$. A direct computation (or [5, Section 5]) yields

i.e., $T$ shrinks the vector by $\cos(\theta)\in\left[0,1\right[$ and rotates it by $\theta$. Hence $\operatorname{Fix}T=\{0\}$ and

On the other hand, using $1-\cos^{2}(\theta)=\sin^{2}(\theta)$, we obtain

Altogether, $d_{\operatorname{Fix}T}(x)=\|x\|=(1/\sin(\theta))\sin(\theta)\|x\|=(1/\sin(\theta))\|x-Tx\|$. $\hfill\quad\blacksquare$

We conclude this section by comparing our notion of bounded linear regularity to metric regularity of set-valued operators.

Suppose that $T$ is firmly nonexpansive and thus the resolvent of a maximally monotone operator $A$. Suppose that $\bar{x}\in X$ is such that $0\in A\bar{x}$, i.e., $\bar{x}\in\operatorname{Fix}T$. Then metric subregularity of $A$ at $\bar{x}$ means that there exists $\delta>0$ and $\gamma>0$ such that $x\in B(\bar{x};\delta)$ $\Rightarrow$ $d_{A^{-1}0}(x)\leq\gamma d_{Ax}(0)$. In terms of $T$, this is expressed as $x\in\operatorname{ball}(\bar{x};\delta)$ $\Rightarrow$ $d_{\operatorname{Fix}T}(x)\leq\gamma\inf\|x-T^{-1}x\|$. If $x=Ty\in\operatorname{ball}(\bar{x};\delta)$, then the Minty parametrization yields

moreover, $d_{\operatorname{Fix}T}(y)\leq(1+\gamma)\|y-Ty\|$. This is related to bounded linear regularity of $T$. The interested reader is referred to for further information on metric subregularity; see also and .

Averaged nonexpansive operators

We work mostly within the class of averaged nonexpansive mappings which have proven to be a good compromise between generality and usability.

The mapping $T\colon X\to X$ is averaged nonexpansive if there exists $\lambda\in\left[0,1\right[$ and $N\colon X\to X$ nonexpansive such that $T=(1-\lambda)\operatorname{Id}+\lambda N$.

The class of averaged nonexpansive operators is closed under compositions and convex combinations, and it includes all firmly nonexpansive mappings; see, e.g., for further information.

Let $T\colon X\to X$ be $\beta$-Lipschitz with $\beta\in\left]0,1\right[$. Then $T$ is averaged.

Proof. Let $\varepsilon\in\left]0,(1-\beta)/2\right[\subset\left]0,1\right[$. Then $(\beta+\varepsilon)/(1-\varepsilon)\in\left]0,1\right[$. Now $(1-\varepsilon)^{-1}T$ is $(1-\varepsilon)^{-1}\beta$-Lipschitz and $-\varepsilon(1-\varepsilon)^{-1}\operatorname{Id}$ is $\varepsilon(1-\varepsilon)^{-1}$-Lipschitz, hence

is nonexpansive. Set $\lambda=1-\varepsilon\in\left]0,1\right[$. Then $(1-\lambda)\operatorname{Id}+\lambda N=\varepsilon\operatorname{Id}+(1-\varepsilon)N=T$ and $T$ is therefore averaged. $\hfill\quad\blacksquare$

(See, e.g., [8, Proposition 4.25(iii)].) Let $T\colon X\to X$ be averaged nonexpansive. Then there exists $\sigma>0$ such that

The following two properties are crucial to our subsequent analysis.

Let $T\colon X\to X$ be averaged nonexpansive. Then there exists $\sigma=\sigma(T)>0$ such that for every nonempty subset $C$ of $\operatorname{Fix}T$, we have

Let $I$ be a finite ordered index set, let $(T_{i})_{i\in I}$ be family of averaged nonexpansive operators with $\sigma_{i}=\sigma(T_{i})$, and let $(\omega_{i})_{i\in I}$ be in $$such that$\sum_{i\in I}\omega_{i}=1$. Set$I_{+}=\big{\{}{i\in I}~{}\big{|}~{}{\omega_{i}>0}\big{\}}$, and set$\sigma_{+}=\min_{i\in I_{+}}\sigma_{i}$. Let$x\in X$, and set$y=\sum_{i\in I}\omega_{i}T_{i}x$ Then

Let $T\colon X\to X$ be averaged nonexpansive such that

Then $T$ is boundedly linearly regular; moreover, $T$ is linearly regular if $\theta$ does not depend on $\rho$.

Proof. We abbreviate $\sigma(T)$ by $\sigma$. Let $\rho>0$ and let $x\in\operatorname{ball}(0;\rho)$. Obtain $\theta$ and $y\in\operatorname{Fix}T$ as in (19). Then

Hence $(1-\theta)^{-1}\|x-Tx\|^{2}\geq d_{\operatorname{Fix}T}^{2}(x)$. $\hfill\quad\blacksquare$

The following example can be viewed as a generalization of Example 2.6.

Suppose that $S\colon X\to X$ is linear such that $S^{*}=-S$ and $(\forall x\in X)$ $\|Sx\|=\|x\|$. Let $\alpha\in\left]0,\pi/2\right]$, let $\beta\in\left]-1,1\right[$, and set $T=\beta(\cos(\alpha)\operatorname{Id}+\sin(\alpha)S)$. Then $T$ is linearly regular.

Proof. Set $R=\cos(\alpha)\operatorname{Id}+\sin(\alpha)S$. Then $T=\beta R$ and $(\forall x\in X)$ $\|Rx\|=\|Sx\|=\|x\|$; hence $\|T\|=|\beta|<1$. By Example 3.2, $T$ is averaged. Furthermore, $(\forall x\in X)$ $\left\langle{x},{Tx}\right\rangle=\beta\cos(\alpha)\|x\|^{2}=\cos(\alpha)\|x\|\|\beta Rx\|=\cos(\alpha)\|x\|\|Tx\|$. The linear regularity of $T$ thus follows from Lemma 3.6. $\hfill\quad\blacksquare$

We conclude this section with some key inequalities.

Let $T\colon X\to X$ be averaged firmly nonexpansive and boundedly linearly regular, and let $\rho>0$. Suppose that $C$ is a nonempty subset of $\operatorname{Fix}T$. Then there exist $\alpha\in\left[0,1\right[$, $\beta\in\left]0,1\right]$, and $\gamma>0$ such that for every $x\in\operatorname{ball}(0;\rho)$, we have

If $T$ is linearly regular, then these constants do not depend on $\rho$.

Proof. Let us obtain the constants $\kappa=\kappa(\rho)\geq 0$ from bounded linear regularity and $\sigma=\sigma(T)$ from the averaged nonexpansiveness. Abbreviate $Z=\operatorname{Fix}T$, and let $x\in\operatorname{ball}(0;\rho)$. Then $d^{2}_{Z}(Tx)\leq d^{2}_{Z}(x)\leq\kappa^{2}\|x-Tx\|^{2}\leq\sigma^{-1}\kappa^{2}(d^{2}_{Z}(x)-d^{2}_{Z}(Tx))$ by Corollary 3.4. Hence (21) holds with

Note that $\alpha$ depends only on $T$ when $T$ is in addition linearly regular. Next, we set

which again depend only on $T$ in the presence of linear regularity. Then, by (21), $d_{Z}(x)-d_{Z}(Tx)\geq(1-\alpha)d_{Z}(x)$. Since $d_{Z}$ is nonexpansive, we deduce

i.e., (22). Finally, using Corollary 3.4, we conclude that

i.e., (23) holds. $\hfill\quad\blacksquare$

The Douglas–Rachford Operator for Tranversal Sets

In this section, $X$ is finite-dimensional, $A$ and $B$ are nonempty closed convex subsets of $X$ with $A\cap B\neq\varnothing$. Moreover, $L=\operatorname{aff}(A\cup B)$, $Y=L-L={\operatorname{span}}\,(B-A)$, denote the affine span of $A\cup B$ and the corresponding parallel space, respectively. We also set

i.e., $T$ is the Douglas–Rachford operator for $(A,B)$. Note that $T(L)\subseteq L$. Our next two results are essentially contained in , where even nonconvex settings were considered. In our present convex setting, the proofs become much less technical.

\operatorname{Fix}T=(A\cap B)+N_{A-B}(0)=(A\cap B)+\big{(}Y\cap N_{A-B}(0)\big{)}+Y^{\perp}.

$L\cap\operatorname{Fix}T=(A\cap B)+(Y\cap N_{A-B}(0))$.

If $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$, then $\operatorname{Fix}T=(A\cap B)+Y^{\perp}$ and $L\cap\operatorname{Fix}T=A\cap B$.

If $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$, then $P_{\operatorname{Fix}T}=\operatorname{Id}-P_{L}+P_{A\cap B}P_{L}$.

If $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$, then $d_{\operatorname{Fix}T}=d_{A\cap B}\circ P_{L}$.

Suppose $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$, and let $c\in A\cap B$. Then there exists $\delta>0$ and $\theta<1$ such that

Proof. Since $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$, we deduce from [10, Lemma 3.1 and Theorem 3.13] that

Set $u_{n}=(x_{n}-P_{A}x_{n})/\|x_{n}-P_{A}x_{n}\|\in Y\cap N_{A}(P_{A}x_{n})$ and $v_{n}=(P_{B}R_{A}x_{n}-R_{A}x_{n})/\|P_{B}R_{A}x_{n}-R_{A}x_{n}\|\in Y\cap-N_{B}(P_{B}R_{A}x_{n})$. After passing to subsequences if necessary we assume that $u_{n}\to u$ and $v_{n}\to v$. Then $\left\langle{u},{v}\right\rangle=1$ and thus $v=u$. Since $x_{n}\to c$, we deduce that $P_{A}x_{n}\to P_{A}c=c$, $R_{A}x_{n}\to c$, and $P_{B}R_{A}x_{n}\to c$. Thus, $u\in N_{A}(c)$ and $-u\in N_{B}(c)$. Altogether, $u\in N_{A}(c)\cap(-N_{B}(c))\cap Y\smallsetminus\{0\}$, which contradicts (31). We thus have proved (29).

Now let $x\in\operatorname{ball}(c;\delta)\cap L$. Because $d_{B}$ is nonexpansive and $R_{A}-\operatorname{Id}=2(P_{A}-\operatorname{Id})$, we deduce with the Cauchy–Schwarz inequality that

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

In particular, $d_{A\cap B}(x_{n})>0$ and $x_{n}-Tx_{n}\to 0$. After passing to subsequences if necessary, we assume that $x_{n}\to\bar{x}$. Then $\bar{x}\in L\cap\operatorname{Fix}T$. By Proposition 4.1(iii), $\bar{x}\in A\cap B$. Using Lemma 4.2 and after passing to another subsequence if necessary, we obtain $\theta<1$ such that

This is absurd since $\varepsilon_{n}\to 0^{+}$. $\hfill\quad\blacksquare$

We are now ready for the main result of this section.

Suppose that the pair $(A,B)$ is transversal, i.e., $\operatorname{ri}A\cap\operatorname{ri}B\neq\varnothing$. Then $T$ is boundedly linearly regular.

Lemma 4.2, which lies at the heart of this section, is proved in much greater generality in the recent paper . The novelty here is to deduce bounded linear regularity of the Douglas–Rachford operator (see Theorem 4.4) in order to make it a useful building block to obtain other linear and strong convergence results.

Fejér Monotonicity and Set Regularities

Since all algorithms considered in this paper generate Fejér monotone sequences, we review this key notion next.

Clearly, every Fejér monotone sequence is bounded. Let us now review some results concerning norm and linear convergence of Fejér monotone sequences.

Proof. (i): See, e.g., [8, Theorem 5.12]. (ii): See, e.g., [8, Proposition 5.9(ii)]. $\hfill\quad\blacksquare$

Corollary 5.4 implies the following example, which was analyzed in much greater detail in .

Proof. $T$ is averaged (even firmly nonexpansive), and linearly regular by Example 2.5. Now apply Corollary 5.4. $\hfill\quad\blacksquare$

Proof. Combine Theorem 4.4 with Corollary 5.4. $\hfill\quad\blacksquare$

2 Regularities for families of sets

We now recall the notion of a collection of regular sets and key criteria. This will be crucial in the formulation of the linear convergence results.

Let $(C_{i})_{i\in I}$ be a finite family of closed convex subsets of $X$ with $C=\bigcap_{i\in I}C_{i}\neq\varnothing$. We say that:

$(C_{i})_{i\in I}$ is linearly regular if $(\exists\,\mu>0)$ $(\forall x\in X)$ $d_{C}(x)\leq\max_{i\in I}d_{C_{i}}(x)$.

$(C_{i})_{i\in I}$ is boundedly linearly regular if $(\forall\rho>0)$ $(\exists\,\mu>0)$ $(\forall x\in\operatorname{ball}(0;\rho))$ $d_{C}(x)\leq\max_{i\in I}d_{C_{i}}(x)$.

Suppose that $I=\{1,\ldots,m\}$, and let $(C_{i})_{i\in I}$ be a finite family of closed convex subsets of $X$ with $C=\bigcap_{i\in I}C_{i}\neq\varnothing$. Then the following hold:

Suppose each $C_{i}$ is a subspace. Then $(C_{i})_{i\in I}$ is regular in any of the four senses if and only if $\sum_{i\in I}C_{i}^{\perp}$ is closed.

Suppose each $C_{i}$ is a cone. Then $(C_{i}\cap C^{\ominus})_{i\in I}$ is regular in any of the four senses if and only if $\sum_{i\in I}(C_{i}\cap C^{\ominus})^{\ominus}$ is closed.

Suppose each $C_{i}$ is a cone and $C=\{0\}$. Then $(C_{i})_{i\in I}$ is regular in any of the four senses if and only if $\sum_{i\in I}C_{i}^{\ominus}$ is closed.

If $C_{m}\cap\operatorname{int}(C_{1}\cap\cdots\cap C_{m-1})\neq\varnothing$, then $(C_{i})_{i\in I}$ is boundedly linearly regular.

If $(C_{1},C_{2})$, $(C_{1}\cap C_{2},C_{3})$, …, $(C_{1}\cap\cdots\cap C_{m-1},C_{m})$ are (boundedly) linearly regular, then so is $(C_{i})_{i\in I}$.

If $0\in\operatorname{sri}(C_{1}-C_{2})$, then $(C_{1},C_{2})$ is boundedly linearly regular.

If each $C_{i}$ is a polyhedron, then $(C_{i})_{i\in I}$ is linearly regular.

If $X$ is finite-dimensional, $C_{1},\ldots,C_{k}$ are polyhedra, and $C_{1}\cap\cdots C_{k}\cap\operatorname{ri}(C_{k+1})\cap\cdots\cap\operatorname{ri}(C_{m})\neq\varnothing$, then $(C_{i})_{i\in I}$ is boundedly linearly regular.

If $X$ is finite-dimensional, then $(C_{i})_{i\in I}$ is boundedly regular.

Proof. (i): [7, Theorem 5.19]. (ii): [18, Theorem 3.28]. (iii): [18, Corollary 3.30]. (iv): [7, Corollary 5.13]. (v): [7, Theorem 5.11]. (vi): [6, Corollary 4.5]. (vii): [7, Corollary 5.26]. (viii): [4, Theorem 5.6.2]. (ix): . $\hfill\quad\blacksquare$

Let $(C_{i})_{i\in I}$ be a finite family of closed convex subsets of $X$ with $C=\bigcap_{i\in I}C_{i}\neq\varnothing$. We say that $(C_{i})_{i\in I}$ is innately boundedly regular if $(C_{j})_{j\in J}$ is boundedly regular for every nonempty subset $J$ of $I$. Innate regularity and innate (bounded) linear regularity are defined analogously.

Fact 5.8 allows to formulate a variety of conditions sufficient for innate regularity. Here, we collect only some that are quite useful.

Let $(C_{i})_{i\in I}$ be a finite family of closed convex subsets of $X$ with $C=\bigcap_{i\in I}C_{i}\neq\varnothing$. Then the following hold:

If $X$ is finite-dimensional, then $(C_{i})_{i\in I}$ is innately boundedly regular.

If $X$ is finite-dimensional and $\bigcap_{i\in I}\operatorname{ri}C_{i}\neq\varnothing$, then $(C_{i})_{i\in I}$ is innately linearly regular.

If each $C_{i}$ is a subspace and $\sum_{j\in J}C_{j}^{\perp}$ is closed for every nonempty subset $J$ of $I$, then $(C_{i})_{i\in I}$ is innately linearly regular.

Proof. (i): Fact 5.8(ix). (ii): Fact 5.8(viii). (iii): Fact 5.8(i). $\hfill\quad\blacksquare$

Convergence Results for Quasi-Cyclic Algorithms

Unless otherwise stated, we assume from now on that

is a finite family of nonexpansive operators from $X$ to $X$ with common fixed point set

We are now ready for our first main result.

Proof. Set $\sigma_{+}=\min_{i\in I}\sigma_{i}$, where $\sigma_{i}=\sigma(T_{i})$. Let $i\in I$. By assumption,

Get $\beta_{j}$ as in (22) (with $T$ replaced by $T_{j}$) and set $\beta_{+}=\min_{j\in I}\beta_{j}>0$. In view of Corollary 3.5, it follows that

Applying this with $z=P_{Z}x_{kp}$ (and releasing $i$) yields

Theorem 6.1 is quite flexible in the amount of control a user has in generating sequences. We point out two very popular instances next.

Some concrete and new results will be considered in Section 8; there are already several known results that can be deduced from this framework (see, e.g., and ).

We mention here the related frameworks by Kiwiel and Łopuch who bundled regularity of the fixed point sets together with regularity of the operators to study accelerated generalizations of projection methods. Theirs and our techniques find their roots in ; see also . We feel that the approach presented here is more convenient for applications; indeed, one first checks that the operators are well behaved — the algorithms will be likewise if the fixed point sets relate well to each other.

We end this section with the following probabilistic result whose basic form is due to Leventhal . The proof presented here is somewhat simpler and the conclusion is stronger.

On the other hand, by bounded linear regularity of $(Z_{1},\ldots,Z_{m})$, we get $\mu>0$ such that

Combining and taking the expected value, we deduce

and the result follows with $\theta=1-\mu$. $\hfill\quad\blacksquare$

Convergence Results for Cyclic and Random Algorithms

In this section, we focus on strong convergence results for algorithms which utilize the operators either cyclically or in a more general, not necessarily quasicyclic, fashion. Simple examples involving projectors show that linear convergence results are not to be expected. Accordingly, the less restrictive notion of (bounded) regularity is introduced — it is sufficient for strong convergence.

We start our analysis with the following notion which can be seen as a qualitative variant of (bounded) linear regularity.

Let $T\colon X\to X$ be such that $\operatorname{Fix}T\neq\varnothing$. We say that:

Comparing with Definition 2.1, we note that

These notions are much less restrictive than their quantitative linear counterparts:

Let $T\colon X\to X$ be continuous, suppose that $X$ is finite-dimensional Or, more generally, that $\operatorname{ran}T$ is boundedly compact. and that $\operatorname{Fix}T\neq\varnothing$. Then $T$ is boundedly regular.

We now turn to “property (S)”, a notion first considered by Dye et al. in .

Let $T\colon X\to X$ be averaged nonexpansive such that $\operatorname{Fix}T\neq\varnothing$. Then $T$ has property (S) with respect to $\operatorname{Fix}T$.

Let $T\colon X\to X$ be nonexpansive and suppose that $T$ is projective with respect to $z\in\operatorname{Fix}T$. Then $T$ has property (S) with respect to $z$.

The importance of projectivity stems from the following observation.

Proof. See [3, Lemma 2.8.(iii)]. $\hfill\quad\blacksquare$

because $T_{i}$ is projective with respect to $z$. Altogether, $(\forall i\in I)$ $d_{Z_{i}}(x_{n})\to 0$. Since $(Z_{i})_{i\in I}$ is boundedly regular, it follows that $d_{Z}(x_{n})\to 0$. Hence $T$ is projective with respect to $z$ and the result now follows from Fact 7.7. $\hfill\quad\blacksquare$

Property (S) in tandem with bounded regularity implies projectivity, which turns out to be crucial for the results on random algorithms.

Let $T\colon X\to X$ be nonexpansive such that $\operatorname{Fix}T\neq\varnothing$, and let $z\in\operatorname{Fix}T$. Suppose that $T$ satisfies property (S) with respect to $z$, and that $T$ is boundedly regular. Then $T$ is projective with respect to $z$.

Let $T\colon X\to X$ be averaged nonexpansive and boundedly regular such that $\operatorname{Fix}T\neq\varnothing$. Then $T$ is projective with respect to $\operatorname{Fix}T$.

Proof. Combine Proposition 7.4 and Proposition 7.9. $\hfill\quad\blacksquare$

We now obtain a powerful strong convergence result for cyclic algorithms.

Proof. By Corollary 7.10, each $T_{i}$ is projective with respect to every point in $Z$. The result thus follows from Proposition 7.8. $\hfill\quad\blacksquare$

Proof. By Corollary 7.10, each $T_{i}$ is projective with respect to $Z_{i}$ and hence with respect to $Z$. Now apply Fact 7.13 and Fact 5.3(ii). $\hfill\quad\blacksquare$

Applications and Numerical Results

In this section, $I=\{1,\ldots,m\}$ and $(U_{i})_{i\in I}$ is a family of closed convex subsets of $X$ with

The following result is due to Borwein and Tam (see [12, Theorem 3.1]):

The following new results now follow from our analysis.

Suppose that $X$ is finite-dimensional and that $\bigcap_{i\in I}\operatorname{ri}U_{i}\neq\varnothing$. Then the convergence of the Borwein–Tam method is with a linear rate.

Proof. Combine Theorem 4.4 with Corollary 6.2. $\hfill\quad\blacksquare$

Suppose that each $U_{i}$ is a subspaceA simple translation argument yields a version for affine subspaces with a nonempty intersection. with $U_{i}+U_{i+1}$ is closed, and that $(Z_{i})_{i\in I}$ is boundedly linearly regular. Then the convergence of the Borwein–Tam method is with a linear rate.

Proof. Combine Example 2.5 with Corollary 6.2. $\hfill\quad\blacksquare$

Of course, using Theorem 6.1, we can formulate various variants for a general quasicyclic variant. We conclude this section with a random version.

Proof. Combine Example 2.5 with Theorem 7.14. $\hfill\quad\blacksquare$

2 The Cyclically Anchored Douglas–Rachford Algorithm (CADRA)

In this section, we assume that $I=\{1,\ldots,m\}$, that $A$ is a closed convex subset of $X$, also referred to as the anchor, and that $(B_{i})_{i\in I}$ is a family of closed convex subsets of $X$ such that

Note that when $m=1$, then CADRA coincides with the classical Douglas–Rachford algorithmThis is not the case for the BTM considered in the previous subsection..

Let us record a central convergence result concerning the CADRA.

$X$ is finite-dimensional and that $\operatorname{ri}(A)\cap\bigcap_{i\in I}\operatorname{ri}(B_{i})\neq\varnothing$.

$A$ and each $B_{i}$ is a subspace with $A+B_{i}$ closed and that $(Z_{i})_{i\in I}$ is boundedly linearly regular.

Proof. The weak convergence follows from e.g. [7, Theorem 5.22]. (i): Now combine Theorem 4.4 with Corollary 6.2. (ii): Combine Example 2.5 with Corollary 6.2. $\hfill\quad\blacksquare$

One may also obtain a random version of CADRA by using Theorem 7.14.

3 Numerical experiments

We divide the 50 problems into 5 groups, depending on the value of $m$. In Table 1, we record the median of the number of iterations required for each algorithm to terminate, and we also list the percentage that each algorithm is the fastest among the three.

Finally, we observe that CADRA performs quite well compared to CycP and BTM, especially when the range of parameters keep the problems moderately underdetermined.

Acknowledgments

HHB was partially supported by the Natural Sciences and Engineering Research Council of Canada and by the Canada Research Chair Program. DN acknowledges hospitality of the University of British Columbia in Kelowna and support by the Pacific Institute of the Mathematical Sciences during the preparation of this paper. HMP was partially supported by an NSERC accelerator grant of HHB.

References