Ergodicity of the implicit midpoint rule for nonexpansive mappings

Abstract

We prove a mean ergodic theorem for the implicit midpoint rule for nonexpansivemappings in a Hilbert space. We obtain weak convergence for the general case andstrong convergence for certain special cases.

MSC: 47J25, 47N20, 34G20, 65J15.

1 Introduction

The first mean ergodic theorem for nonlinear noncompact operators was proved byBaillon [1]. Let C be a closed convex subset of a Hilbert space Hand let be a nonexpansive mapping (i.e., for all ) with fixed points. Then, for each, the Cesàro means

converge weakly to a fixed point of T. This mean ergodic theorem wasextended by Bruck [2] to the setting of Banach spaces that are uniformly convex and have aFréchet differentiable norm. Baillon and Clement [3] also investigated ergodicity of the nonlinear Volterra integral equationsin Hilbert spaces.

It is quite natural to consider ergodic convergence of iterative algorithms in thecase where the sequences generated by the algorithms either are not guaranteed toconverge or not convergent at all. For instance, the double-backward method ofPassty [4] generates a sequence in the recursive manner:

(1.1)

where A and B are maximal monotone operators in a Hilbert spacesuch that is also maximal monotone and the inclusion is solvable, and and are the resolvents of A and B,respectively, that is, and . It is well known [5] that the sequence generated by the double-backward method (1.1) failsto converge weakly, in general. However, Passty [4] showed that if the sequence of parameters, , is in , then the averages

(1.2)

converge weakly to a solution to the inclusion .

The implicit midpoint rule (IMR) for nonexpansive mappings in a Hilbert spaceH, inspired by the IMR for ordinary differential equations [6–12], was introduced in [13]. This rule generates a sequence via the semi-implicit procedure:

(1.3)

where the initial guess is arbitrarily chosen, for all n, and is a nonexpansive mapping with fixed points.

The IMR (1.3) is proved to converge weakly [13] in the Hilbert space setting provided the sequence satisfies the two conditions:

(C1) for all and some , and

(C2) .

However, this algorithm may fail to converge weakly without the assumption (C2). Wetherefore turn our attention to the ergodic convergence of the algorithm. We willshow that for any sequence in the interval , the mean averages as defined by (1.2) will always converge weakly to afixed point of T as long as is an approximate fixed point of T(i.e., ). We will also show that under certain additionalconditions the means can converge in norm to a fixed point of T.This paper is organized as follows. In the next section we introduce the concept ofnearest point projections and properties of nonexpansive mappings. The main resultsof this paper (i.e., weak and strong ergodicity of the IMR (1.3)) arepresented in Section 3.

2 Preliminaries

Let C be a nonempty closed convex subset of a Hilbert space H.Recall that the nearest point projection from H to C,, is defined by

(2.1)

We need the following characterization of projections.

Lemma 2.1LetCbe a nonempty closed convex subset of a Hilbert spaceH. Givenand, thenif and only if any one of the following properties is satisfied:

• (i) for all;

• (ii) for all;

• (iii) for all.

Recall that a mapping is said to be nonexpansive if

A point such that is said to be a fixed point of T. The set ofall fixed points of T is denoted by , namely,

In the rest of this paper we always assume .

We need the demiclosedness principle of nonexpansive mappings as described below.

Lemma 2.2[14]

LetCbe a closed convex subset of a Hilbert spaceHand letbe a nonexpansive mapping. Then the mappingis demiclosed in the sense that, for any sequenceofC, the following implication holds:

Next we need the following lemma (not hard to prove).

Lemma 2.3[15]

For each integer, such that, points, and any nonexpansive mapping, we have

(2.2)

Recall also that the implicit midpoint rule (IMR) [13] generates a sequence by the recursion process

(2.3)

where for all n, and is a nonexpansive mapping.

The following properties of the IMR (2.3) are proved in [13].

Lemma 2.4Letbe any sequence inand letbe the sequence generated by the IMR (2.3). Then

• (i) for alland. In particular, is bounded, and moreover, we have

  

  (2.4)

• (ii) .

• (iii) .

The convergence of the IMR (2.3) is proved in [13].

Theorem 2.5LetCbe a nonempty closed convex subset of a Hilbert spaceHandbe a nonexpansive mapping with. Assumeis generated by the IMR (2.3) where the sequenceof parameters satisfies the conditions (C1) and (C2) in theIntroduction. Thenconverges weakly to a fixed point ofT.

3 Ergodicity

In this section we discuss the ergodic convergence of the sequence generated by the IMR (2.3), that is, the convergenceof the means

(3.1)

where is a sequence of positive numbers such that

(3.2)

Set and let be the nearest point projection from H toF.

Lemma 3.1The sequenceis convergent in norm.

Proof First observe that

(3.3)

As a matter of fact, we get for , by Lemma 2.1(i) and Lemma 2.4(i),

That is, is decreasing and (3.3) is proven.

Applying the inequality (Lemma 2.1(iii))

(3.4)

to the case where and (with ) together with Lemma 2.4(i), we get

The strong convergence of follows immediately from the fact(3.3). □

Remark 3.2 The limit of , which we denote by , can also be identified as the asymptotic center ofthe sequence with respect to the fixed point set F ofT. In other words,

(3.5)

As a matter of fact, by (3.4) we get, for any ,

Upon taking limsup we immediately obtain

Hence, (3.5) holds.

Theorem 3.3LetCbe a closed convex subset of a Hilbert spaceHand letbe a nonexpansive mapping such that. Assumeis any sequence of positive numbers in the unit intervaland letbe the sequence generated by the IMR (2.3). Define the meansby (3.1), where the weightsare all positive and satisfy the condition (3.2). Assume, inaddition, . Thenconverges weakly to a pointz, where (in norm).

Proof Let which is well defined by Lemma 3.1. ByLemma 2.1(ii), we have, for each k,

It turns out that, for ,

(Here M is a constant such that for all k.)

By multiplying by and then summing up from to n, we conclude

(3.6)

We now claim that

(3.7)

Consequently, by Lemma 2.2, each weak cluster point of falls in F.

To see (3.7), we will prove that

(3.8)

for all n big enough, where as . For the sake of simplicity, we may, due to theassumption , assume that

(3.9)

for all n.

Let for and let M be a constant such that. For each n, we put for and apply (2.2) to get

(3.10)

Combining (3.9) and (3.10), we derive that

(3.11)

It turns out that (3.8) with .

Now since in norm, we see that the means in norm, as well. Consequently, if is a subsequence weakly converging to some point, it follows from (3.6) that

(3.12)

This together with the fact that implies that . That is, z is the only weak cluster pointof the sequence and therefore, we must have weakly. □

Remark 3.4 In Theorem 3.3 we assumed that . This assumption is guaranteed if the sequence satisfies the condition (C2) in the Introduction,that is, . Indeed, by (C2) and Lemma 2.4(ii), we find

(3.13)

Since the definition of IMR (2.3) yields

we also have

(3.14)

Combining (3.13) and (3.14), we infer that

Remark 3.5 If we assume (3.9) holds for all , then we need some more delicate technicalitiesdealing with (3.10). We may proceed as follows. Decompose (for ) as

where

As , we may assume . Repeating the argument for (3.10) and (3.11), we get

Let . We finally obtain, for ,

Next we show that in some circumstances, the sequence can converge strongly.

Theorem 3.6Let the assumptions of Theorem 3.3 holds. Then thesequenceconverges in norm to the pointif, in addition, any one of the following conditions issatisfied:

• (i) The fixed point setFofThas nonempty interior.

• (ii) Tis a contraction, that is,

  

whereis a constant. In this case, the sequencegenerated by the IMR (2.3) converges in norm to the unique fixed pointofT.

• (iii) Tis compact, namely, Tmaps bounded sets to relatively norm-compact sets.

Proof (i) By assumption, we have and such that

• for all such that .

Therefore, upon substituting for u in (3.6) we obtain

(3.15)

for all such that .

Taking the supremum in (3.15) over such that immediately yields

This verifies that in norm.

• (ii) Since T is a contraction, T has a unique fixed point which is denoted by p. By (2.3) we deduce that (noticing )

  

It turns out that

and hence

Since , we must have . However, since the sequence is decreasing, we must have . Namely, in norm, and so in norm.

• (iii) Since T is compact and since is weakly convergent, is relatively norm-compact. This together with (3.7) evidently implies that is relatively norm-compact. Therefore, must converge in norm to . □