Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity

Introduction

Consider the problem of finding a point in the intersection of a finite family of closed convex subsets of a Hilbert space; a problem often referred to as the convex feasibility problem which arises frequently throughout areas of mathematics, science and engineering. For details, we refer the reader to the surveys , the monographs , any of , and the references therein.

One approach to solving convex feasibility problems involves designing a nonexpansive operator whose fixed point set can be used to easily produce a point in the target intersection (in the simplest case, the fixed point set coincides with the target intersection). The operator’s fixed point iteration can then be used as the basis of an iterative algorithm which, in the limit, yields the desired solution. An important class of such methods comprises the so-called projection and reflection methods which employ various combinations of projection and reflection operations with respect to underlying constraint sets.

Notable methods of this kind include the alternating projection algorithm, the Douglas–Rachford (DR) algorithm , and many extensions and variants . Even in settings without convexity , such methods remain a popular choice due largely to their simplicity, ease-of-implementation and relatively – often surprisingly – good performance.

The origins of the Douglas–Rachford (DR) algorithm can be traced to where it was used to solve problems arising in nonlinear heat flow. In its full generality, the method finds zeros of the sum of two maximal monotone operators. Weak convergence of the scheme was originally proven by Lions and Mercier , and the result was recently strengthened by Svaiter . Specialized to feasibility problems, Svaiter’s result implies that the iterates generated by the DR algorithm are always weakly convergent, and that the shadow sequence converges weakly to a point in the intersection of the two closed convex sets. The scheme has also been examined in where its relationship with another popular method, the proximal point algorithm, was discussed.

Motivated by the computational observation that the Douglas–Rachford algorithm sometimes outperforms other projection methods, in the convex case many researchers have studied the actual convergence rate of the algorithm. By convergence rate, we mean how fast the sequences generated by the algorithm converges to their limit points. For the Douglas–Rachford algorithm, the first such result, which appeared in and was later extended by , showed the algorithm to converge linearly whenever the two constraint sets are closed subspaces with a closed sum, and, further, that the rate is governed exactly by the cosine of the Friedrichs angle between the subspaces. In finite dimensions, if the sum of the two subspaces is not closed, convergence of the method – while still assured – need not be linear [11, Sec. 6]. See also for other recent work regarding linear convergence. For most projection methods, it is typical that there exists instances in which the rate of convergence is arbitrarily slow and not even sublinear or arithmetic . Most recently, a preprint of Davis and Yin shows that indeed the Douglas–Rachford method also may converge arbitrarily slowly in infinite dimensions [25, Th. 9].

In potentially nonconvex settings, a number of recent works have established local linear convergence rates for the DR algorithm using commonly used constraint qualifications. When specialized to the convex case, these results state that the DR algorithm exhibits locally linear convergence for convex feasibility problems in a finite dimensional space whenever the relative interiors of the two convex sets have a non-empty intersection. On the other hand, when such a regularity condition is not satisfied, the DR algorithm can fail to exhibit linear convergence, even in simple two dimensional cases as observed by [12, Ex. 5.4(iii)] (see Section 6 for further examples and discussion). This situation therefore calls for further research aimed at answering the question: Can a global convergence rate for the DR algorithm and its variants be established or estimated for some reasonable class of convex sets without the above mentioned regularity condition?

The goal of this paper is to provide some partial answers to the above question, as well as giving simple tools for establishing sublinear or linear convergence of the Douglas–Rachford algorithm and variants. Our analysis is performed within the much more general setting of fixed point iterations described by averaged nonexpansive operators. This broad framework covers many iterative fixed-point methods including various Krasnoselskii–Mann iterations, the cyclic projection algorithm, Douglas–Rachford algorithms and forward-backward splitting methods, and can be used to solve not only convex feasibility problems but also convex optimization problems and variational inequality problems. We pay special attention to the case in which the underlying sets are convex semi-algebraic sets in a finite dimensional space. Such sets comprise a broad sub-class of convex sets that we shall show satisfy Hölder regularity properties without requiring any further assumptions. Indeed, they capture all polyhedra and convex sets described by convex quadratic functions. Furthermore, convex semi-algebraic structure can often be relatively easily identified.

The detailed contributions of this paper are summarized as follows:

We study an abstract algorithm which we refer to as the quasi-cyclic algorithm. This algorithm covers many iterative fixed-point methods including various Krasnoselskii–Mann iterations, the cyclic projection algorithm, Douglas–Rachford algorithms and forward-backward splitting methods. In the presence of so-called bounded Hölder regularity properties, sublinear convergence of the algorithm is then established (Theorem 15).

The quasi-cyclic algorithm framework is then specialized to the Douglas–Rachford algorithm and its variants (Section 4). We show the results apply, for instance, to the important case of feasibility problems for which the underlying sets are convex semi-algebraic in a finite dimensional space.

A damped variant of the Douglas–Rachford algorithm is examined. Again, in the case in which the underlying sets are convex basic semi-algebraic sets in a finite dimensional space, we obtain a more explicit estimate of the sublinear convergence rate in terms of the dimension of the underlying space and the maximum degree of the polynomials involved (Theorem 5.46).

The remainder of the paper is organized as follows: in Section 2 we recall definitions and key facts used in our analysis. In Section 3 we investigate the rate of convergence of the quasi-cyclic algorithm. In Section 4 we specialize these results to the classical Douglas–Rachford algorithm and its cyclic variants. In Section 5 we consider a damped version of the Douglas–Rachford algorithm. In Section 6 we establish explicit convergence rates for two illustrative problems. We conclude the paper in Section 7 by discussing possible directions for future research.

Preliminaries

Throughout this paper our setting is a (real) Hilbert space $H$ with inner product $\langle\cdot,\cdot\rangle$. The induced norm is defined by $\|x\|:=\sqrt{\langle x,x\rangle}$ for all $x\in H$. Given a closed convex subset $A$ of $H$, the (nearest point) projection operator is the operator ${\rm P_{A}}:H\to A$ given by

Let us now recall various definitions and facts used throughout this work, beginning with the notion of Fejér monotonicity.

We now turn our attention to a Hölder regularity property for typically finite collections of sets.

It is clear, from Definition 4, that any collection containing only a single set trivially has a bounded Hölder regular intersection with uniform exponent $\gamma=1$. More generally, Definition 4 with $\gamma=1$ is well-studied in the literature where it appears, amongst other names, as bounded linear regularity . For a recent study, the reader is referred to [32, Remark 7]. The local counterpart to Definition 4 has been characterized in [32, Th. 1] under the name of metric $[\gamma]$-subregularity.

We next turn our attention to a nonexpansivity notion for operators.

firmly non-expansive if, for all $x,y\in H$,

$\alpha$-averaged for some $\alpha\in(0,1)$, if there exists a non-expansive mapping $R\colon H\to H$ such that

The class of firmly non-expansive mappings comprises precisely the 1/2-averaged mappings, and any $\alpha$-averaged operator is non-expansive [7, Ch. 4]. The term “av- eraged mapping” was coined in . The following fact provides a characterization of averaged maps that is useful for our purposes.

Let $T\colon H\to H$ be an $\alpha$-averaged operator on a Hilbert space with $\alpha\in(0,1)$. Then, for all $x,y\in H$,

Denote the set of fixed points of an operator $T\colon H\to H$ by

The following definition is of a Hölder regularity property for operators.

An operator $T\colon H\to H$ is bounded Hölder regular if, for each bounded set $K\subseteq H$, there exists an exponent $\gamma\in(0,1]$ and a scalar $\mu>0$ such that

Furthermore, if the exponent $\gamma$ does not depend on the set $K$, we say that $T$ is bounded Hölder regular with uniform exponent $\gamma$.

Note that, in the case when $\gamma=1$, Definition 7 collapses to the well studied concept of bounded linear regularity and has been used in to analyze linear convergence of algorithms involving non-expansive mappings. Moreover, it is also worth noting that if an operator $T$ is bounded Hölder regular with exponent $\gamma\in(0,1]$ then the mapping $x\mapsto x-T(x)$ is bounded Hölder metric subregular with exponent $\gamma$. Hölder metric subregularity – which is a natural extension of metric subregularity – along with Hölder type error bounds has recently been studied in .

Finally, we recall the definitions of semi-algebraic functions and semi-algebraic sets.

The next fact summarises some fundamental properties of semi-algebraic sets and functions.

Any polynomial is a semi-algebraic function.

Let $D$ be a semi-algebraic set. Then ${\rm dist}(\cdot,D)$ is a semi-algebraic function.

(P1) and (P4) follow directly from the definitions. See [14, Prop. 2.2.8] for (P2), [14, Prop. 2.2.6] for (P3) and (P5), and [14, Cor. 2.6.7] for (P6). ∎

Any basic semi-algebraic convex set is clearly convex and semi-algebraic. On the other hand, there exist sets which are both convex and semi-algebraic but fail to be basic semi-algebraic convex set, see .

It transpires out that any finite collection of basic semi-algebraic convex sets has an intersection which is boundedly Hölder regular with uniform exponent (without requiring further regularity assumptions). In the following lemma, $B(n)$ denotes the central binomial coefficient with respect to $n$ given by $\binom{n}{[n/2]}$ where $[\,\cdot\,]$ denotes the integer part of a real number.

where $\gamma=\left[\min\left\{\frac{(2d-1)^{n}+1}{2},\,B(n-1)d^{n}\right\}\right]^{-1}$.

We also recall the following useful recurrence relationship established in .

where the convention that $\frac{1}{0}=+\infty$ is adopted.

The rate of convergence of the quasi-cyclic algorithm

In this section we investigate the rate of convergence of an abstract algorithm we call quasi-cyclic. To define the algorithm, let $J$ be a finite set, and let $\{T_{j}\}_{j\in J}$ be a finite family of operators on a Hilbert space $H$. Given an initial point $x^{0}\in H$, the quasi-cyclic algorithm generates a sequence according to

The quasi-cyclic algorithm appears in where linear convergence of the algorithm was established under suitable regularity conditions. As we shall soon see, the quasi-cyclic algorithm provides a broad framework which covers many important existing algorithms including Douglas-Rachford algorithms, the cyclic projection algorithm, the Krasnoselskii–Mann method, and forward-backward splitting. To establish its convergence rate, we use three preparatory results.

from which, for sufficiently large $t$ , we deduce

Together with (5) this gives $\max_{j\in J_{+}(t)}\|x^{t}-T_{j}(x^{t})\|\to 0$ as claimed. ∎

The following proposition provides a convergence rate for Fejér monotone sequences satisfying an additional property, which we later show to be satisfied in the presence of Hölder regularity.

Let $F$ be a non-empty closed convex set in a Hilbert space $H$ and let $s$ be a positive integer. Suppose the sequence $\{x^{t}\}$ is Fejér monotone with respect to $F$ and satisfies

for some $\delta>0$ and $\theta\geq 1$. Then $x^{t}\rightarrow\bar{x}$ for some $\bar{x}\in F$ and, there exist constants $M_{1},M_{2}\geq 0$ and $r\in[0,1)$ such that

Furthermore, the constants may be chosen to be

and $\delta$ necessarily lies in $(0,1]$ whenever $\theta=1$.

Without loss of generality, we assume that $x^{0}\notin F$. Let $\beta_{t}:={\rm dist}^{2}(x^{ts},F)$ and $p:=\theta-1\geq 0$. Then (6) becomes

We now distinguish two cases based on the value of $\theta$.

Case 1: Suppose $\theta\in(1,+\infty)$. Then, noting that $1/(\theta-1)>0$, Lemma 12 implies

It follows that ${\rm dist}(x^{ts},F)=\sqrt{\beta_{t}}\leq\left[(\theta-1)\delta\right]^{-\frac{1}{2(\theta-1)}}t^{-\frac{1}{2(\theta-1)}}$. In particular, we have $\|x^{ts}-{\rm P}_{F}(x^{ts})\|={\rm dist}(x^{ts},F)\rightarrow 0$. By Fact 2, ${\rm P}_{F}(x^{ts})\rightarrow\bar{x}$ for some $\bar{x}\in F$ and hence $x^{ts}\rightarrow\bar{x}\in F$ as $t\rightarrow\infty$. Denote

and, on the other hand, if $t>2s$ (and so, $\frac{t}{s}-1\geq\frac{t}{2s})$, then

Here $\lfloor\frac{t}{s}\rfloor$ denotes the largest integer which is smaller or equal to $\frac{t}{s}$, the first inequality follows from the Fejér monotonicity of $\{x^{t}\}$ and the last inequality follows from the definition of $\bar{M}_{1}$. This, together with Fact 3, implies that

where the last equality follows from the definition of $M_{1}$.

Let $\bar{M}_{2}=\max\{\left(\sqrt[4s]{1-\delta}\right)^{-2s}{\rm dist}(x^{0},F),\sqrt{{\rm dist}(x^{0},F)}\}$. On one hand, if $t\leq 2s$, then

and, on the other hand, if $t>2s$ (and so, $\frac{t}{s}-1\geq\frac{t}{2s})$, then

By the same argument as used in Case 1, for some $\bar{x}\in F$, we see that

The conclusion follows by setting $r=\sqrt[4s]{1-\delta}\in[0,1).$ ∎

We are now in a position to state our main convergence result, which we simultaneously prove for both variants of our Hölder regularity assumption (non-uniform and uniform versions).

For each $j\in J$, the operator $T_{j}$ is bounded Hölder regular .

$\{{\rm Fix\ }T_{j}\}_{j\in J}$ has a boundedly Hölder regular intersection.

Then $x^{t}\to\bar{x}\in\cap_{j\in J}{\rm Fix\,}T_{j}\neq\emptyset$ at least with a sublinear rate $O(t^{-\rho})$ for some $\rho>0$.

In particular, if we assume ${\rm(a^{\prime})}$, ${\rm(b^{\prime})}$ and ${\rm(c)}$ hold where ${\rm(a^{\prime})}$, ${\rm(b^{\prime})}$ are given by

for each $j\in J$, the operator $T_{j}$ is bounded Hölder regular with uniform exponent $\gamma_{1,j}\in(0,1]$;

$\{{\rm Fix\ }T_{j}\}_{j\in J}$ has a bounded Hölder regular intersection with uniform exponent $\gamma_{2}\in(0,1]$,

then there exist constants $M_{1},M_{2}\geq 0$ and $r\in[0,1)$ such that

where $\gamma:=\gamma_{1}\gamma_{2}$ and $\gamma_{1}:=\min\{\gamma_{1,j}\mid j\in J\}$.

Denote $F:=\cap_{j\in J}{\rm Fix\,}T_{j}$. We first consider the case in which Assumptions (a), (b) and (c) hold. We first observe that, as a consequence of Lemma 13, we may assume without loss of generality the following two inequalities holds:

Set $\gamma_{1}=\min\{\gamma_{1,j}\mid j\in J\}$ and $\mu:=\max\{\mu_{j}\mid j\in J\}$. By (11) and (9), for all $j\in J_{+}(t)$, it follows that

Also, since $\{{\rm Fix\ }T_{j}\}_{j\in J}$ has a boundedly Hölder regular intersection, there exist an exponent $\gamma_{2}>0$ and a scalar $\beta>0$ such that

where the second from last inequality follows from convexity of the function $(\cdot)^{2}$, and the last uses (12) noting that $j^{\prime}\in J_{+}(t_{k})$.

Furthermore, for each $n\in\{ts,\ldots,(t+1)s-1\}$, applying $x=x^{n}$ and $y=P_{F}(x^{ts})$ in (3) we have

where the last inequality follows from (10). Altogether, combining (14), (16) and (17) gives

Since $j^{\prime}\in J$ was chosen arbitrary, using (13) we obtain

where the constant $\delta>0$ and $\gamma>0$ are given by

Then, the first assertion follows from Proposition 14.

To establish the second assertion, we suppose that the assumptions (a′), (b′) and (c) hold. Proceed with the same proof as above, and noting that the exponents $\gamma_{1j}$ and $\gamma_{2}$ are now independent of the choice of $K$, we see that the second assertion also follows. ∎

A closer look at the proof of Theorem 15 reveals that a quantification of the constants $M_{1},M_{2}$ and $r$ is possible using the various regularity constants/exponents and (7). More precisely, (7) holds with

Here $\mu$ is the max of the constants of bounded Hölder regularity of the individual operators $T_{j}$ and $\beta$ is the constant of bounded Hölder regularity of the collection $\{{\rm Fix\ }T_{j}\}_{j\in J}$, respectively, on an appropriate compact set. Consequently, these expressions, appropriately specialized, also hold for all the subsequent corollaries of Theorem 15.

Theorem 15 generalizes [10, Th. 6.1] which considers the special case in which the Hölder exponents are independent of the bounded set $K$ and are specified by $\gamma_{1j}=\gamma_{2}=1$, $j=1,\ldots,m$.

A slight refinement of Theorem 15 which allows for extrapolations as well as different averaging constants is possible. More precisely, an extrapolation of the operator $T$ (in the sense of ) is a (non-convex) combination of the form $wT+(1-w)I$ where the weight $w$ may take values larger than $1$. Recall that for a finite set $\Omega$, we use $|\Omega|$ to denote the number of elements of $\Omega$.

Let $x^{0}\in H$ and consider the extrapolated quasi-cyclic algorithm generated by

For each $j\in J$, the operator $T_{j}$ is bounded Hölder regular.

$\{{\rm Fix\ }T_{j}\}_{j\in J}$ has a boundedly Hölder regular intersection.

Then $x^{t}\to\bar{x}\in\cap_{j\in J}{\rm Fix\,}T_{j}\neq\emptyset$ at least with a sublinear rate $O(t^{-\rho})$ for some $\rho>0$.

In particular, if we assume ${\rm(a^{\prime})}$, ${\rm(b^{\prime})}$ and ${\rm(c)}$ hold where ${\rm(a^{\prime})}$, ${\rm(b^{\prime})}$ are given by

for each $j\in J$, the operator $T_{j}$ is bounded Hölder regular with uniform exponent $\gamma_{1,j}\in(0,1]$;

$\{{\rm Fix\ }T_{j}\}_{j\in J}$ has a bounded Hölder regular intersection with uniform exponent $\gamma_{2}\in(0,1]$,

then there exist constants $M_{1},M_{2}\geq 0$ and $r\in[0,1)$ such that

where $\gamma:=\gamma_{1}\gamma_{2}$ and $\gamma_{1}:=\min\{\gamma_{1,j}\mid j\in J\}$.

For each $j\in J$, by Definition 5(c), the operator $\overline{T}_{j}$ is $\alpha$-averaged where

Let $\overline{w}_{j,t}:=\frac{w_{j,t}\alpha_{j}}{\alpha}$, $j\in J$. Then, $\overline{w}_{j,t}\geq 0$ and

This together with Assumption (c) of this corollary implies that Assumption (c) of Theorem 15 holds for $\{\overline{w}_{j,t}\}_{j\in\overline{J}}$. Therefore,the claimed result now follows from Theorem 15.

Throughout this work we assume the collection of operators $\{T_{j}\}_{j\in J}$ ($J$ a finite index set) to have a common fixed point. In this setting, with appropriate nonexpansivity properties, one has that the fixed point set of convex combinations or compositions of the operators $\{T_{j}\}_{j\in J}$ is precisely the set of their common fixed points. Whilst there do exist several instance where such an assumption does not hold (e.g., regularization schemes such as ), this does not preclude their analysis using the theory presented here (see Proposition 4.39). Indeed, for such cases, the fixed point set of an appropriate convex combination or composition of operators is non-empty, and this aggregated operator thus amenable to our results (rather than the individual operators themselves). The question of usefully characterizing the fixed point set of this aggregated operator must then be addressed; a matter significantly more subtle in the absence of a common fixed point.

We next provide four important specializations of Theorem 15. The first result is concerned with a simple fixed point iteration, the second with a Kransnoselskii–Mann scheme, the third with the method of cyclic projections, and the fourth with forward-backward splitting for variational inequalities.

Let $T$ be an $\alpha$-averaged operators on a Hilbert space $H$ with ${\rm Fix}\,T\neq\emptyset$ and $\alpha\in(0,1)$. Suppose $T$ is bounded Hölder regular. Let $x^{0}\in H$ and set $x^{t+1}=Tx^{t}$. Then $x^{t}\to\bar{x}\in{\rm Fix}\,T\neq\emptyset$ at least with a sublinear rate $O(t^{-\rho})$ for some $\rho>0$. In particular, if $T$ is bounded Hölder regular with uniform exponent $\gamma\in(0,1]$ then exist $M>0$ and $r\in[0,1)$ such that

The conclusion follows immediately from Theorem 15.

Then $x^{t}\to\bar{x}\in{\rm Fix}\,T\neq\emptyset$ at least with a sublinear rate $O(t^{-\rho})$ for some $\rho>0$. In particular, if $T$ is bounded Hölder regular with uniform exponent $\gamma\in(0,1]$ then there exist $M>0$ and $r\in[0,1)$ such that

A straightforward manipulation shows that the identity map, $I$, is bounded Hölder regular with uniform exponent $\gamma_{1,1}\leq 1$. Since ${\rm Fix}\,I=H$, the collection $\{{\rm Fix}\,I,{\rm Fix}\,T\}$ has a bounded Hölder regular intersection with exponent $1$. The result now follows from Theorem 15.

The following result includes [17, Th. 4.4] and [6, Th. 3.12] a special cases.

Let $J=\{1,2,\dots,m\}$ and let $\{C_{j}\}_{j\in J}$ a collection of closed convex subsets of a Hilbert space $H$ with non-empty intersection. Given $x^{0}\in H$, set

Suppose that $\{C_{j}\}_{j\in J}$ has a bounded Hölder regular intersection. Then $x^{t}\to\bar{x}\in\cap_{j\in J}C_{j}\neq\emptyset$ at least with a sublinear rate $O(t^{-\rho})$ for some $\rho>0$. In particular, if the collection $\{C_{j}\}_{j\in J}$ is bounded Hölder regular with uniform exponent $\gamma\in(0,1]$ there exist $M>0$ and $r\in[0,1)$ such that

First note that the projection operator over a closed convex set is $1/2$-averaged. Now, for each $j\in J$, $C_{j}={\rm Fix\,P}_{C_{j}}$, and hence

That is, for each $j\in J$, the projection operator ${\rm P}_{C_{j}}$ is bounded Hölder regular with uniform exponent $1$. The result follows from Theorem 15.

We now turn our attention to variational inequalities [7, Ch. 25.5]. Let $f:H\to(-\infty,+\infty]$ be a proper lower semi-continuous (l.s.c.) convex function and let $F:H\mapsto H$ be $\beta$-cocoercive, that is,

The generalized variational inequality problem, denoted ${\rm VIP}(F,f)$, is:

and the set of solutions to (20) is denoted ${\rm Sol}({\rm VIP}(F,f))$.

The forward-backward splitting method is often employed to solve $VIP(F,f)$ (see, for instance, [7, Prop. 25.18]) and generates a sequence $\{x^{t}\}$ according to

where $R_{T_{0}}:=(I+T_{0})^{-1}$ denotes the resolvent of an operator $T_{0}$. Here, we note that $\partial f$ is a maximal monotone operator and so, its resolvent is single-valued.

If $T_{2}:=R_{\gamma\partial f}(I-\gamma F)$ is bounded Hölder regular then $x^{t}\to\bar{x}\in{\rm Sol}({\rm VIP}(F,f))$ at least with a sublinear rate $O(t^{-\rho})$ for some $\rho>0$. In particular, if $T$ is bounded Hölder regular with uniform exponent $\gamma\in(0,1]$ then there exist $M>0$ and $r\in[0,1)$ such that

Since $F$ is $\beta$-cocoercive, [7, Prop. 4.33] shows that $I-\gamma F$ is $\gamma/(2\beta)$-averaged. The operator $R_{\gamma\partial f}$ is $\frac{1}{2}$-averaged, as the resolvent of a maximally monotone operator. By [7, Prop. 4.32], $T_{2}$ is $\frac{2}{3}$-averaged. Applying Corollary 3.23 with $T=T_{2}$, the claimed convergence rate to a point $\bar{x}\in{\rm Fix\ }T_{2}$ thus follows.

It remains to show that ${\rm Fix\ }T_{2}={\rm Sol}({\rm VIP}(F,f))$. Indeed, $x\in{\rm Fix\ }T_{2}$ if and only if

which is a semi-algebraic set since $(I+\gamma\partial f)$ is a semi-algebraic function by Fact 9, and hence the resolvent is a semi-algebraic mapping. A further application of Fact 9, shows that $T_{2}$ is semi-algebraic, as the composition of semi-algebraic maps.

We may therefore define two continuous semi-algebraic functions $\phi(x):={\rm dist}(x,{\rm Fix}T_{2})$ and $\varphi(x):=\|x-Tx\|$. Since $\phi^{-1}(0)={\rm Fix}T_{2}=\varphi^{-1}(0)$, (P6) of Fact 9 yields, for any compact semi-algebraic set $K$, the existence of constants $c>0$ and $\tau\in(0,1]$ such that

or, in other words, the bounded Hölder regularity of $T_{2}$.

The rate of convergence of DR algorithms for convex feasibility problems

We now specialize our convergence results to the classical DR algorithm and its variants in the setting of convex feasibility problems. In doing so, a convergence rate is obtained under the Hölder regularity condition. Recall that the basic Douglas–Rachford algorithm for two set feasibility problems can be stated as follows:

Direct verification shows that the relationship between consecutive terms in the sequence $(x^{t})$ of (23) can be described in terms of the firmly nonexpansive (two-set) Douglas–Rachford operator which is of the form

where $I$ is the identity mapping and $R_{C}:=2P_{C}-I$ is the reflection operator with respect to the set $C$ (‘reflect-reflect-average’).

We shall also consider the abstraction given by Algortihm 2 which chooses two constraint sets from some finite collection at each iteration. Note that iterations (23) and (25) have the same structure.

The motivation for studying Algorithm 2 is that, beyond Algorithm 1, it include two further DR-type schemes from the literature. The first scheme is the cyclic DR algorithm and is generated according to:

Let $p$ be a positive integer. The composition of $p$ Douglas–Rachford operators is $\frac{p}{p+1}$–averaged.

The two-set Douglas–Rachford operator of (24) is firmly nonexpansive, and hence $1/2$-averaged. The result follows by [7, Prop. 4.32].

Let $C_{1},C_{2},\dots,C_{m}$ be closed convex sets in a Hilbert space $H$ with non-empty intersection. Let $\{\Omega_{j}\}_{j=1}^{p}$ and $\{(y^{t},z^{t},x^{t})\}$ be generated by the multiple-sets Douglas–Rachford algorithm (23). Suppose that:

For each $j\in\{1,\dots,p\}$, the operator $T_{\Omega_{j}}$ is bounded Hölder regular.

The collection $\{{\rm Fix}\,T_{\Omega_{j}}\}_{j=1}^{p}$ has a bounded Hölder regular intersection.

Then $x^{t}\rightarrow\bar{x}\in\cap_{j=1}^{p}{\rm Fix\,}T_{\Omega_{j}}$ with at least a sublinear rate $O(t^{-\rho})$ for some $\rho>0$. In particular, suppose we assume the stronger assumptions:

For each $j\in\{1,\dots,p\}$, the operator $T_{\Omega_{j}}$ is bounded Hölder regular with uniform exponent $\gamma_{1,j}$.

The collection $\{{\rm Fix}\,T_{\Omega_{j}}\}_{j=1}^{p}$ has a bounded Hölder regular intersection with uniform exponent $\gamma_{2}\in(0,1]$.

Then there exist $M>0$ and $r\in(0,1)$ such that

where $\gamma:=\gamma_{1}\gamma_{2}$ where $\gamma_{1}:=\min\{\gamma_{1,j}\mid 1\leq j\leq s\}$.

Let $J=\{1,2,\dots,s\}$. For all $j\in J$, set $T_{j}=T_{\Omega_{j}}$ and

Since $T_{\Omega_{j}}$ is firmly nonexpansive (that is, $1/2$-averaged), the conclusion follows immediately from Theorem 15.

We next observe that bounded Hölder regularity of the Douglas-Rachford operator $T_{\Omega_{j}}$ and Hölder regular intersection of the collection $\{{\rm Fix}\,T_{\Omega_{j}}\}_{j=1}^{p}$ are automatically satisfied for the semi-algebraic convex case, and so, sublinear convergence analysis follows in this case without any further regularity conditions. This follows from:

For each $j\in\{1,\dots,p\}$, the operator $T_{\Omega_{j}}$ is bounded Hölder regular. Moreover, if $d=1$, then ${\rm T}_{\Omega_{j}}$ is bounded Hölder regular with uniform exponent $1$.

The collection $\{{\rm Fix}\,T_{\Omega_{j}}\}_{j=1}^{p}$ has a bounded Hölder regular intersection.

In particular, let $\{(y^{t},z^{t},x^{t})\}$ be generated by the multiple-sets Douglas–Rachford algorithm (25). Then there exists $\rho>0$ such that $x^{t}\rightarrow\bar{x}\in\cap_{j=1}^{p}{\rm Fix\,}T_{\Omega_{j}}$ with at least a sublinear rate $O(t^{-\rho})$.

By the Łojasiewicz inequality for semi-algebraic functions ((P6) of Fact 9), we see that for every $\rho>0$, one can find $\mu>0$ and $\gamma\in(0,1]$ such that

So, the Douglas–Rachford operator $T_{C_{1},C_{2}}$ is bounded Hölder regular in this case.

Then, a standard compactness argument shows that the Douglas–Rachford operator $T_{C_{1},C_{2}}$ is bounded linear regular, that is, uniformly bounded Hölder regular with exponent $1$.

Next, we assert that the collection $\{{\rm Fix}\,T_{\Omega_{j}}\}_{j=1}^{p}$ has a bounded Hölder regular intersection. To see this, as in the proof of part (a), we can show that for each $j=1,\ldots,p$, ${\rm Fix\,}T_{\Omega_{j}}$ is a semi-algebraic set. Then, their intersection $\cap_{j=1}^{p}{\rm Fix\,}T_{\Omega_{j}}$ is also a semi-algebraic set. Thus, $\psi(x)={\rm dist}(x,\cap_{j=1}^{p}{\rm Fix\,}T_{\Omega_{j}})$ and $\displaystyle\phi(x)=\max_{1\leq j\leq p}{\rm dist}(x,{\rm Fix\,}T_{\Omega_{j}})$ are semi-algebraic functions. It is easy to see that $\phi^{-1}(0)=\psi^{-1}(0)$ and hence the Łojasiewicz inequality for semi-algebraic functions ((P6) of Fact 9) implies that the collection $\{{\rm Fix}\,T_{\Omega_{j}}\}_{j=1}^{p}$ has a bounded Hölder regular intersection.

The final conclusion follows by Theorem 15.

Next, we establish the convergence rate for DR algorithm assuming bounded Hölder regularity of the Douglas–Rachford operator $T_{C,D}$.

Let $C,D$ be two closed convex sets in a Hilbert space $H$ with $C\cap D\neq\emptyset$, and let $T_{C,D}$ be the Douglas–Rachford operator. Let $\{(y^{t},z^{t},x^{t})\}$ be generated by the Douglas–Rachford algorithm (23). Suppose that $T_{C,D}$ is bounded Hölder regular. Then $x^{t}\rightarrow\bar{x}\in{\rm Fix\,}T_{C,D}$ with at least a sublinear rate $O(t^{-\rho})$ for some $\rho>0$. In particular, if $T_{C,D}$ is bounded Hölder regular with uniform exponent $\gamma\in(0,1]$ then there exist $M>0$ and $r\in(0,1)$ such that

Let $J=\{1\}$, $T_{1}=T_{C,D}$ and $w_{t,1}\equiv 1$. Note that $T_{C,D}$ is firmly nonexpansive (that is, $1/2$-averaged) and any collection containing only one set has Hölder regular intersection with exponent one. Then the conclusion follows immediately from Theorem 15.

Similar to Proposition 4.34, if $C$ and $D$ are basic convex semi-algebraic sets, then DR algorithm exhibits at least a sublinear convergence rate.

To conclude this section, we consider a regularization of the DR algorithm which converges even when the target intersection is empty where the sequence is generated by $x^{t+1}=T_{R}(x^{t})$ where $T_{R}:=\beta{\rm P_{C}}+(1-\beta)T_{C,D}$ and $\beta\in(0,1)$. When the target intersection $C\cap D$ is empty, this gives an example of a useful algorithm in which the two operators of interest, $P_{C}$ and $T_{C,D}$, have no common fixed point but can still be analyzed within our framework.

Let $C,D$ be two basic convex semi-algebraic sets and let $T_{C,D}$ be the Douglas–Rachford operator. Let $\{x^{t}\}$ be generated by $x^{t+1}:=T_{R}(x^{t})$ where $T_{R}=\beta{\rm P_{C}}+(1-\beta)T_{C,D}$ and $\beta\in(0,1)$. Then ${\rm P}_{D}(x^{t})\rightarrow\bar{x}_{1}\in D$ and ${\rm P}_{C}({\rm P}_{D}(x^{t}))\rightarrow\bar{x}_{2}\in C$ both with at least a sublinear rate $O(t^{-\rho})$ for some $\rho>0$ and $\|\bar{x}_{1}-\bar{x}_{2}\|={\rm dist}(C,D)$. In particular, if $C,D$ are polyhedral, then there exist $M>0$ and $r\in(0,1)$ such that

As $C,D$ be two basic convex semi-algebraic sets, $D-C$ is a closed set [17, Lemma 4.7]. Let $g=P_{D-C}(0)$, $E=C\cap(D-g)$ and $F=(C+g)\cap D$. Then, [44, Lemma 2.1] shows that ${\rm Fix}T_{R}=F-\frac{\beta}{1-\beta}\,g$, $P_{D}({\rm Fix}T_{R})\subseteq F$ and $P_{C}(P_{D}({\rm Fix}T_{R}))\subseteq E$. We first show that $T_{R}$ is bounded Hölder regular, and $T_{R}$ is bounded Hölder regular with uniform exponent $1$ if $C,D$ are polyhedral. To see this, we use the same argument as in Proposition 4.34 and it suffices to establish that $T_{R}-I$ is a semi-algebraic (resp. piecewise affine) map when $C$ and $D$ are semi-algebraic (resp. polyhedral). For the sake of avoiding repetition, we only show the latter. Observe that

Thus $T_{R}-I$ can be represented in terms of linear combinations and compositions of continuous semi-algebraic (resp. continuous piecewise affine) operators; more precisely, the projectors onto $C$ and $D$. Since projectors of convex semi-algebraic (resp. polyhedral) sets are semi-algebraic (resp. piecewise affine) and continuous, it follows that $T_{R}-I$ is semi-algebraic (resp. piecewise affine) and continuous. It then follows from Theorem 15 that $x^{t}\rightarrow\bar{x}\in{\rm Fix}T_{R}$ with at least a sublinear rate $O(t^{-\rho})$ for some $\rho>0$. From the non-expansive property of projection mapping, we see that ${\rm P}_{D}(x^{t})\rightarrow\bar{x}_{1}\in P_{D}({\rm Fix}T_{R})\subseteq F$ and ${\rm P}_{C}({\rm P}_{D}(x^{t}))\rightarrow\bar{x}_{2}=P_{C}(\bar{x}_{1})\subseteq E$ both with at least a sublinear rate $O(t^{-\rho})$. From the definitions of $E$, $F$ and $g$, it follows that $\|\bar{x}_{1}-\bar{x}_{2}\|={\rm dist}(C,D)$. The assertion for the linear convergence in the case where $C$ and $D$ are polyhedral also follows from Theorem 15.

The rate of convergence of the damped DR algorithm

We now investigate a variant of Algorithm 1 which we refer to as the damped Douglas–Rachford algorithm. To proceed, let $\eta>0$, let $A$ be a closed convex set in $H$, and define the operator ${\rm P}_{A}^{\eta}$ by

where $I$ denotes the identity operator on $H$. The operator ${\rm P}_{A}^{\eta}$ can be considered as a relaxation of the projection mapping. Further, a direct verification shows that

where ${\rm prox}_{f}$ denotes the proximity operator of the function $f$. The damped variant can be stated as follows:

In the more general setting in which $P_{C}^{\eta}$ and $P_{D}^{\eta}$ are, respectively, replaced by ${\rm prox}_{\eta f}$ and ${\rm prox}_{\eta g}$ for $f$ and $g$ proper lower semicontinuous convex functions, Algorithm 3 can be found, for instance, in [7, Cor. 27.4], [44, Alg. 1.8] and . Convergence of this algorithm (without an explicit estimate of the convergence rate) has been established in [44, Cor. 1.11] and [23, Cor. 5.2]. We also note that a similar relaxation of the Douglas–Rachford algorithm for lattice cone constraints has been proposed and analyzed in .

Whilst it is possible to analyze the damped Douglas–Rachford algorithm within the quasi-cyclic framework, we learn more by proving the following result directly.

Step 1 (A Fejér monotonicity type inequality for $x^{t}$): Let $x^{*}\in C\cap D$. We first show that

To see this, note that, for any closed and convex set $A$, ${\rm dist}^{2}(\cdot,A)$ is a differentiable convex function satisfying $\nabla({\rm dist}^{2})(x,A)=2(x-{\rm P}_{A}(x))$ which is $2$-Lipschitz. Using the convex subgradient inequality, we have

where the last equality follows from the last relation in (27). Now using (26), we see that

Summing these two equalities and multiplying by $\lambda_{t}$ yields

Substituting the last two equations into (5.43) gives

Step 2 (establishing a recurrence for ${\rm dist}^{2}(x^{t},{C\cap D})$): First note that

This shows that $y^{t+1}$ lies in the line segment between $x^{t}$ and its projection onto $C$. So, $P_{C}(y^{t+1})={\rm P}_{C}(x^{t})$ and hence,

the point $z^{t+1}$ lies in the line segment between $2y^{t+1}-x^{t}$ and its projection onto $D$. Thus $P_{D}(z^{t+1})={\rm P}_{D}(2y^{t+1}-x^{t})$ and so,

Now, using the non-expansiveness of ${\rm dist}(\cdot,D)$, we have

In particular, we see that the sequence $\{x^{t}\}$ is bounded and Fejér monotone with respect to $C\cap D$. Thence, letting $K$ be a bounded set containing $\{x^{t}\}$, by bounded Hölder regularity of $\{C,D\}$, there exists $\mu>0$ and $\gamma\in(0,1]$ such that

where $\theta=\frac{1}{\gamma}\in[1,\infty)$. So, Fact 2 implies that ${\rm P}_{C\cap D}(x^{t})\rightarrow\bar{x}$ for some $\bar{x}\in C\cap D$. Setting $x^{*}={\rm P}_{C\cap D}(x^{t})$ in (30) we therefore obtain

Now, the conclusion follows by applying Proposition 14 with $\theta=1/\gamma$.

Note that Theorem 5.42 only requires Hölder regularity of the underlying collection of constraint sets, rather than the damped DR operator explicitly. A careful examination of the proof of Theorem 5.42 shows that the inequality (5.43) does not hold for the basic DR algorithm (which would require setting $\eta=+\infty$).

In the case when $0\in{\rm sri}(C-D)$, where ${\rm sri}$ is the strong relative interior, then the Hölder regularity result holds with exponent $\gamma=1$ (see ). The preceding proposition therefore implies that the damped Douglas–Rachford method converges linearly in the case where $0\in{\rm sri}(C-D)$.

where $\gamma=[\min\left\{\frac{(2d-1)^{n}+1}{2},\,B(n-1)d^{n}\right\}]^{-1}$ and $\beta(n-1)$, is the central binomial coefficient with respect to $n-1$ which is given by $\binom{n-1}{[(n-1)/2]}$.

By Lemma 11 with $\theta=1$, we see that for any compact set $K$, there exists $c>0$ such that for all $x\in K$,

where $\gamma=[\min\left\{\frac{(2d-1)^{n}+1}{2},\,B(n-1)d^{n}\right\}]^{-1}$. Note that $\gamma=1$ if $d=1$; while $\gamma\in(0,1)$ if $d>1$. The conclusion now follows from Theorem 5.42.

Two Examples

In this section we fully examine two concrete problems which illustrate the difficulty of establishing optimal rates. In addition to illustrating our approach, these examples also give some further insight into the sharpness of our derived qualitative behavior. We begin with an example consisting of two sets having an intersection which is bounded Hölder regular but not bounded linearly regular. In the special case where $n=1$, it has previously been examined in detail as part of [12, Ex. 5.4].

Firstly, on the route to showing bounded Hölder regularity, it can be verified (see also [9, Cor. 3.9]) that

where the equality follows from (31). This shows that, for all $(x,r)\in K$,

where the equality follows from (31). Therefore, there exists $\mu>0$ such that, for all $(x,r)\in K$,

We note that, for $n=1$, it was shown in (by examining the generated DR sequence directly) that the sequence $x^{t}$ converges to zero at the order $t^{-\frac{1}{d-2}}$ where $d>2$. Note that $r^{t}=\|x^{t}\|^{d}$. It follows that the actual convergence rate for $(x^{t},r^{t})$ for this example is $t^{-\frac{1}{d-2}}$ in the case $n=1$. Thus, our convergence rate estimate for this example is not tight in the case $n=1$. On the other hand, as noted in , their analysis is largely limited to the $2$-dimensional case and it is not clear how it can be extended to the higher dimensional setting.

We now examine an even more concrete example involving a subspace and a lower level set of a convex quadratic function in the plane.

Setting $\alpha:=1/\max\{1,\|x-(1,0)\|\}$, a direct computation shows that

Now, fix an arbitrary compact set $K$ and let $M>0$ such that $\|x\|\leq M$ for all $x\in K$. For all $x\in K$, there exists $m\in(0,1]$ such that $\alpha=1/\max\{1,\|x-(1,0)\|\}\in[m,1]$ for all $x\in K$. By shrinking $m$ if necessary, we may assume that

We now distinguish two cases depending on $\alpha$.

Case 1 $(\alpha=1)$: In this case, we have

In particular, this shows that $x_{1}\geq 0$. Now (33) gives

Case 2 $(\alpha<1)$: Fix $x\in K$. In this case, we show that

To do this, we further divide the discussion into two subcases depending on the sign of $x_{1}$.

Subcase I $(x_{1}>0)$: In this case, ${\rm dist}(x,{\rm Fix}\,T_{C,D})=\|x\|$. Note that

where the last inequality follows by the fact that $\alpha\geq m$. So, the elementary inequality $\sqrt{a^{2}+b^{2}}\geq(a+b)/2$ for all $a,b\geq 0$ implies that

From the definition of $\alpha$, we see that

As $m\leq\alpha<1$, $\|x-(1,0)\|\leq\frac{1}{m}$. So,

The claimed equation (35) now follows from (34).

Subcase II $(x_{1}\leq 0)$: In this case, ${\rm dist}(x,{\rm Fix}\,T_{C,D})=|x_{2}|$ and

where the last inequality follows from $x_{1}\leq 0$. Thus, (35) also follows in this subcase.

That is, $T_{C,D}$ is bounded Hölder regular with exponent $\gamma=1/3$. Therefore, for this example, Corollary 4.36 implies that the DR algorithm generated a sequence $\{x^{t}\}$ which converges to $\bar{x}\in{\rm Fix}T_{C,D}=(-\infty,0]\times\{0\}$ at least with a sublinear convergence rate of $O(\frac{1}{\sqrt{t}})$. Let $x^{t}=(x_{1}^{t},x_{2}^{t})$ and $\bar{x}=(\bar{x}_{1},0)$ with $\bar{x}_{1}\leq 0$. As $x^{t+1}=T_{C,D}(x^{t})$, by passing to the limit in (32), we have $\bar{x}_{1}=\bar{\alpha}-1-\bar{\alpha}\bar{x}_{1}$ where $\bar{\alpha}=1/\max\{1,|\bar{x}_{1}-1|\}$. If $\bar{x}_{1}<0$, then $|\bar{x}_{1}-1|>1$, and so, $\bar{\alpha}=1/(1-\bar{x}_{1})$. This implies that $\bar{x}_{1}=(\bar{\alpha}-1)/(1+\bar{\alpha})=\bar{x}_{1}/(2-\bar{x}_{1})$ and hence, $\bar{x}_{1}=1$ or $\bar{x}_{1}=0$ which is impossible. This shows that $\bar{x}_{1}=0$, and so, $\{x^{t}\}$ converges to $\bar{x}=(0,0)$ at worst in a sublinear convergence rate $O(\frac{1}{\sqrt{t}})$ regardless the choice of the initial points.

We now illustrate the sublinear convergence rate by numerical simulation. To do this, we first randomly generated an initial point in $^{2}$. We then ran the DR algorithm for this example (starting with the corresponding random starting point) whilst tracking the value of $\sqrt{t}\,\|x^{t}-\bar{x}\|$ and $\frac{-{\log(\|x^{t}-\bar{x}\|)}}{\log(t)}$. The experiment was repeated 200 times, and the results plotted in Figure 1.

From the first graph, we see that the value of $\sqrt{t}\,\|x^{t}-\bar{x}\|$ quickly decreases with increasing $t$. This supports the result that $x^{t}$ converges at least in the order of $O(1/\sqrt{t})$. From the second graph, the value of $\frac{-{\log(\|x^{t}-\bar{x}\|)}}{\log(t)}$ appears to approach $1/2$. This suggests that the actual sublinear convergence rate for this example is $O(1/\sqrt{t})$, regardless of the choice of the initial point.

Furthermore, the following example shows that, whenever the initial point is chosen in the region specified below, the sequence in Example 6.50 converges with an exact order $O(1/\sqrt{t})$ and thus supports the conjectured rate of convergence.

Since $w_{t}\to 0$, for sufficiently large $t$, we have

Taking square roots and inverting both sides we obtain

Since \sqrt{(1-u_{t})^{2}+v_{t}^{2}}\big{(}(1-u_{t})+\sqrt{(1-u_{t})^{2}+v_{t}^{2}}\big{)}\rightarrow 2 as $t\rightarrow\infty$, whenever $t$ is sufficiently large we have

Noting that $\frac{v_{t+1}}{v_{t}}=\frac{1}{\sqrt{(1-u_{t})^{2}+v_{t}^{2}}}\to 1$ as $t\to\infty$ and $v_{t}>0$, we therefore deduce that $v_{t-1}<2v_{t}$ for all sufficiently large $t$. Combined with (38), this yields

As before, we set $w_{t}:=v_{t}^{2}$. Since $w_{t}\to 0$ and $(1+\frac{9}{2}w_{t})^{2}(1-10w_{t})=1-w_{t}-\frac{279}{4}w_{t}^{2}-\frac{405}{2}w_{t}^{3}<1$, we deduce

This shows that $\|(u_{t},v_{t})\|\geq\frac{1}{10}\,\frac{1}{\sqrt{t}}$. Altogether, we have proven that $(u_{t},v_{t})\rightarrow(0,0)$ with an exact sublinear convergence order $O(1/\sqrt{t})$.

Conclusions

In this paper, using a Hölder regularity assumption, sublinear and linear convergence of fixed point iterations described by averaged nonexpansive operators has been established. The framework was then specialized to various fixed point algorithms including Krasnoselskii–Mann iterations, the cyclic projection algorithm, and the Douglas–Rachford feasibility algorithm along with some variants. In the case where the underlying sets are convex semi-algebraic, in a finite dimensional space, the results apply without any further regularity assumptions.

In particular, for our damped Douglas–Rachford algorithm, an explicit estimate for the sublinear convergence rate has been provided in terms of the dimension and the maximum degree of the polynomials which define the convex sets. We emphasize that, unlike the for damped Douglas–Rachford algorithm, we were not able to provide an explicit estimate of the sublinear convergence rate for the classical Douglas–Rachford algorithm when the two convex sets are described by convex polynomials. Our approach relies on the Łojasiewicz’s inequality which gives no quantitative information regarding the Hölder exponent. Providing explicit estimates is left as an open question for future research.

Another area for future research involves characterization of the convergence rate in the absence of Hölder regularity properties. For instance, it is known that the alternating projection method can exhibit arbitrarily slow convergence when applied to two subspaces in infinite dimensional spaces without closed sum . As shown in [20, Cor. 3.1], if only two sets are involved and the initial point is chosen in a specific way, the cyclic Douglas–Rachford method can coincide with the alternating projection method, and so, it may exhibit arbitrarily slow convergence. On the other hand, it was shown in Proposition 4.34 that the basic/cyclic Douglas–Rachford method enjoys a sublinear convergence rate if the underlying sets are convex semi-algebraic sets in finite dimensional spaces. It would be interesting to see whether an arbitrarily slow convergence can happen for these two methods for general closed and convex sets in finite dimensional spaces.

Finally, the current definition of basic semi-algebraic convex sets only applies to finite dimensional spaces. It would interesting to see if a suitable extension of the notion can be profitably used in infinite dimensional spaces using, for instance, polynomials as defined in .

JMB is supported, in part, by the Australian Research Council. GL is supported, in part, by the Australian Research Council. MKT is supported by Deutsche Forschungsgemeinschaft Research Training Grant 2088. The work was partially performed during his candidature at the University of Newcastle where he was supported by an Australian Postgraduate Award. The authors wish to thank Neal Hermer, Victor Isaac Kolobov, Simeon Reich, Rafał Zalas and the three anonymous referees for their insightful comments.

References