An Algorithm Based on Unions of Nonexpansive Mappings in Metric Spaces

Abstract

In this paper, we obtain two extensions of a recent result of Tam, which was proved for iterates of set-valued paracontracting operators in a finite-dimensional space. Our results are obtained for operators in an arbitrary metric space. In the first result, we study exact iterates of the set-valued mapping, while in the second one, we deal with its inexact iterates, taking computational errors into account. In a particular case of a Banach space, if all the operators are symmetric, then the set of all limit points of iterates is symmetric too.

1. Introduction

For more than sixty years now, there has been a lot of research activity focused on the study of the fixed-point theory of nonexpansive operators [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]. The starting point of this study is Banach’s celebrated theorem [21], which concerns the existence of a unique fixed point for a strict contraction. It also concerns the convergence of (inexact) iterates of a nonexpansive mapping to one of its fixed points. Since that seminal result, many developments have taken place in this field, including, in particular, studies of feasibility, common fixed-point problems, and variational inequalities, which find important applications in mathematical analysis, optimization theory, and in engineering, medical, and natural sciences [19,20,22,23,24,25,26]. In particular, in [27], it was considered a framework for the analysis of iterative algorithms, which can be described in terms of a structured set-valued operator. Namely, at every point in the ambient space, it is assumed that the value of the operator can be expressed as a finite union of values of single-valued paracontracting operators. For such algorithms, a convergence result was proved, which generalizes a result obtained in [28].

In this paper, we obtain two extensions of the result of Tam (2018) which was proved for iterates of set-valued paracontracting operators in a finite-dimensional space. Our results are obtained for operators in an arbitrary metric space. In the first result, we study exact iterates of the set-valued mapping, while in the second one, we deal with its inexact iterates, taking computational errors into account. It should be mentioned that in a particular case of a Banach space, if all the operators are symmetric, then the set of all limit points of iterates is symmetric too.

2. Preliminaries

Suppose that $(X,\rho )$ is a metric space and that $C\subset X$ is its nonempty, closed set. For every point $x\in X$ and every positive number r, define

$$B(x,r)=\{y\in X:\rho (x,y)\le r\}$$

and for every point $x\in C$ and every nonempty set $B\subset C$, put

$$\rho (x,B)=\sup \left\{\rho \right(x,y):y\in B\}.$$

For every operator $S:C\to C$ set

$$\mathrm{Fix}\left(S\right)=\{x\in C:S(x)=x\}.$$

Suppose that m is a natural number, $T_i:C\to C$, $i=1,\cdots ,m$, $\overline{c}\in (0,1]$ and that for every natural number $i\in \{1,\cdots ,m\}$, every point $z\in \mathrm{Fix}\left(T_i\right)$ and every point $y\in C$, we have

$$\rho {(z,y)}^2-\rho {(z,T_i\left(y\right))}^2\ge \overline{c}\rho {(y,T_i\left(y\right))}^2.$$

(1)

Note that (1) holds for many nonlinear mappings [19,20] including projections on closed, convex sets in a Hilbert space.

Assume that for every point $x\in X$, a nonempty set

$$\varphi \left(x\right)\subset \{1,\cdots ,m\}$$

(2)

is given. In other words,

$$\varphi :X\to 2^{\{1,\cdots ,m\}}\backslash \{\varnothing \}.$$

Define

$$T\left(x\right)=\{T_i\left(x\right):i\in \varphi \left(x\right)\}$$

(3)

for each $x\in C$,

$$\overline{F}\left(T\right)=\{z\in C:T_i\left(z\right)=z,i=1,\cdots ,m\}$$

(4)

and

$$F\left(T\right)=\{x\in C:x\in T(x\left)\right\}.$$

(5)

Assume that

$$\overline{F}\left(T\right)\ne \varnothing .$$

Fix

$$\theta \in C.$$

By (4) and (5),

$$\overline{F}\left(T\right)\subset F\left(T\right).$$

Use Card$\left(D\right)$ to denote the cardinality of a set D. For each $z\in R^1$ set

$$\lfloor z\rfloor =\inf \{i:i\mathrm{is} \mathrm{an} \mathrm{integer} \mathrm{and} i\le z\}.$$

3. The First Result

In this section, we prove the following result, which shows that almost all iterates of our set-valued mappings are approximated solutions of the corresponding fixed-point problem. Many results of this type are collected in [19,20].

Theorem 1.

Assume that $M>0$, $ϵ\in (0,1]$,

$$\overline{F}\left(T\right)\cap B(\theta ,M)\ne \varnothing$$

(6)

and that

$$Q=\lfloor 4M^2{\overline{c}}^{-1}{ϵ}^{-2}\rfloor .$$

(7)

Then, for each sequence ${\left\{x_i\right\}}_{i=0}^{\infty }\subset C$, which satisfies

$$\rho (\theta ,x_0)\le M$$

(8)

and

$$x_{i+1}\in T\left(x_i\right),i=0,1,\cdots$$

(9)

the inequality

$$Card\left(\{i\in \{0,1,\cdots ,\}:\min \{\rho (x_i,T_j\left(x_i\right)):j\in \varphi \left(x_i\right)\}\ge ϵ\}\right)\le Q$$

holds.

Proof. 

According to (6), there exists

$$z\in \overline{F}\left(T\right)\cap B(\theta ,M).$$

(10)

In view of (4) and (10),

$$z=T_i\left(z\right),i=1,\cdots ,m.$$

(11)

Assume that ${\left\{x_i\right\}}_{i=0}^{\infty }\subset C$ and (8) and (9) hold. According to Equations (2), (3) and (9), for every nonnegative integer i, there is a natural number

$$j\left(i\right)\in \varphi \left(x_i\right),$$

(12)

such that

$$x_{i+1}=T_{j\left(i\right)}\left(x_i\right).$$

(13)

Let i be a nonnegative integer. In view of Equations (1) and (11)–(13),

$$\begin{array}{ll}\rho {(z,x_i)}^2& \ge \rho {(z,T_{j\left(i\right)}\left(x_i\right))}^2+\overline{c}\rho {(x_i,T_{j\left(i\right)}\left(x_i\right))}^2\\ & =\rho {(z,x_{i+1})}^2+\overline{c}\rho {(x_i,x_{i+1})}^2.\end{array}$$

(14)

Let q be a natural number. Equations (8), (10) and (14) imply that that

$$4M^2\ge {(M+\rho (z,\theta ))}^2\ge {(\rho (z,\theta )+\rho (\theta ,x_0))}^2$$

$$\ge \rho {(z,z_0)}^2\ge \rho {(z,x_0)}^2-\rho {(z,x_q)}^2$$

$$=\sum _{i=0}^{q-1}(\rho {(z,x_i)}^2-\rho {(z,x_{i+1})}^2)$$

$$\ge \overline{c}\sum _{i=0}^{q-1}\rho {(x_i,x_{i+1})}^2\ge \overline{c}\mathrm{Card}\left(\{i\in \{0,\cdots ,q-1\}:\rho (x_i,x_{i+1})\ge ϵ\}\right){ϵ}^2$$

and

$$\mathrm{Card}\left(\{i\in \{0,\cdots ,q-1\}:\rho (x_i,x_{i+1})\ge ϵ\}\right)\le 4M^2{\overline{c}}^{-1}{ϵ}^{-2}.$$

(15)

By (7) and (15),

$$\mathrm{Card}\left(\{i\in \{0,1,\cdots \}:\rho (x_i,x_{i+1})\ge ϵ\}\right)\le \lfloor 4M^2{\overline{c}}^{-1}{ϵ}^{-2}\rfloor =Q.$$

Theorem 1 is proved. □

4. The Second Result

In our second main result, taking into account computational errors, we show that an approximate fixed point is obtained after a certain number of iterates, which depends on a computational error. Many results of this type are collected in [19,20].

Theorem 2.

Assume that $M>0$, $ϵ\in (0,1)$,

$$\overline{F}\left(T\right)\cap B(\theta ,M)\ne \varnothing ,$$

(16)

an integer Q satisfies

$$Q>8M^2{\overline{c}}^{-1}{ϵ}^{-2},$$

(17)

$\delta \in (0,1)$ satisfies

$$\delta \le {(4M+1)}^{-1}{ϵ}^2\overline{c}/2,$$

(18)

a sequence ${\left\{x_i\right\}}_{i=0}^{\infty }\subset C$ satisfies

$$\rho (\theta ,x_0)\le M$$

(19)

and that for every nonnegative integer i,

$$B(x_{i+1},\delta )\cap T\left(x_i\right)\ne \varnothing .$$

(20)

Then, there exists a nonnegative integer $j\le Q-1$, such that

$$B(x_j,ϵ)\cap T\left(x_j\right)\ne \varnothing .$$

(21)

Proof. 

According to (16), there exists

$$z\in \overline{F}\left(T\right)\cap B(\theta ,M).$$

(22)

Assume that for every nonnegative integer $j\le Q-1$, Equation (21) does not hold. Then, for each nonnegative integer $i\le Q-1$, we have

$$B(x_i,ϵ)\cap T\left(x_i\right)=\varnothing .$$

(23)

Let

$$i\in \{0,\cdots ,Q-1\}.$$

(24)

In view of (20) and (24), there exists

$${\widehat{x}}_{i+1}\in T\left(x_i\right)$$

(25)

such that

$$\rho (x_{i+1},{\widehat{x}}_{i+1})\le \delta .$$

(26)

It follows from (1), (3), (4), (22) and (25) that

$$\rho {(z,x_i)}^2\ge \rho {(z,{\widehat{x}}_{i+1})}^2+\overline{c}\rho {(x_i,{\widehat{x}}_{i+1})}^2.$$

(27)

According to (23) and (25),

$$\rho (x_i,{\widehat{x}}_{i+1})>ϵ.$$

(28)

Equations (27) and (28) imply that

$$\rho {(z,x_i)}^2\ge \rho {(z,{\widehat{x}}_{i+1})}^2+{ϵ}^2\overline{c}.$$

(29)

According to (26),

$$\rho (z,{\widehat{x}}_{i+1})\ge \rho (z,x_{i+1})-\rho ({\widehat{x}}_{i+1},x_{i+1})\ge \rho (z,x_{i+1})-\delta .$$

(30)

In view of (30),

$$\begin{array}{c}\rho {(z,x_{i+1})}^2\le {(\rho (z,{\widehat{x}}_{i+1})+\delta )}^2\\ ={\delta }^2+\rho {(z,{\widehat{x}}_{i+1})}^2+2\delta \rho (z,{\widehat{x}}_{i+1}).\end{array}$$

(31)

Equations (29) and (31) imply that

$$\begin{array}{ll}\rho {(z,x_i)}^2& \ge \rho {(z,x_{i+1})}^2-{\delta }^2-2\delta \rho (z,{\widehat{x}}_{i+1})+\overline{c}{ϵ}^2\\ & \ge \rho {(z,x_{i+1})}^2-{\delta }^2-2\delta \rho (z,x_i)+\overline{c}{ϵ}^2.\end{array}$$

(32)

It follows from (26) and (29) that

$$\rho (z,x_{i+1})\le \rho (z,{\widehat{x}}_{i+1})+\rho (x_{i+1},{\widehat{x}}_{i+1})$$

$$\le \rho (z,{\widehat{x}}_{i+1})+\delta \le \rho (z,x_i)+\delta .$$

We show by induction that for all integers $i=0,\cdots ,Q-1$,

$$\rho (z,x_i)\le 2M,$$

$$\rho {(z,x_i)}^2\ge \rho {(z,x_{i+1})}^2+\overline{c}{ϵ}^2/2.$$

In view of (19) and (22),

$$\rho (z,x_0)\le \rho (z,\theta )+\rho (\theta ,x_0)\le 2M.$$

(33)

Assume that an integer $i\in \{0,\cdots ,Q-1\}$ and that

$$\rho (z,x_i)\le 2M.$$

(34)

According to (18), (32) and (34),

$$\begin{array}{ll}\rho {(z,x_i)}^2& \ge \rho {(z,x_{i+1})}^2-{\delta }^2-2\delta \rho (z,x_i)+\overline{c}{ϵ}^2\\ & \ge \rho {(z,x_{i+1})}^2-{\delta }^2-4\delta M+\overline{c}{ϵ}^2\\ & \ge \rho {(z,x_{i+1})}^2-\delta (4M+1)+\overline{c}{ϵ}^2\\ & \ge \rho {(z,x_{i+1})}^2+\overline{c}{ϵ}^2/2.\end{array}$$

(35)

In view of (34) and (35),

$$\begin{array}{c}\rho (z,x_{i+1})\le \rho (z,x_i)\le 2M,\\ \rho {(z,x_i)}^2-\rho {(z,x_{i+1})}^2\ge \overline{c}{ϵ}^2/2.\end{array}$$

(36)

Thus, by induction (see (33), (34), (36)), we have shown that for all $i=0,\cdots ,Q-1$,

$$\rho (z,x_i)\le 2M$$

(37)

and (36) holds. It follows from (36) and (37) that

$$4M^2\ge \rho {(z,z_0)}^2-\rho {(z,x_Q)}^2$$

$$=\sum _{i=0}^{Q-1}(\rho {(z,x_i)}^2-\rho {(z,x_{i+1})}^2)\ge Q{ϵ}^2\overline{c}/2$$

and

$$Q\le 8M^2{ϵ}^{-2}{\overline{c}}^{-1}.$$

This contradicts (17). The contradiction we have reached proves Theorem 2. □

5. Examples

An interesting example of the problem studied in [25] and in this paper was considered in Section 3 of [25]. This finite-dimensional example is related to a sparsity constrained minimization. Another important example of the problem considered here is obtained when C is a Hilbert space X, for each $i\in \{1,\cdots ,m\}$, $T_i$ is a projector of X on a nonempty, closed, convex set $C_i$. This is a well-known convex feasibility problem [19,20,22,23,24].

6. Conclusions

In our paper, we establish two extensions of the result of Tam (2018), which was obtained in a framework for the analysis of iterative algorithms described in terms of a structured set-valued operator. More precisely, at each point in the ambient space, it is assumed that the value of the operator can be expressed as a finite union of values of single-valued paracontracting operators. Our results are obtained for operators in an arbitrary metric space. In the first result, we study exact iterates of the set-valued mapping, while in the second one, we deal with its inexact iterates, taking into account computational errors. It should be mentioned that in a particular case of a Banach space, if all the operators are symmetric, then the set of all limit points of iterates is symmetric too. These results can be applied in the study of convex feasibility problems.