Volume 2007, Article ID 32870,8pages doi:10.1155/2007/32870
Research Article
Iterative Algorithm for Approximating Solutions of Maximal Monotone Operators in Hilbert Spaces
Yonghong Yao and Rudong ChenReceived 11 October 2006; Revised 8 December 2006; Accepted 11 December 2006 Recommended by Nan-Jing Huang
We first introduce and analyze an algorithm of approximating solutions of maximal monotone operators in Hilbert spaces. Using this result, we consider the convex mini- mization problem of finding a minimizer of a proper lower-semicontinuous convex func- tion and the variational problem of finding a solution of a variational inequality.
Copyright © 2007 Y. Yao and R. Chen. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1. Introduction
Throughout this paper, we assume thatH is a real Hilbert space andT:H →2H is a maximal monotone operator. A well-known method for solving the equation 0∈Tvin a Hilbert spaceHis the proximal point algorithm:x1=x∈Hand
xn+1=Jrnxn, n=1, 2,. . ., (1.1) where{rn} ⊂(0,∞) andJr=(I+rT)−1for allr >0. This algorithm was first introduced by Martinet [1]. Rockafellar [2] proved that if lim infn→∞rn>0 andT−10= ∅, then the sequence{xn}defined by (1.1) converges weakly to an element ofT−10. Later, many re- searchers have studied the convergence of the sequence defined by (1.1) in a Hilbert space;
see, for instance, [3–6] and the references mentioned therein. In particular, Kamimura and Takahashi [7] proved the following result.
Theorem 1.1. LetT:H→2H be a maximal monotone operator. Let{xn}be a sequence defined as follows:x1=u∈Hand
xn+1=αnu+1−αnJrnxn, n=1, 2,. . ., (1.2)
where{αn} ⊂[0, 1] and{rn} ⊂(0,∞) satisfy limn→∞αn=0,∞n=1αn= ∞, and limn→∞rn=
∞. IfT−10= ∅, then the sequence{xn}defined by (1.2) converges strongly toPu, whereP is the metric projection ofHontoT−10.
Motivated and inspired by the above result, in this paper, we suggest and analyze an it- erative algorithm which has strong convergence. Further, using this result, we consider the convex minimization problem of finding a minimizer of a proper lower-semicontinuous convex function and the variational problem of finding a solution of a variational in- equality.
2. Preliminaries
Recall that a mappingU:H→His said to be nonexpansive ifUx−U y ≤ x−yfor allx,y∈H. We denote the set of all fixed points ofUbyF(U). A multivalued operator T:H→2H with domainD(T) and rangeR(T) is said to be monotone if for eachxi∈ D(T) andyi∈Txi,i=1, 2, we havex1−x2,y1−y2 ≥0.
A monotone operatorTis said to be maximal if its graphG(T)= {(x,y) :y∈Tx}is not properly contained in the graph of any other monotone operator. LetI denote the identity operator onH and letT:H→2H be a maximal monotone operator. Then we can define, for eachr >0, a nonexpansive single-valued mappingJr:H→HbyJr=(I+ rT)−1. It is called the resolvent (or the proximal mapping) ofT. We also define the Yosida approximationAr byAr=(I−Jr)/r. We know thatArx∈TJrxandArx ≤inf{y: y∈Tx}for allx∈H.
Before starting the main result of this paper, we include some lemmas.
Lemma 2.1 (see [8]). Let{xn}and{zn}be bounded sequences in a Banach spaceX and let{αn}be a sequence in [0, 1] with 0<lim infn→∞αn≤lim supn→∞αn<1. Supposexn+1= αnxn+ (1−αn)zn for all integers n≥0 and lim supn→∞(zn+1−zn − xn+1−xn)≤0.
Then, limn→∞zn−xn =0.
Lemma 2.2 (the resolvent identity). Forλ,μ >0, there holds the identity
Jλx=Jμ
μ λx+
1−μ
λ
Jλx
, x∈X. (2.1)
Lemma 2.3 (see [9]). LetEbe a real Banach space. Then for allx,y∈E
x+y2≤ x2+ 2y,j(x+y) ∀j(x+y)∈J(x+y). (2.2) Lemma 2.4 (see[10]). Let{an}be a sequence of nonnegative real numbers satisfying the propertyan+1≤(1−sn)an+sntn,n≥0, where{sn} ⊂(0, 1) and{tn}are such that
(i)∞n=0sn= ∞,
(ii) either lim supn→∞tn≤0 or∞n=0|sntn|<∞. Then{an}converges to zero.
3. Main result
LetT:H→2Hbe a maximal monotone operator and letJr:H→H be the resolvent of T for eachr >0. Then we consider the following algorithm: for fixedu∈H and given x0∈Harbitrarily, let the sequence{xn}is generated by
yn≈Jrnxn,
xn+1=αnu+βnxn+δnyn, (3.1) where{αn},{βn},{δn}are three real numbers in [0, 1] and{rn} ⊂(0,∞). Here the crite- rion for the approximate computation ofynin (3.1) will be
yn−Jrnxn ≤σn, (3.2)
where∞n=0σn<∞.
Theorem 3.1. LetT:H→2Hbe a maximal monotone operator. Assume{αn},{βn},{δn}, and{rn}satisfy the following control conditions:
(i)αn+βn+δn=1;
(ii) limn→∞αn=0 and∞n=0αn= ∞; (iii) 0<lim infn→∞βn≤lim supn→∞βn<1;
(iv)rn≥>0 for allnandrn+1−rn→0(n→ ∞).
IfT−10= ∅, then{xn}defined by (3.1) under criterion (3.2) converges strongly toPu, where Pis the metric projection ofHontoT−10.
Proof. FromT−10= ∅, there existsp∈T−10 such thatJsp=pfor alls >0. Then we have xn+1−p ≤αnu−p+βn xn−p +δn yn−p
≤αnu−p+βn xn−p +δn
σn+ Jrnxn−p
≤αnu−p+βn xn−p +δn xn−p +δnσn
=αnu−p+1−αn xn−p +δnσn.
(3.3)
An induction gives that
xn−p ≤maxu−p, x0−p + n k=0
σk (3.4)
for alln≥0. This implies that{xn}is bounded. Hence{Jrnxn}and{yn}are also bounded.
Define a sequence{zn}by
xn+1=βnxn+1−βnzn, n≥0. (3.5)
Then we observe that
zn+1−zn=xn+2−βn+1xn+1
1−βn+1 −xn+1−βnxn
1−βn
=
αn+1
1−βn+1− αn
1−βn
u+ δn+1
1−βn+1
yn+1−yn
+
δn+1
1−βn+1− δn
1−βn
yn.
(3.6)
Ifrn−1≤rn, fromLemma 2.2, using the resolvent identity Jrnxn=Jrn−1
rn−1
rn xn+
1−rn−1
rn
Jrnxn
, (3.7)
we obtain
Jrnxn−Jrn−1xn−1 ≤rn−1
rn xn−xn−1 +
rn−rn−1
rn Jrnxn−xn−1
≤ xn−xn−1 +1
rn−1−rn Jrnxn−xn−1 .
(3.8)
Similarly, we can prove that the last inequality holds ifrn−1≥rn. On the other hand, from (3.2), we have
yn+1−yn ≤ yn+1−Jrn+1xn+1 + yn−Jrnxn + Jrn+1xn+1−Jrnxn
≤σn+1+σn+ Jrn+1xn+1−Jrnxn . (3.9) Thus it follows from (3.5) that
zn+1−zn − xn+1−xn
≤ αn+1
1−βn+1− αn
1−βn
u+ yn + δn+1
1−βn+1 xn+1−xn + δn+1
1−βn+1
1
rn+1−rn× Jrn+1xn+1−xn +σn+1+σn− xn+1−xn
≤ αn+1
1−βn+1− αn
1−βn
u+ yn +σn+1+σn + δn+1
1−βn+1
1
rn+1−rn× Jrn+1xn+1−xn ,
(3.10)
which implies that lim supn→∞(zn+1−zn − xn+1−xn)≤0. Hence, byLemma 2.1, we have limn→∞zn−xn =0. Consequently, it follows from (3.5) that
nlim→∞ xn+1−xn =lim
n→∞
1−βn zn−xn =0. (3.11) On the other hand,
xn−yn ≤ xn+1−xn + xn+1−yn
≤ xn+1−xn +αn u−yn +βn xn−yn , (3.12)
and so, by (ii), (iii), (3.11), and (3.12), we have limn→∞xn−yn =0. It follows that Arnxn ≤ 1
rn xn−yn + yn−Jrnxn ≤1
xn−yn +σn−→0. (3.13) We next prove that
lim sup
n→∞
u−Pu,xn+1−Pu≤0, (3.14)
wherePis the metric projection ofH ontoT−10. To prove this, it is sufficient to show lim supn→∞u−Pu,Jrnxn−Pu ≤0, becausexn+1−Jrnxn→0. Now there exists a subse- quence{xni} ⊂ {xn}such that
limi→∞
u−Pu,Jrnixni−Pu=lim sup
n→∞
u−Pu,Jrnxn−Pu. (3.15)
Since {Jrnxn}is bounded, we may assume that{Jrnixni} converges weakly to somev∈ H. Then it follows thatv∈T−10. Indeed, sinceArnxn∈TJrnxnandT is monotone, we haves−Jrnixni,s−Arnixni ≥0, wheres∈Ts. FromArnxn→0, we obtains−v,s ≥0 whenevers∈Ts. Hence, from the maximality ofT, we havev∈T−10. SinceP is the metric projection ofH ontoT−10, we obtain
lim sup
n→∞
u−Pu,Jrnxn−Pu=lim
i→∞
u−Pu,Jrnixni−Pu= u−Pu,v−Pu ≤0. (3.16)
That is, (3.14) holds.
Finally, to prove thatxn→p, we applyLemma 2.3to get xn+1−Pu 2≤ βn
xn−Pu+δn
yn−Pu 2+ 2αn
u−Pu,xn+1−Pu
≤
βn xn−Pu +δn xn−Pu +δnσn2+ 2αnu−Pu,xn+1−Pu
=
1−αn xn−Pu +δnσn2+ 2αnu−Pu,xn+1−Pu
≤
1−αn xn−Pu 2+ 2αnu−Pu,xn+1−Pu+Mσn,
(3.17)
whereM >0 is some constant such that 2(1−αn)δnxn−Pu+δ2nσn≤M. An applica- tion ofLemma 2.4yields thatxn−Pu →0. This completes the proof.
Remark 3.2. It is clear that the algorithm (3.1) includes the algorithm (1.2) as a special case. Our result can be considered as a complement of Kamimura and Takahashi [7] and others.
4. Applications
Let f :H→(−∞,∞] be a proper lower semicontinuous convex function. Then we can define the subdifferential∂ f of f by
∂ f(x)=
z∈H:f(y)≥ f(x) +y−x,z ∀y∈H (4.1)
for allx∈H. It is well known that∂ f is a maximal monotone operator ofHinto itself;
see Minty [11] and Rockafellar [12,13].
In this section, we investigate our algorithm in the case ofT=∂ f. Our discussion fol- lows Rockafellar [14, Section 4]. IfT=∂ f, the algorithm (3.1) is reduced to the following algorithm:
yn≈arg min
z∈H
f(z) + 1 2rn
z−xn 2 , xn+1=αnu+βnxn+δnyn, n∈N,
(4.2) with the following criterion:
d0,Sn yn
≤σn
rn, (4.3)
where∞n=0σn<∞,Sn(z)=∂ f(z) + (z−xn)/rn, andd(0,A)=inf{x:x∈A}. About (4.3), the following lemma was proved in Rockafellar [2, Proposition 3].
Lemma 4.1. Ifynis chosen according to criterion (4.3), thenyn−Jrnxn ≤σnholds, where Jrn=(I+rn∂ f)−1.
Theorem 4.2. Let f :H→(−∞,∞] be a proper lower semicontinuous convex function.
Assume{αn},{βn},{δn}, and{rn}satisfy the same conditions (i)–(iv) as inTheorem 3.1.
If (∂ f)−10= ∅, then{xn}defined by (4.2) with criterion (4.3) converges strongly tov∈H, which is the minimizer of f nearest tou.
Proof. Puttinggn(z)=f(z) +z−xn2/2rn, we obtain
∂gn(z)=∂ f(z) + 1 rn
z−xn
=Sn(z) (4.4)
for allz∈H andJrnxn=(I+rn∂ f)−1xn=arg minz∈Hgn(z). It follows fromTheorem 3.1 andLemma 4.1that{xn}converges strongly tov∈Hand f(v)=minz∈Hf(z). This com-
pletes the proof.
Next we consider a variational inequality. LetCbe a nonempty closed convex subset ofHand letTbe a single-valued operator ofCintoH. We denote by VI(C,T) the set of solutions of the variational inequality, that is,
VI(C,T)=
w∈X:s−w,Tw ≥0,∀s∈C. (4.5) A single-valued operatorT is called semicontinuous ifT is continuous from each line segment ofCtoHwith the weak topology. LetFbe a single-valued monotone and semi- continuous operator ofCintoH and letNCzbe the normal cone toCatz∈C, that is, NCz= {w∈H:z−s,w ≥0,∀s∈C}. Letting
Az=
⎧⎨
⎩
Fz+NCz, z∈C,
∅, z∈H\C, (4.6)
we have thatAis a maximal monotone operator (see Rockafellar [14, Theorem 3]). We can also check that 0∈Avif and only ifv∈VI(C,F) and thatJrx=VI(C,Fr,x) for all r >0 andx∈H, whereFr,xz=Fz+ (z−x)/rfor allz∈C. Then we have the following result.
Corollary 4.3. LetFbe a single-valued monotone and semicontinuous operator ofCinto H. For fixedu∈H, let the sequence{xn}be generated by
yn≈VIC,Frn,xn
,
xn+1=αnu+βnxn+δnyn. (4.7) Here the criterion for the approximate computation ofynin (4.7) will be
yn−VIC,Frn,xn ≤σn, (4.8)
where∞n=0σn<∞. Assume{αn},{βn},{δn}, and{rn}satisfy the same conditions (i)–(iv) as inTheorem 3.1. If VI(C,F)= ∅, then{xn}defined by (4.7) with criterion (4.8) converges strongly to the point of VI(C,F) nearest tou.
References
[1] B. Martinet, “R´egularisation d’in´equations variationnelles par approximations successives,” Re- vue Franc¸aise d’Automatique et Informatique. Recherche Op´erationnelle, vol. 4, pp. 154–158, 1970.
[2] R. T. Rockafellar, “Monotone operators and the proximal point algorithm,” SIAM Journal on Control and Optimization, vol. 14, no. 5, pp. 877–898, 1976.
[3] H. Br´ezis and P.-L. Lions, “Produits infinis de r´esolvantes,” Israel Journal of Mathematics, vol. 29, no. 4, pp. 329–345, 1978.
[4] O. G¨uler, “On the convergence of the proximal point algorithm for convex minimization,” SIAM Journal on Control and Optimization, vol. 29, no. 2, pp. 403–419, 1991.
[5] G. B. Passty, “Ergodic convergence to a zero of the sum of monotone operators in Hilbert space,”
Journal of Mathematical Analysis and Applications, vol. 72, no. 2, pp. 383–390, 1979.
[6] M. V. Solodov and B. F. Svaiter, “Forcing strong convergence of proximal point iterations in a Hilbert space,” Mathematical Programming, vol. 87, no. 1, pp. 189–202, 2000.
[7] S. Kamimura and W. Takahashi, “Approximating solutions of maximal monotone operators in Hilbert spaces,” Journal of Approximation Theory, vol. 106, no. 2, pp. 226–240, 2000.
[8] T. Suzuki, “Strong convergence of Krasnoselskii and Mann’s type sequences for one-parameter nonexpansive semigroups without Bochner integrals,” Journal of Mathematical Analysis and Ap- plications, vol. 305, no. 1, pp. 227–239, 2005.
[9] W. V. Petryshyn, “A characterization of strict convexity of Banach spaces and other uses of dual- ity mappings,” Journal of Functional Analysis, vol. 6, no. 2, pp. 282–291, 1970.
[10] H.-K. Xu, “Another control condition in an iterative method for nonexpansive mappings,” Bul- letin of the Australian Mathematical Society, vol. 65, no. 1, pp. 109–113, 2002.
[11] G. J. Minty, “On the monotonicity of the gradient of a convex function,” Pacific Journal of Math- ematics, vol. 14, pp. 243–247, 1964.
[12] R. T. Rockafellar, “Characterization of the subdifferentials of convex functions,” Pacific Journal of Mathematics, vol. 17, pp. 497–510, 1966.
[13] R. T. Rockafellar, “On the maximal monotonicity of subdifferential mappings,” Pacific Journal of Mathematics, vol. 33, pp. 209–216, 1970.
[14] R. T. Rockafellar, “On the maximality of sums of nonlinear monotone operators,” Transactions of the American Mathematical Society, vol. 149, no. 1, pp. 75–88, 1970.
Yonghong Yao: Department of Mathematics, Tianjin Polytechnic University, Tianjin 300160, China Email address:[email protected]
Rudong Chen: Department of Mathematics, Tianjin Polytechnic University, Tianjin 300160, China Email address:[email protected]
Special Issue on
Time-Dependent Billiards
Call for Papers
This subject has been extensively studied in the past years for one-, two-, and three-dimensional space. Additionally, such dynamical systems can exhibit a very important and still unexplained phenomenon, called as the Fermi acceleration phenomenon. Basically, the phenomenon of Fermi accelera- tion (FA) is a process in which a classical particle can acquire unbounded energy from collisions with a heavy moving wall.
This phenomenon was originally proposed by Enrico Fermi in 1949 as a possible explanation of the origin of the large energies of the cosmic particles. His original model was then modified and considered under different approaches and using many versions. Moreover, applications of FA have been of a large broad interest in many different fields of science including plasma physics, astrophysics, atomic physics, optics, and time-dependent billiard problems and they are useful for controlling chaos in Engineering and dynamical systems exhibiting chaos (both conservative and dissipative chaos).
We intend to publish in this special issue papers reporting research on time-dependent billiards. The topic includes both conservative and dissipative dynamics. Papers dis- cussing dynamical properties, statistical and mathematical results, stability investigation of the phase space structure, the phenomenon of Fermi acceleration, conditions for having suppression of Fermi acceleration, and computational and numerical methods for exploring these structures and applications are welcome.
To be acceptable for publication in the special issue of Mathematical Problems in Engineering, papers must make significant, original, and correct contributions to one or more of the topics above mentioned. Mathematical papers regarding the topics above are also welcome.
Authors should follow the Mathematical Problems in Engineering manuscript format described at http://www .hindawi.com/journals/mpe/. Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking System athttp://
mts.hindawi.com/according to the following timetable:
Manuscript Due March 1, 2009 First Round of Reviews June 1, 2009 Publication Date September 1, 2009
Guest Editors
Edson Denis Leonel,Department of Statistics, Applied Mathematics and Computing, Institute of Geosciences and Exact Sciences, State University of São Paulo at Rio Claro, Avenida 24A, 1515 Bela Vista, 13506-700 Rio Claro, SP, Brazil; [email protected]
Alexander Loskutov,Physics Faculty, Moscow State University, Vorob’evy Gory, Moscow 119992, Russia;
Hindawi Publishing Corporation http://www.hindawi.com
