Compositions and Convex Combinations of Averaged Nonexpansive Operators

Introduction

Since their introduction in , averaged nonexpansive operators have proved to be very useful in the analysis and the numerical solution of problems arising in nonlinear analysis and its applications; see, e.g., .

As discussed in , averaged operators are stable under compositions and convex combinations and such operations form basic building blocks in various composite fixed point algorithms. The averagedness constants resulting from such operations determine the range of the step sizes and other parameters in such algorithms. It is therefore important that they be tight since these parameters have a significant impact on the speed of convergence.

In this paper, we discuss averagedness constants for compositions and convex combinations of averaged operators and construct novel fixed point algorithms based on these constants. In particular, we obtain a new version of the forward-backward algorithm with an extended relaxation range and iteration-dependent step sizes.

Compositions and convex combinations of averaged operators

We first recall some characterizations of averaged operators (see [11, Lemma 2.1] or [6, Proposition 4.25]).

Let $D$ be a nonempty subset of ${\mathcal{H}}$, let $T\colon D\to{\mathcal{H}}$ be nonexpansive, and let $\alpha\in\left]0,1\right[$. Then the following are equivalent:

$(\forall x\in D)(\forall y\in D)$ $\|Tx-Ty\|^{2}+(1-2\alpha)\|x-y\|^{2}\leqslant 2(1-\alpha){\left\langle{{x-y}\mid{Tx-Ty}}\right\rangle}$.

The next result concerns the averagedness of a convex combination of averaged operators.

Let $D$ be a nonempty subset of ${\mathcal{H}}$, let $(T_{i})_{i\in I}$ be a finite family of nonexpansive operators from $D$ to ${\mathcal{H}}$, let $(\alpha_{i})_{i\in I}$ be a family in $\left]0,1\right[$, and let $(\omega_{i})_{i\in I}$ be a family in $]0,1]$ such that $\sum_{i\in I}\omega_{i}=1$. Suppose that, for every $i\in I$, $T_{i}$ is $\alpha_{i}$-averaged, and set $T=\sum_{i\in I}\omega_{i}T_{i}$ and $\alpha=\sum_{i\in I}\omega_{i}\alpha_{i}$. Then $T$ is $\alpha$-averaged.

We conclude that $T$ is $\alpha$-averaged.

In view of [8, Corollary 2.2.17], Proposition 2.2 is equivalent to [8, Theorem 2.2.35], and it improves the averagedness constant of [11, Lemma 2.2(ii)] which was $\alpha=\text{\rm max}_{i\in I}\alpha_{i}$. In the case of two operators, Proposition 2.2 can be found in [16, Theorem 3(a)].

Next, we turn our attention to compositions of averaged operators, starting with the following result, which was obtained in [16, Theorem 3(b)] with a different proof.

Let $D$ be a nonempty subset of ${\mathcal{H}}$, let $(\alpha_{1},\alpha_{2})\in\left]0,1\right[^{2}$, let $T_{1}\colon D\to D$ be $\alpha_{1}$-averaged, and let $T_{2}\colon D\to D$ be $\alpha_{2}$-averaged. Set

Then $\alpha\in\left]0,1\right[$ and $T$ is $\alpha$-averaged.

Proof. Since $\alpha_{1}(1-\alpha_{2})<(1-\alpha_{2})$, we have $\alpha_{1}+\alpha_{2}<1+\alpha_{1}\alpha_{2}$ and, therefore, $\alpha\in\left]0,1\right[$. Now let $x\in D$, let $y\in D$, and set

Moreover, by [6, Corollary 2.14], we have

In view of Proposition 2.1, we conclude that $T$ is $\alpha$-averaged.

In [8, Theorem 2.2.37], the averagedness constant of (2.2) was written as

By induction, it leads to the following result for the composition of $m$ averaged operators, which was obtained in (combine [8, Theorem 2.2.42] and [8, Corollary 2.2.17]).

Let $D$ be a nonempty subset of ${\mathcal{H}}$, let $m\geqslant 2$ be an integer, and set

For every $i\in\{1,\ldots,m\}$, let $\alpha_{i}\in\left]0,1\right[$ and let $T_{i}\colon D\to D$ be $\alpha_{i}$-averaged. Set

Proof. We proceed by induction on $k\in\{2,\ldots,m\}$. To this end, let us set $(\forall k\in\{2,\ldots,m\})$ $\beta_{k}=[1+[\sum_{i=1}^{k}\alpha_{i}/(1-\alpha_{i})]^{-1}]^{-1}$. By Proposition 2.4 and (2.7), the claim is true for $k=2$. Now assume that, for some $k\in\{2,\ldots,m-1\}$, $T_{1}\cdots T_{k}$ is $\beta_{k}$-averaged. Then we deduce from Proposition 2.4 and (2.7) that the averagedness constant of $(T_{1}\cdots T_{k})T_{k+1}$ is

The following result provides alternative expressions for the averagedness constant $\alpha$ of (2.9).

Let $m\geqslant 2$ be an integer, let $\phi$ be as in (2.8), let $(\alpha_{i})_{1\leqslant i\leqslant m}\in\left]0,1\right[^{m}$, and let $(\sigma_{j})_{1\leqslant j\leqslant m}$ the elementary symmetric polynomials in the variables $(\alpha_{i})_{1\leqslant i\leqslant m}$, i.e.,

$\phi(\alpha_{1},\ldots,\alpha_{m})=\big[{\sum_{l=1}^{{+\infty}}\sum_{i=1}^{m}\alpha_{i}^{l}}\big]\big/\big[{1+\sum_{l=1}^{{+\infty}}\sum_{i=1}^{m}\alpha_{i}^{l}}\big]$.

$\phi(\alpha_{1},\ldots,\alpha_{m})=\big[{\sum_{j=1}^{m}(-1)^{j-1}j\sigma_{j}}\big]\big/\big[{1+\sum_{j=2}^{m}(-1)^{j-1}(j-1)\sigma_{j}}\big]$.

$\phi(\alpha_{1},\ldots,\alpha_{m})>\text{\rm max}_{1\leqslant i\leqslant m}\alpha_{i}$.

(ii): Using the inductive argument of the proof of Proposition 2.5 and (2.7), we observe that $\phi(\alpha_{1},\ldots,\alpha_{m})$ can be defined via the recursion

We have $(\forall j\in\{1,\ldots,m\})$ $\sigma_{j}=s_{j}(m)$. Furthermore,

Let us show by induction that, for every $k\in\{2,\ldots,m\}$,

Since $s_{1}(2)=\alpha_{1}+\alpha_{2}$ and $s_{2}(2)=\alpha_{1}\alpha_{2}$, (2.13) yields

This establishes (2.16) for $k=2$. Now suppose that (2.16) holds for some $k\in\{2,\ldots,m-1\}$. We derive from (2.14) and (2.15) that

This shows that (2.16) holds for every $k\in\{2,\dots,m\}$.

(iii): We need to consider only the case when $m=2$ since the general case will follow from (2.13) by induction. We derive from (2.13) that

Since $\beta_{2}-\alpha_{1}=\alpha_{2}(1-\alpha_{1})^{2}/(1-\alpha_{1}\alpha_{2})>0$ and $\beta_{2}-\alpha_{2}=\alpha_{1}(1-\alpha_{2})^{2}/(1-\alpha_{1}\alpha_{2})>0$, we have $\beta_{2}>\text{max}\{\alpha_{1},\alpha_{2}\}>0$.

Let us compare the averagedness constant of Proposition 2.5 with alternative ones. Set

and let $(\alpha_{i})_{1\leqslant i\leqslant m}\in\left]0,1\right[^{m}$.

The averagedness constant of Proposition 2.5 is sharper than that of [11, Lemma 2.2(iii)], namely

${\phi}(\alpha_{1},\ldots,\alpha_{m})=\widetilde{\phi}(\alpha_{1},\ldots,\alpha_{m})$ if $\alpha_{1}=\cdots=\alpha_{m}$ and, in particular, if all the operators are firmly nonexpansive, i.e., $\alpha_{1}=\cdots=\alpha_{m}=1/2$.

If $m=2$, the averagedness constant of Proposition 2.5 is strictly sharper than that of [19, Lemma 3.2], namely (see also [8, Remark 2.2.38])

In addition, $\phi(\alpha_{1},\alpha_{1})=\widetilde{\phi}(\alpha_{1},\alpha_{1})<\widehat{\phi}(\alpha_{1},\alpha_{1})$ while, for $\alpha_{1}={3}/{4}$ and $\alpha_{2}={1}/{8}$, $\widehat{\phi}(\alpha_{1},\alpha_{2})={25}/{32}<{6}/{7}=\widetilde{\phi}(\alpha_{1},\alpha_{2})$, which shows that $\widetilde{\phi}$ and $\widehat{\phi}$ cannot be compared in general.

Proof. (i): Combine [8, Theorem 2.2.42], and [8, Corollary 2.2.17].

(ii): Set $\beta_{1}=\delta_{1}=\alpha_{1}$ and

We have $\beta_{1}=\delta_{1}=\alpha_{1}$. Next, suppose that, for some $k\in\{1,\ldots,m-1\}$, $\beta_{k}=\delta_{k}$. Then $\alpha_{k+1}=\alpha_{1}$, while (2.10) and (2.26) yield

(iii): This inequality was already obtained in [8, Remark 2.2.38]. It follows from the fact that

The remaining assertions are easily verified.

Algorithms

We present applications of the bounds discussed in Section 2 to fixed point algorithms. Henceforth, we denote the set of fixed points of an operator $T\colon{\mathcal{H}}\to{\mathcal{H}}$ by $\text{\rm Fix}\,T$.

As a direct application of Proposition 2.2 and Proposition 2.5, we first consider so-called “string-averaging” iterations, which involve a mix of compositions and convex combinations of operators. In the case of projection operators, such iterations go back to .

Then $T$ is $\alpha$-averaged and $\text{\rm Fix}\,T=\bigcap_{i\in I}\text{\rm Fix}\,T_{i}$.

Proof. (i): The $\alpha$-averagedness of $T$ follows from Propositions 2.2 and 2.5. The remaining assertions follow from [6, Proposition 4.34 and Corollary 4.37].

(ii): This follows from (i) and [6, Proposition 5.15(iii)].

Proposition 3.1 improves upon [6, Corollary 5.18], where the averagedness constant $\alpha$ of (3.2) was replaced by

The subsequent applications require the following technical fact.

Next, we introduce a general iteration process for finding a common fixed point of a countable family of averaged operators which allows for approximate computations of the operator values.

Then $\text{\rm Fix}\,R_{n}=\text{\rm Fix}\,T_{n}$ and, by Proposition 2.1, $R_{n}$ is nonexpansive. Furthermore, (3.5) can be written as

Now set $z_{n}=x_{n}+\mu_{n}(R_{n}x_{n}-x_{n})$. Since $x\in\text{\rm Fix}\,R_{n}$ and $R_{n}$ is nonexpansive, we have

Moreover, using (3.11), (3), and [6, Corollary 2.14], we can write

Thus, (3.6) follows from (3.8) and (3.14), and (3.15) provides (3.7).

(ii): This follows from (3.7), (3.13), and Lemma 3.3.

(iii): The weak convergence statement follows from (3.13), (3.16), and [10, Theorem 3.8], while the strong convergence statement follows from [10, Proposition 3.10].

The main result of this section is the following.

and therefore $\lambda_{n}\in\left]0,1/\alpha_{n}\right[$, as required in Proposition 3.4.

(i): Using the nonexpansiveness of the operators $(T_{i,n})_{1\leqslant i\leqslant m}$, we derive from (3.22) that

Hence, we deduce from Proposition 3.4(i) that

(ii): We derive from Proposition 2.1 that

Thus, Proposition 3.4(i), (3.20), and [6, Corollary 2.14] yield

On the one hand, it follows from (3.26), (3.27), and (3.28) that

On the other hand, combining (3) and (3), we obtain

(iii)–(iv): These follow from their counterparts in Proposition 3.4.

Application to forward-backward splitting

The forward-backward algorithm is one of the most versatile and powerful algorithm for finding a zero of the sum of two maximally monotone operators (see and the references therein for historical background and recent developments). In , the first author showed that the theory of averaged nonexpansive operators provided a convenient setting for analyzing this algorithm. In this section, we exploit the results of Sections 2 and 3 to further extend this analysis and obtain a new version of the forward-backward algorithm with an extended relaxation range.

Let us recall a few facts about monotone set-valued operators and convex analysis . Let $A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ be a set-valued operator. The domain, the graph, and the set of zeros of $A$ are respectively defined by $\text{\rm dom}\,A=\big\{{x\in{\mathcal{H}}}~\big|~{Ax\neq{\varnothing}}\big\}$, $\text{\rm gra}A=\big\{{(x,u)\in{\mathcal{H}}\times{\mathcal{H}}}~\big|~{u\in Ax}\big\}$, and $\text{\rm zer}\,A=\big\{{x\in{\mathcal{H}}}~\big|~{0\in Ax}\big\}$. The inverse of $A$ is $A^{-1}\colon{\mathcal{H}}\mapsto 2^{{\mathcal{H}}}\colon u\mapsto\big\{{x\in{\mathcal{H}}}~\big|~{u\in Ax}\big\}$, and the resolvent of $A$ is

This operator is firmly nonexpansive if $A$ is monotone, i.e.,

and $\text{\rm dom}\,J_{A}={\mathcal{H}}$ if, furthermore, $A$ is maximally monotone, i.e., there exists no monotone operator $B\colon{\mathcal{H}}\to 2^{\mathcal{H}}$ such that $\text{\rm gra}A\subset\text{\rm gra}B$ and $A\neq B$. We denote by $\Gamma_{0}({\mathcal{H}})$ the class of proper lower semicontinuous convex functions $f\colon{\mathcal{H}}\to\left]-\infty,+\infty\right]$. Let $f\in\Gamma_{0}({\mathcal{H}})$. For every $x\in{\mathcal{H}}$, $f+\|x-\cdot\|^{2}/2$ possesses a unique minimizer, which is denoted by $\text{\rm prox}_{f}x$. We have

We start with a specialization of Theorem 3.5 to $m=2$.

(i)–(ii): Let $x\in S$. We derive from Theorem 3.5(ii) with $m=2$ that

However, it follows from the assumptions that

Combining (4.7) and (4.8) yields the claims.

(iv)–(v): These follow from Theorem 3.5(iii)–(iv).

Here are some examples of demiregular monotone operators.

[1, Proposition 2.4] Let $A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ be monotone and suppose that $x\in\text{\rm dom}\,A$. Then $A$ is demiregular at $x$ in each of the following cases:

$A$ is uniformly monotone at $x$, i.e., there exists an increasing function $\theta\colon\left[0,+\infty\right[\to\left[0,+\infty\right]$ that vanishes only at $0$ such that $(\forall u\in Ax)(\forall(y,v)\in\text{\rm gra}A)$ ${\left\langle{{x-y}\mid{u-v}}\right\rangle}\geqslant\theta(\|x-y\|)$.

$J_{A}$ is compact, i.e., for every bounded set $C\subset{\mathcal{H}}$, the closure of $J_{A}(C)$ is compact. In particular, $\text{\rm dom}\,A$ is boundedly relatively compact, i.e., the intersection of its closure with every closed ball is compact.

$A\colon{\mathcal{H}}\to{\mathcal{H}}$ is single-valued with a single-valued continuous inverse.

$A=\partial f$, where $f\in\Gamma_{0}({\mathcal{H}})$ is uniformly convex at $x$, i.e., there exists an increasing function $\theta\colon\left[0,+\infty\right[\to\left[0,+\infty\right]$ that vanishes only at $0$ such that

Our extended forward-backward splitting scheme can now be presented.

Let $\beta\in\left]0,+\infty\right[$, let $\varepsilon\in\left]0,\min\{1/2,\beta\}\right[$, let $x_{0}\in{\mathcal{H}}$, let $A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ be maximally monotone, and let $B\colon{\mathcal{H}}\to{\mathcal{H}}$ be $\beta$-cocoercive, i.e.,

Suppose that one of the following is satisfied:

$A$ is demiregular at every point in $\text{\rm zer}\,(A+B)$.

$B$ is demiregular at every point in $\text{\rm zer}\,(A+B)$.

Proof. We are going to establish the results as an application of Corollary 4.1. Set

in conformity with (4.4). In turn, Proposition 2.6(iii) yields

On the other hand, [6, Proposition 25.1(iv)] yields

Altogether, $S=\text{\rm zer}\,(A+B)\neq{\varnothing}$, (4.6) is satisfied, and (4.13) is an instance of (4.5).

(i): This is a consequence of Corollary 4.1(iii) and (4.14).

We derive from (i) that $y_{n}-x_{n}\to 0$, hence $y_{k_{n}}\>\rightharpoonup\>y$. Now let $x\in\text{\rm zer}\,(A+B)$. Then (ii) implies that $Bx_{n}\to Bx$, hence $u_{n}\to-Bx$. However, since (4.11) implies that $B$ is maximally monotone [6, Example 20.28], it follows from the properties $x_{k_{n}}\>\rightharpoonup\>y$ and $Bx_{k_{n}}\to Bx$ that $By=Bx$ [6, Proposition 20.33(ii)]. Thus, $y_{k_{n}}\>\rightharpoonup\>y$ and $u_{k_{n}}\to-By$, and it therefore follows from (4.22) and [6, Proposition 20.33(ii)] that $-By\in Ay$, i.e., $y\in\text{\rm zer}\,(A+B)$.

(iv): By (iii), there exists $x\in\text{\rm zer}\,(A+B)$ such that $x_{n}\>\rightharpoonup\>x$. In addition, we derive from (4.21), (i), and (ii) that $y_{n}\>\rightharpoonup\>x$ and $u_{n}\to-B{x}\in A{x}$.

(iv)(a): Suppose that $A$ is demiregular at $x$. Then (4.22) yields $y_{n}\to{x}$ and (i) implies that $x_{n}\to{x}$.

(iv)(b): Suppose that $B$ is demiregular at $x$. Since $x_{n}\>\rightharpoonup\>x$ and $Bx_{n}\to Bx$ by (ii), we have $x_{n}\to x$.

(iv)(c): This follows from (iii) and Corollary 4.1(iv).

Proof. Using the same arguments as in [6, Section 27.3], one shows that this is the specialization of Proposition 4.4 to the case when $A=\partial f$ and $B=\nabla g$.

References