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.
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
