File Type: MS Word (DOC) & PDF

File Size: 460KB

Number of Pages:36

## ABSTRACT

## Let E be a uniformly convex and uniformly smooth real Banach space and E be its dual.

Let A : E ! 2E be a bounded maximal monotone map. Assume that A1(0) 6= ;. A new

iterative sequence is constructed which converges strongly to an element of A1(0). The theorem

proved, complements results obtained on strong convergence of the proximal point algorithm for

approximating an element of A1(0) (assuming existence) and also resolves an important open

question. Furthermore, this result is applied to convex optimization problems and to variational

inequality problems. These results are achieved by combining a theorem of Riech on the strong

convergence of the resolvent of maximal monotone mappings in a uniformly smooth real Banach

space; new geometric properties of uniformly convex and uniformly smooth real Banach spaces

introduced by Alber with a technique of proof which is also of independent interest.

** **

## TABLE OF CONTENTS

## List of publications arising from the thesis vi

1 Introduction and literature review 2

1.0.1 Accretive-type mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 PRELIMINARIES 10

2.1 Denition of some terms and concepts. . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Results of Interest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Some interesting properties of Normalized Duality map . . . . . . . . . . . . . . 15

3 Main Results 17

4 Applications 24

4.1 Application to convex minimization problems . . . . . . . . . . . . . . . . . . . 24

4.2 Application to variational inequality problems . . . . . . . . . . . . . . . . . . . 25

## CHAPTER ONE

Introduction and literature review

The contents of this thesis fall within the general area of nonlinear operator theory, a thriving

range of exploration for many mathematicians. In this thesis, we concentrate on an important

topic in this area-approximation of solutions of nonlinear equations involving monotone-type

mappings.

Let H be a real Hilbert space. A map A : H ! 2H is called monotone if for each x; y 2 H; the

following inequality holds:

h ; x yi 0; 8 2 Ax; 2 Ay: (1.1)

Monotone maps were rst studied in Hilbert spaces by Zarantonello [66], Minty [39], Kacurovskii

[32] and a host of other authors. Interest in such mappings comes mainly as a result of their

usefulness in applications. In particular, monotone mappings appear in optimization theory.

Consider, for example, the following: Let f : H ! R [ f1g be a proper convex function.

The subdierential of f, @f : H ! 2H, is dened for each x 2 H by @f(x) := fx 2 H :

f(y) f(x) hy x; xi 8 y 2 Hg. It is easy to verify that @f is a monotone operator on H,

and that 0 2 @f(u) if and only if u is a minimizer of f. Setting @f A, it follows that solving

the inclusion 0 2 Au, in this case, is solving for a minimizer of f.

Futhermore, the inclusion 0 2 Au when A is monotone map from a real Hilbert space to itself

also appears in evolution systems. Consider the evolution inclusion

du

dt

+ Au 3 0: (1.2)

where A is a monotone map from a real Hilbert space to itself. At equilibrium state, du

dt = 0 so

that Au 3 0, whose solutions correspond to the equilibrium state of the dynamical system.

In general, the following problem is of interest and has been studied extensively by numerous

authors.

Let H be a real Hilbert space. Find u 2 H such that

0 2 Au; (1.3)

where A : H ! 2H is a monotone-type operator.

Several existence theorems have been proved for the inclusion Au 3 0; where A is of the

monotone-type (see e.g., Deimling [27], Pascali and Sburlan [45]). As is well known, among

2

all innite dimensional Banach spaces, Hilbert spaces have the nicest geometric properties

(Chidume [13]). Hilbert spaces have four unique properties that make working in them relatively

easy. These are: availability of the inner product, the fact that projection maps are

nonexpansive and the following identities

kx + yk2 = kxk2 + 2hy; xi + kyk2 (1.4)

and

kx + (1 y) k2 = kxk2 + (1 )kyk2 (1 )kx yk2 (1.5)

However, even with these nice properties of Hilbert spaces, it is known that many and probably

most, mathematical objects and models do not naturally live in Hilbert spaces.

We quickly remark that once one moves out of Hilbert spaces, one loses these nice properties.

Consequently, to extend some of the Hilbert space techniques to more general Banach spaces,

analogues of the identities (1.4) and (1.5) have to be developed. For this development, the

duality map which has become a most important tool in nonlinear functional analysis plays a

central role (Chidume [13]). In 1976, Bynum [11] obtained the following analogue of (1.4) for

lp spaces, 1 < p < 1:

jjx + yjj2 (p 1)jjxjj2 + jjyjj2 + 2hx; j(y)i; 2 p < 1; (1.6)

(p 1)jjx + yjj2 jjxjj2 + jjyjj2 + 2hx; j(y)i; 1 < p 2: (1.7)

Analogues of (1.5) were also obtained by Bynum. In 1979, Reich [50] obtained the following

result which is an analogue of (1.4) in uniformly smooth Banach spaces:

Let E be a real uniformly smooth Banach space. Then, there exists a nondecreasing continuous

function : [0;1) ! [0;1), satisfying the following conditions:

(i) (ct) c(t) 8 c 1;

(ii) limt!0+ (t) = 0 and,

jjx + yjj2 jjxjj2 + 2Rehy; j(x)i + maxfjjxjj; 1gjjyjj(jjyjj) 8 x; y 2 E: (1.8)

Later on, other analogues of (1.4) and (1.5) were obtained and are given below:

(Xu, [59]) Let E be a puniformly convex space. Then, there exist constants dp > 0; cp > 0

such that for every x; y 2 E; fx 2 Jp(x); fy 2 Jp(y), the following inequalities hold:

jjx + yjjp jjxjjp + phy; fxi + dpjjyjjp; (1.9)

jjx + (1 )yjjp jjxjjp + (1 )jjyjjp cpWp()jjx yjjp; (1.10)

for all 2 [0; 1]; and

hx y; fx fyi c2jjx yjjp: (1.11)

(Xu, [59]) Let E be a real uniformly convex Banach space. For arbitrary r > 0, let Br(0) :=

fx 2 E : jjxjj rg. Then, there exists a continuous strictly increasing convex function

g : [0;1) ! [0;1); g(0) = 0 such that for every x; y 2 Br(0); fx 2 Jp(x); fy 2 Jp(y), the

following inequalities hold:

jjx + yjjp jjxjjp + phy; fxi + g(jjyjj); (1.12)

jjx + (1 )yjjp jjxjjp + (1 )jjyjjp Wp()g(jjx yjj); (1.13)

and,

hx y; fx fyi g(jjx yjj): (1.14)

3

(Xu, [59]) Let E be a real quniformly smooth Banach space. Then, there exist constants

cq > 0; dq > 0; d > 0 such that for all x; y 2 E,

jjx + yjjq jjxjjq + qhy; jq(x)i + dqjjyjjq; (1.15)

jjx + (1 )yjjq jjxjjq + (1 )jjyjjq cqWq()jjx yjjq; (1.16)

and,

hx y; jq(x) jq(y)i jjx yjjq: (1.17)

(Xu, [59]) Let E be a real uniformly smooth Banach space. For arbitrary r > 0; let Br(0) :=

fx 2 E : jjxjj rg. Then, there exists a continuous strictly increasing and convex function

g : [0;1) ! [0;1), g(0) = 0 such that for every x; y 2 Br(0); the following inequalities hold:

jjx + yjjq jjxjjq + qhy; jq(x)i + g(jjyjj); (1.18)

jjx + (1 )yjjq jjxjjq + (1 )jjyjjq Wq()g(jjx yjj); (1.19)

and,

hx y; jq(x) jq(y)i g(jjx yjj): (1.20)

(Xu and Roach, [64]) Let E be a real uniformly smooth Banach space. Then, there exist

constants D and C such that for all x; y 2 E; j(x) 2 J(x), the following inequality holds:

jjx + yjj2 jjxjj2 + 2hy; j(x)i + Dmaxfjjxjj + jjyjj;

1

2

CgE(jjyjj) (1.21)

where E denotes the modulus of smoothness of E, p 2 (1;1); 2 [0; 1] and Wp() :=

p(1 ) + (1 )p.

Given these developments in Banach spaces so far, it is not suprising that the notion of monotone

mappings has been extended to arbitrary real normed spaces. We now examine two

well-studied extensions of Hilbert space monotonicity to arbitrary normed spaces.

It is obvious that monotonicity of a map dened from a normed space to its dual is another

extension of Hilbert space monotonicity to general normed spaces.

The extension of the monotonicity condition from a Banach space into its dual has

been the starting point for the development of nonlinear functional analysis…: The

monotone mappings appear in a rather wide variety of contexts, since they can

be found in many functional equations. Many of them appear also in calculus of

variations, as subdierential of convex funtions (Pascali and Sburlan [45], p. 101).

1.0.1 Accretive-type mappings

Another extension of the concept of monotone mappings dened in real inner product spaces

to arbitrary real normed linear spaces is connected with the concept of accretive-type mappings

which were introduced independently in 1967 by Browder [7] and Kato [34]. A mapping A :

D(A) E ! E is called accretive if for each x; y 2 D(A), there exists j(x y) 2 J(x y)

such that

hAx Ay; j(x y)i 0;

where J is the normalized duality mapping from E into 2E dened by

J(x) := ff 2 E :

x; f

= kxk2 = kfk2g; (1.22)

4

where h:; :i denotes the duality pairing.

In a Hilbert space, the normalized duality map reduces to the identity map so that, in this

case, accretive maps are monotone.

In general, the following problem is of interest and has been studied extensively by numerous

authors.

Let E be a real Banach space. Find u 2 E such that

Au 3 0; (1.23)

where A : E ! E is an accretive-type operator.

Solutions to inclusion (1.23), in many cases, yield the equilibrium states of some dynamical

systems (see e.g., Brouwder [7], Chidume [13], p.116).

For approximating a solution of Au = 0, assuming existence, where A : E ! E is of accretive-

type, Browder [7], dened an operator T : E ! E by T := I A, where I is the identity map

on E. He called such an operator pseudo-contractive. It is trivial to observe that zeros of A

corresspond to xed points of T. Following this denition, a map T : E ! E is called pseudo-

contractive if (I T) is accretive, i.e., if for each x; y 2 E; there exists j(xy) 2 J(xy) such

that the following inequality holds:

hTx Ty; j(x y)i jjx yjj2;

and is called strongly pseudo-contractive if there exists k 2 (0; 1) such that for each x; y 2 E;

there exists j(x y) 2 J(x y) such that the following inequality holds:

hTx Ty; j(x y)i kjjx yjj2:

For strongly pseudo-contractive maps, Chidume [17] proved the following theorem.

Theorem 1.0.1. Let E = Lp; 2 p < 1, and K E be nonempty closed convex and

bounded. Let T : K ! K be a strongly pseudo-contractive and Lipschitz map. For arbitrary

x0 2 K, let a sequence fxng be dened iteratively by xn+1 = (1n)xn +nTxn; n 0; where

fng (0; 1) satises the following conditions: (i)

P1

n=1 n = 1; (ii)

P1

n=1 2n

< 1. Then,

fxng converges strongly to the unique xed point of T.

By replacing T by I A in Theorem 1.0.1, the following theorem for approximating the unique

solution of Au = 0 when A : E ! E is a strongly accretive and Lipschitz map is easily proved.

Theorem 1.0.2. Let E = Lp; 2 p < 1. Let A : E ! E be a strongly accretive and Lipschitz

map. For arbitrary x1 2 K, let a sequence fxng be dened iteratively by xn+1 = xnnAxn; n

1; where fng (0; 1) satises the following conditions: (i)

P1

n=1 n = 1; (ii)

P1

n=1 2n

< 1.

Then, fxng converges strongly to the unique solution of Au = 0.

The main tool used in the proof of Theorem 1.0.1 is an inequality of Bynum [11]. This theorem

signalled the return to extensive research eorts on inequalities in Banach spaces and their

applications to iterative methods for solutions of nonlinear equations. Consequently, Theorem

1.0.1 has been generalized and extended in various directions, leading to ourishing areas of

research, for the past thirty years or so, for numerous authors (see e.g., Censor and Riech [12],

Chidume [15, 16], Chidume and Ali [18], Chidume and Chidume [19, 20], Chidume and Osilike

5

[24], Deng [26], Mouda [41, 42, 43, 44], Zhou and Jia [68], Liu [37], Qihou [46], Berinde et

al. [6], Reich [50, 49], Reich and Sabach [52, 53], Weng [56], Xiao [58], Xu [61, 59, 60], Xu

and Roach [64], Xu[65], Zhu [69] and a host of other authors). Recent monographs emanating

from these researches include those by Berinde [5], Chidume [13], Goebel and Reich [29], and

William and Shahzad [57].

Also, assuming existence, a well-known algorithm for approximating a solution of inclusion

0 2 Au in real Hilbert spaces is the celebrated proximal point algorithm. The proximal point

algorithm (PPA) introduced by Martinet [38] and studied extensively by Rockafellar [54] and

numerous authors is concerned with an iterative method for approximating a solution of 0 2 Au

where A is a maximal monotone operator. Specically, given xn 2 H, the proximal point algorithm

generates the next iterate xn+1 by solving the following equation:

xn+1 =

I +

1

n

A

1

(xn) + en; (1.24)

where n > 0 is a regularizing parameter.

Rockafellar [54] proved that if the sequence fng1

n=1 is bounded from above, then the resulting

sequence fxng1

n=1 of proximal point iterates converges weakly to a solution of 0 2 Au, provided

that a solution exists. He then posed the following question.

Question 1. Does the proximal point algorithm always converge strongly?

This question was resolved in the negative by Guler [30], (see also Bauschke et al., [4]). This

naturally raised the following question.

Question 2. Can the proximal point algorithm be modied to guarantee strong conver-

gence?

Before we comment on Question 2, we make the following remark.

Remark 1. We observe that in using the proximal point algorithm, at each step of the iteration

process, one has to compute

I + 1

n

A

1

(xn) and this is generally not convenient in several

applications.

Consequently, while thinking of modications of the proximal point algorithm that will guarantee

strong convergence, the following question is, perhaps, more important than Question 2.

Question 3. Can an iteration process be developed which will not involve the

computation of

I + 1

n

A

1

(xn) at each step of the iteration process and which

will still guarantee strong convergence to a solution of 0 2 Au?

First, we review brie y modications of the PPA obtained by several authors that yield strong

convergence.

Bruck [9] considered an iteration process of the Mann-type and proved that the sequence

of the process converges strongly to a solution of the inclusion 0 2 Au in a real Hilbert space

where A is a maximal monotone map, provided the initial vector is chosen in a neighbourhood

of a solution of this inclusion. Chidume [14] extended this result to Lp spaces, p 2 (see also

6

Reich [49, 51]). These results of Bruck [9] and Chidume [14] are not easy to use in any possible

application because the neighborhood of a solution in which the initial vector must be chosen

is not known precisely.

Solodov and Svaiter [55] proposed a modication of the proximal point algorithm which

guarantees strong convergence in a real Hilbert space. Their algorithm involves the construction

of two subsets Ck and Qk in H and projection of the initial vector onto Ck \ Qk at each

stage of the iteration process.

The authors themselves noted ([55], p. 195) that “… at each iteration, there are two subproblems

to be solved…” : (i) nd an inexact solution of the proximal point algorithm, and (ii)

nd the projection of x0 onto Ck \ Qk: They also acknowledged that these two subproblems

constitute a serious drawback in using their algorithm.

Kamimura and Takahashi [33] extended this work of Solodov and Svaiter to the framework of

Banach spaces that are both uniformly convex and uniformly smooth. Reich and Sabach [53]

extended these results of Kamimura and Takahashi to re exive Banach spaces.

Xu [62] noted that “… Solodov and Svaiter’s algorithm, though strongly convergent, does

need more computing time due to the projection in the second subproblem …”. He then proposed

and studied the following algorithm:

xn+1 = nx0 + (1 n)

I + cnA

1

(xn) + en; n 0: (1.25)

He proved that the sequence generated by (1.25) converges strongly to a solution of 0 2 Au

provided that the sequences fng1n

=1 and fcng1 n=1 of real numbers and the sequence feng1 n=1 of

errors are chosen appropriately.

Lehdili and Mouda [35] considered the technique of the proximal map and the Tikhonov regularization

to introduce the so-called Prox-Tikhonov method. Using the notion of variational

distance, Lehdili and Mouda [35] proved strong convergence theorems for this algorithm and

its perturbed version, under appropriate conditions on their iteration parameters.

Xu also studied the perturbed version of the recurrence formulas studied by Lehdili and

Mouda and used the method of nonexpansive mappings to prove strong convergence theorems

for the perturbed version under much relaxed conditions on the iteration parameters.

Another modication of the proximal point algorithm, perhaps the most signicant, which

yields strong convergence, is implicitly contained in the following theorem of Reich.

Theorem 1.0.3 (Reich, [48]). Let E be a uniformly smooth real Banach space, and let A :

E ! 2E be m-accretive. Let Jtx := (I + tA)1x; t > 0 be the resolvent of A, and assume that

A1(0) is nonempty. Then, for each x 2 E, lim

t!1

Jtx exists and belongs to A1(0).

Remark 2. We note that, in response to Question 2, that each modication of the classical

proximal point algorithm to obtain strong convergence so far studied involved: either the com-

putation of

I + 1

n

A

1

(xn) at each step of the iteration process, or the construction of two

convex subsets Cn and Qn of the space E and projecting the initial vector onto Cn \Qn, at each

step of the process. This is certainly not easy to use in several applications.

Remark 3. The proximal point algorithm, however, can still be very useful in some special

cases. For example, the algorithm can be used in signal processing and in image restoration in

the cases where the proximal mappings are not very dicult to evaluate.

7

In response to Question 3, Chidume and Djitte [22] provided an armative answer when the

space E is a 2-uniformly smooth real Banach space. We note here that Lp spaces, p 2

are 2-uniformly smooth but Lp spaces, 1 < p < 2 are not. So, this result of Chidume

and Djitte does not guarantee strong convergence to a solution of 0 2 Au on Lp spaces, for

1 < p < 2. Recently, Chidume [21] proved the following theorem which is applicable in all Lp

spaces, 1 < p < 1:

Theorem 1.0.4 (Chidume, [21]). Let E be a uniformly smooth real Banach space with modulus

of smoothness E, and let A : E ! 2E be a multi-valued bounded maccretive operator with

D(A) = E such that the inclusion 0 2 Au has a solution. For arbitrary x1 2 E, dene a

sequence fxng1 n=1 by,

xn+1 = xn nun nn(xn x1); un 2 Axn; n 1;

where fng1n

=1 and fng1 n=1 are sequences in (0; 1) satisfying the folliowing conditions:

(i) limn!1 n = 0; fng1 n=1 is decreasing;

(ii)

P

nn = 1;

P

E(nM1) < 1, for some constant M1 > 0;

(iii) limn!1

h

n1

n

1

i

nn

= 0. There exists a constant 0 > 0 such that

E(n)

n

0n. Then the sequence fxng1n

=1 converges strongly to a zero of A.

We remark that a solution of 0 2 Au where A is an accretive-type mapping, in general, corresponds

to an equilibrium state of a dynamical system (see e.g., Zeidler, [67]).

We now consider the inclusion 0 2 Au where A : E ! 2E is of monotone-type. We have seen

that if H is a real Hilbert space and f : H ! R [ f1g a lower semi-continuous proper convex

function, then the subdierential of f; @f : H ! 2H is a maximal monotone map and that

0 2 @f(u) if and only if u is a minimizer of f: If E is a real normed space and f : E ! R[f1g

is a proper convex function, then, the subdierential of f; @f : E ! 2E is dened as follows:

for x 2 E;

@f(x) = fx 2 E : f(y) f(x) hy x; xi; 8 y 2 Eg

and it is clear from this that 0 2 @f(u) if and only if u is a minimizer of f: It is trivial that the

subdierential of f; @f : E ! 2E satitses the following inequality:

hx y; x yi 0 8x 2 @f(x); y 2 @f(y): (1.26)

In this case, the subdierential is said to be monotone. In the case that the subdierential @f

is single-valued, inequality (1.26) reduces to

h@f(x) @f(y); x yi 0 8 x; y 2 E:

This leads to the following denition. For an arbitrary real normed space E with dual space

E; a mapping A : E ! 2E is called monotone if

h ; x yi 0 8 2 Ax; 2 Ay: (1.27)

It is clear that if E = H a real Hilbert space, then E = E = H and inequality (1.27) coincides

with the monotonicity denition in Hilbert spaces. This extension of the Hilbert space

monotonicity condition to an arbitrary normed space as given in (1.27) was the begining of the

development of nonlinear functional analysis (Pascali and Sburlan [45]).

Unfortunately, for approximating a solution of inclusion 0 2 Au in real Banach spaces more

general than real Hilbert spaces, the success achieved in using geometric properties developed

from the mid 1980s to early 1990s in approximating zeros of accretive-type mappings has not

8

carried over to approximating zeros of monotone-type mappings. Part of the problem is that

since A maps E to E, for xn 2 E, Axn is in E. Consequently, a recursion formula involving

only xn and Axn may not be well dened. Another diculty is that the xed point technique

for approximating solutions of Au = 0 introduced by Browder [7] for accretive-type mappings

from E to E is not directly applicable here, since A maps E into E.

Attempts were made to overcome the rst diculty by introducing the inverse of the normalized

duality mapping in the recursion formulas for approximating zeros of monotone-type mappings.

Fortunately, new geometric properties of Banach spaces recently introduced by Alber are appropriate

for approximating zeros of monotone-type mappings.

In this thesis, our aim is to prove an analogue of theorem 1.0.4 for maximal monotone mappings,

A : E ! 2E and apply it to convex optimization problems and to variational inequality

problems.