ABSTRACT

We study iterative processes of stochastic approximation for finding fixed points of weakly contractive and nonexpansive operators in Hilbert spaces under the condition that operators are given with random errors. We prove mean square convergence and convergence almost sure (a.s.) of iterative approximations and establish both asymptotic and nonasymptotic estimates of the convergence rate in degenerate and non-degenerate cases. Previously the stochastic approximation algorithms were studied mainly for optimization problems.

1. Introduction

In this paper the following problem is solved: To find a fixed point of the operator in other words, to find a solution of the equation

(1.1)

where is a Lipschitz continuous mapping, is a Hilbert space, is a closed convex subset. We suppose that exists, i.e., the fixed point set of is nonempty. Note in different particular cases of the Equation (1.1), for example, when the solution existence and solution uniqueness can be proved under some additional assumptions.

We separately consider two classes of mappings T: the class of weakly contractive maps and more general class of nonexpansive ones. Let us recall their definitions.

Definition 1.1. A mapping is said to be weakly contractive of class on a closed convex subset if there exists a continuous and increasing function defined on such that is positive on and for all

(1.2)

Remark 1.2. It follows from (1.2) that and in real problems an argument of the function doesn’t necessary approaches to obeying the condition (see the example in Remark 3.4).

Definition 1.3. A mapping is said to be nonexpansive on the closed convex subset if for all

It is obvious that the class of weakly contractive maps is contained in the class of nonexpansive maps because the right-hand side of (1.2) is estimated as

(1.3)

and it contains the class of strongly contractive maps because with gives us

(1.4)

We study the following algorithm of stochastic approximation:

(1.5)

where is the metric projection operator from onto G and deterministic step-parameters satisfy the standard conditions:

(1.6)

The factor in (1.5) is an infinite-dimensional vector of random observations of the clearance operator at random points given for all on the same probability space We set

(1.7)

where and is a sequence of independent random vectors with the conditions

(1.8)

Here is a symbol of the mathematical expectation. In order to calculate conditional mathematical expectations of different random variables we define the - subalgebra on And then means function with the following property: for any

We also assume in the sequel that is A_n-measurable for all

Let us recall the mean square convergence and almost sure (a.s.) convergence.

We say that the sequence of random variables converges in mean square to if exists and

The sequence converges to almost surely or with probability 1 if

Almost sure convergence and convergence in mean square imply convergence in the sense of probability: The sequence of random variables converges in the sense of probability to if for all

So, we consider iterative processes of stochastic approximation in the form (1.5) for finding fixed points of weakly contractive (Definition 1.1) and nonexpansive (Definition 1.3) mappings in Hilbert spaces under the conditions (1.8). We prove mean square convergence and convergence almost sure of iterative approximations and establish both asymptotic and nonasymptotic estimates of the convergence rate. Perhaps, we present here the first results of this sort for fixed point problems. Formerly the stochastic approximation methods were studied mainly to find minimal and maximal points in optimization problems (see, for example, [1-6] and references within).

2. Auxiliary Recurrent Inequalities

Lemma 2.1. [3,4] Let be sequences of nonnegative real numbers satisfying the recurrent inequality.

(2.1)

Assume that and Then

is bounded and converges to some limit.

Lemma 2.2. [3,4] Let be sequences of nonnegative real numbers satisfying the recurrent inequality.

(2.2)

where and either or

(2.3)

Assume that is continuous and increasing function defined on such that is positive on, Then There exists an infinite subsequence such that

where

In the following two lemmas we want to present nonasymptotic estimates for the whole sequence For this the stronger requirements are made of parameters and function in the recurrent inequality.

Suppose that such that and

are antiderivatives from and respectively, with arbitrary constants (without loss of generality, one can put), i.e.

Observe that has the following properties:

i)

ii) is strictly increasing on and as

iii) The function is decreasing;

iv) as

Introduce the following denotations:

1) and are the inverse functions to and respectively;

2) is a fixed control parameter;

3)

4)

5) where

is an arbitrary fixed number;

We present now the based condition (P): The graphs of the scalar functions and with any fixed are intersected on the interval not more than at two points and (we do not consider contact points as intersection ones excepting if any).

For example, the graphs of the functions and

calculated for

and satisfy the condition (P).

Lemma 2.3. [3,4] Assume that 1) the property (P) is carried out for the function and

2) as 3) the control parameter is chosen such that

(2.4)

Then for the sequence generated by the inequality

(2.5)

it follows: and for all

(2.6)

Lemma 2.4. [3,4] Assume that 1) the property (P) is carried out for all the function and 2) as Then for the sequence generated by the inequality (2.5) In additiona) if and the control parameter is chosen such that as then for all

(2.7)

b) in all remaining cases

(2.8)

(2.9)

where is a unique root of the equation

(2.10)

on the interval.

The following lemmas deal with another sort of recurrent inequalities:

Lemma 2.5. [7,8] Let be sequences of non-negative real numbers satisfying the recurrence inequality.

(2.11)

Assume that

Then:

i) There exists an infinite subsequence such that

(2.12)

and, consequently,

ii) if and there exists such that

(2.13)

for all, then

Lemma 2.6. [7,8] Let be sequences of non-negative real numbers satisfying the recurrence inequality (2.11). Assume that

and (2.3) is satisfied. Then there exists an infinite subsequence such that

3. Mean Square Convergence of Stochastic Approximations

Theorem 3.1. Assume that is a weakly contractive mapping of the class is a convex function with respect to and

Then the sequence generated by (1.5)-(1.7) converges in mean square to a unique fixed point of There exists an infinite subsequence such that

(3.1)

where and some positive constant satisfies the inequality

(3.2)

Remark 3.2. exists in view of the second condition in (1.6).

Proof. First of all, we note that the method (1.5)-(1.7) guarantees inclusion for all Since the metric projection operator is nonexpansive in a Hilbert space and exists, we can write

(3.3)

Let us evaluate the first scalar product in (3.3). We have

(3.4)

We remember that Then the inequalities (3.3) and (3.4) yield

(3.5)

Applying the conditional expectation with respect to to the both sides of (3.5) we obtain

(3.6)

It is easy to see that

(3.7)

Since is weakly contractive and therefore nonexpansive, one gets

Taking into account (3.7), the inequality (3.9) is estimated as follows:

(3.8)

Now the unconditional expectation implies

(3.9)

Next we need the Jensen inequality for a convex function

(see [9,10]). This allows us to rewrite (3.9) in the form

(3.10)

because of

Denoting we have

(3.11)

where in view of Definition 1.1, is a continuous and increasing function with Due to (6), from Lemma 2.2 it follows

and the estimate (3.1) holds too. The theorem is proved. □

Remark 3.3. If a fixed point of weakly contractive mapping exists, then it is unique [11].

Remark 3.4. The following example was presented in  [11]: Let and It has been shown in [11] that

for all Then

Definition 3.5. Let a nonexpansive mapping

have a unique fixed point. T is said to be weakly sub-contractive on the closed convex subset if there exists continuous and increasing function defined on such that is positive on

, , such that for all

.

(3.12)

Theorem 3.6. Assume that a mapping is weakly sub-contractive and the function in (3.12) is convex on Then the results of Theorem 3.1 holds for the sequence generated by (1.5)-(1.7).

The second inequality in (1.6) can be omitted if we assume not less than linear growth of “on infinity” and put as

Theorem 3.7. Assume that a mapping is weakly sub-contractive and the function in (3.12) is convex on Suppose that instead of (1.6) the conditions

(3.13)

hold. In addition, let and

(3.14)

Then the sequence generated by (1.5), (1.7) and (3.13) converges in mean square to There exists an infinite subsequence such that

where

(3.15)

Proof. Consider the inequality ( 11) in the form

(3.16)

where Observe that it is derived by making use of (3.4) and the nonexpansivity property of We shall show that are bounded for all Indeed, since is a convex increasing continuous function, we conclude that

is nondecreasing and since (3.14) holdsthe inequality has a solution where is the unique root of the scalar equ0 ation Together with this, (3.4) and (3.14) are co-ordinated by the parameter

Only one alternative can happen for each either

or

Denote and

. It is clear that From the hypothesis it arises

and then for all From the hypothesis we have: for all Consider all the possible cases:

1) Then for all

2) Then for all

3) Let and Then for By (3.16), It is obvious that for Therefore, for all

4) Let and Then for and for Thus, for all

5) Let and be unbounded sets. Consider an arbitrary interval

where It is easy to be sure that and for all

6) The other situations of bounded and unbounded sets and are covered by the items 1)-5). Consequently, we have the final result: for all

Thus, we obtain the inequality

(3.17)

where is defined by (3.15). Now Lemma 2.2 with the condition (2.3) implies the result. □

Remark 3.8. For a linear function which is convex and concave at the same time we suppose

Remark 3.9. If is bounded or more generally is bounded, then the inequality (3.17) (with some different constant) immediately follows from (3.16).

4. Estimates of the Mean Square Convergence Rate

Using Lemmas 2.3 and 2.4 we are able to give two general theorems on the nonasymptotic estimates of the mean square convergence rate for sequence generated by the stochastic approximation algorithm (1.5)- (1.7).

Again we introduce denotations 1)-5) from Section 2 induced now by the recurrent inequality (3.11):

1) and are the inverse functions to and respectively;

2) is a fixed control parameter;

3)

4)

5)

Introduce also the basic condition (P).

Theorem 4.1. Assume that all the conditions of Theorem 3.1 are fulfiled and i) the condition (P) holds for the functions

and

ii) as

iii) is chosen such that as

Then the sequence generated by (1.5)-(1.7) converges in average to a unique fixed point of and for all

(4.1)

Theorem 4.2. Assume that all the conditions of Theorem 3.1 are fulfiled and i) the condition (P) holds for the functions

and with any fixed

ii) as

iii) If and is chosen such that as then the sequence

generated by (1.5)-(1.7) converges in average to a unique fixed point of and for all

(4.2)

iv) In all the remaining cases, (4.1) holds for and (4.2) for where is a unique root of the equation on the interval.

Let us provide the examples of functions and suitable for Theorems 4.1 and 4.2 (see [12,13]).

1) Below in Corollaries 4.3-4.6 we use the functions with For them

(4.3)

and

(4.4)

2) If then

3) If then

4) If then

In this example we are unable to define in analitical form, therefore suggest to calculate it numerically by computer.

We next present very important corollaries from Theorems 4.1 and 4.2, where their assumptions automatically guarantee accomplishment of the condition (P) (see [4]). The functions coincide with the point 1) above.

Corollary 4.3. Assume that is a strongly contractive mapping, that is, (1.4) is satisfied with

Let in (1.5) Then

I. Suppose that and Then

and 1) If and we have for all

(4.5)

2) In all the remain cases

(4.6)

and

(4.7)

where is a unique root of the equation

on the interval.

II. Suppose that and

Then and the estimate (4.6) holds for all

Corollary 4.4. Assume that is a strongly contractive mapping, that is, in (1.4) is satisfied with

Let in (1.5) Then

Suppose that Then

and 1) If and we have for all

(4.8)

2) In all the remain cases the estimates (4.6) and (4.7) hold.

Corollary 4.5. Assume that is a weakly contractive mapping of the class that is, in Theorem 3.1 Let in (1.5)

Then

If is chosen from the condition

then and for all

(4.9)

Corollary 4.6. Assume that is a weakly contractive mapping of the class that is, in Theorem 3.1 Let in (1.5)

Then

I. Suppose that

1) If and is chosen from the condition

then and for all

(4.10)

2) In all the remain cases the estimates (4.6) and (4.7) hold.

II. Suppose that

If is chosen from the condition

then and for all

(4.11)

In addition to the examples presented in this section, we produce the functions and which have as a tangency point of the infinite degree multiplicity and given logarithmic estimates of the convergence rate.

We define the function by the following way:

where is differentiable and decreasing function,

and

where denote the derivative degrees of the function

It is easy to see that

and

In particulari) We have

and We have to verify that is convex. In fact, it is true because

Beside this, it is easy to see that at least, on the interval. In the next examples we leave to readers to check these properties.

ii)

We have and

iii)

We have

and

5. Almost Sure Convergence of Stochastic Approximations for Nonexpansive Mappings

Consider next the almost surely convergence of stochastic approximations. First of all, we need the stochastic analogy of Lemma 2.5:

Lemma 5.1. Let be sequences of non-negative real numbers and be sequence of random measurable variables, a.s. nonnegative for all Assume that

If and there exists such that for all

(5.1)

then a.s.

The proof can be provided by the scheme of nonstochastic case (see Proposition 2 in [8]) or as it was done in [5].

We need also the following lemma from [14] as applied to our case of Hilbert spaces (the concepts of modulus of convexity of Banach spaces B or Hilbert spaces can be found in [15] and [16]).

Lemma 5.2. If with a nonexpansive mapping then for all

where

If and with then and

Theorem 5.3. Assume that a mapping is nonexpansive and its fixed point set is nonempty. If

(1.8) holds and then the sequence

generated by (1.5)-(1.7) weakly almost surely converges to some

Proof. Let We next use Lemma 5.2 and the estimate (see [17], p. 49)

to get

In this case the inequality (3.3) implies

(5.2)

Similarly to (3.10), we have

(5.3)

Denote and

and apply the unconditional expectation to both sides of (5.3). Then

(5.4)

It follows from this that

Since and due to Lemma 2.1, we conclude that is bounded. Consequently, is bounded a.s. that follows from the theory of convergent quasimartingales (see [5,18]).

We now need Lemma 5.1. It is not difficult to see that

(5.5)

The last gives us

Next we evaluate the following difference:

It is easy to see that is bounded a.s. Indeed, since a.s., there exists a constant such that

Therefore

It is obviously that

Thus,

By Lemma 5.1, a.s. as

Since is bounded a.s., there is a subsequence weakly convergent to some point Since is convex and closed, consequently, weakly closed, we assert that It is known that a nonexpansive mapping is weakly demiclosed, therefore, a.s. Weak almost surely convergence of whole sequence is shown by the standard way [8]. □

Corollary 5.4. Assume that is a weakly contractive mapping of the class If and then the sequence

generated by (1.5)-(1.7) strongly almost surely converges to unique fixed point of

Proof. We have from (3.4)

(5.6)

Since is bounded a.s. and a.s.

as we conclude that a.s.

The proof follows due to the properties of the function □

Remark 5.5. It is clear that all the results remain still valid for self-mappings However, in this case, unlike any deterministic situation, the algorithm (1.5)-(1.7) must use the projection operator because the vector not always belongs to G. If for all and then (1.5) can be replaced by

REFERENCES