Volume 2008, Article ID 598191,10pages doi:10.1155/2008/598191
Research Article
Approximate Proximal Point Algorithms for
Finding Zeroes of Maximal Monotone Operators in Hilbert Spaces
Yeol Je Cho,1Shin Min Kang,2and Haiyun Zhou3
1Department of Mathematics Education and the RINS, Gyeongsang National University, Chinju 660-701, South Korea
2Department of Mathematics and the RINS, Gyeongsang National University, Chinju 660-701, South Korea
3Department of Mathematics, Shijiazhuang Mechanical Engineering College, Shijiazhuang 050003, China
Correspondence should be addressed to Haiyun Zhou,[email protected] Received 1 March 2007; Accepted 27 November 2007
Recommended by H. Bevan Thompson
LetHbe a real Hilbert space,Ωa nonempty closed convex subset ofH, andT:Ω→2Ha maximal monotone operator withT−10/∅. LetPΩbe the metric projection ofHontoΩ. Suppose that, for any givenxn ∈ H,βn > 0, anden ∈ H, there existsxn ∈ Ωsatisfying the following set-valued mapping equation:xnen ∈xnβnTxnfor alln≥0, where{βn} ⊂ 0,∞withβn → ∞as n→ ∞and{en}is regarded as an error sequence such that∞
n0en2<∞. Let{αn} ⊂0,1be a real sequence such thatαn→0 asn→ ∞and∞
n0αn∞. For any fixedu∈Ω, define a sequence {xn}iteratively asxn1αnu 1−αnPΩxn−enfor alln≥0. Then{xn}converges strongly to a pointz∈T−10 asn→ ∞, wherezlimt→∞Jtu.
Copyrightq2008 Yeol Je Cho et al. 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 and preliminaries
LetH be a real Hilbert space with the inner product·,· and norm · . A setT ⊂H×His called a monotone operator onHifThas the following property:
x−x, y−y ≥0, ∀x, y,x, y∈T. 1.1 A monotone operatorT onHis said to be maximal monotone if it is not properly contained in any other monotone operator onH.Equivalently, a monotone operatorTis maximal monotone ifRItT H for allt >0. For a maximal monotone operatorT, we can define the resolvent
ofTby
Jt ItT−1, ∀t >0. 1.2 It is well known thatJt :H→DTis nonexpansive. Also we can define the Yosida approxima- tionTtby
Tt 1 t
I−Jt
, ∀t >0. 1.3
We know thatTtx∈TJtxfor allx∈H,Ttx ≤ |Tx|for allx∈DT,where|Tx|inf{y:y∈ Tx},andT−10FJtfor allt >0.
Throughout this paper, we assume thatΩis a nonempty closed convex subset of a real Hilbert spaceHandT:Ω→2H is a maximal monotone operator withT−10/∅.
It is well known that, for anyu∈H,there exists uniquelyy0∈Ωsuch that u−y0infu−y:y∈Ω
. 1.4
When a mappingPΩ :H →Ωis defined byPΩuy0in1.4, we callPΩthe metric projection of HontoΩ.The metric projectionPΩofHontoΩhas the following basic properties:
iPΩx−x, x−PΩx ≥0 for allx∈Ωandx∈H, iiPΩx−PΩy2≤ x−y, PΩx−PΩy for allx, y∈H, iiiPΩx−PΩy ≤ x−yfor allx, y∈H,
ivxn→x0weakly andPxn→y0strongly imply thatPx0y0.
Finding zeroes of maximal monotone operators is the central and important topic in nonlinear functional analysis. A classical method to solve the following set-valued equation:
0∈Tz, 1.5
whereT :Ω → 2H is a maximal monotone operator, is the proximal point algorithm which, starting with any pointx0∈H,updatesxn1iteratively conforming to the following recursion:
xn∈xn1βnTxn1, ∀n≥0, 1.6
where{βn} ⊂β,∞,β >0,is a sequence of real numbers. However, as pointed out in1, the ideal form of the algorithm is often impractical since, in many cases, solving the problem1.6 exactly is either impossible or as difficult as the original problem1.5. Therefore, one of the most interesting and important problems in the theory of maximal monotone operators is to find an efficient iterative algorithm to compute approximately zeroes ofT.
In 1976, Rockafellar2gave an inexact variant of the method
xnen1∈xn1βnTxn1, ∀n≥0, 1.7 where{en}is regarded as an error sequence. This method is called an inexact proximal point algo- rithm. It was shown that if∞
n0en<∞, then the sequence{xn}defined by1.7converges weakly to a zero ofT. G ¨uler3constructed an example showing that Rockafellar’s proximal point algorithm1.7does not converge strongly, in general. This gives rise to the following question.
Question 1. How to modify Rockafellar’s algorithm so that strong convergence is guaranteed?
Xu4gave one solution toQuestion 1. However, this requires that the error sequence {en}is summable, which is too strong. This gives rise to the following question.
Question 2. Is it possible to establish some strong convergence theorems under the weaker assumption on the error sequence{en}given in1.7?
It is our purpose in this paper to give an affirmative answer toQuestion 2under a weaker assumption on the error sequence{en}in Hilbert spaces. For this purpose, we collect some lemmas that will be used in the proof of the main results in the next section.
The first lemma is standard and it can be found in some textbooks on functional analysis.
Lemma 1.1. For allx, y∈Handλ∈0,1,
λx 1−λy2λx2 1−λy2−λ1−λx−y2. 1.8 Lemma 1.2see5, Lemma 1. For allu∈H, limt→∞Jtuexists and it is the point ofT−10 nearest tou.
Lemma 1.3see1, Lemma 2. For any givenxn ∈ H,βn > 0, anden ∈H, there existsxn ∈Ω conforming to the following set-valued mapping equation (in short, SVME):
xnen∈xnβnTxn, ∀n≥0. 1.9 Furthermore, for anyp∈T−10, one has
xn−p, xn−xnen ≥
xn−xn, xn−xnen ,
xn−en−p2≤xn−p2−xn−xn2en2. 1.10 Lemma 1.4see6, Lemma 1.1. Let{an},{bn}, and{cn}be three real sequences satisfying
an1≤ 1−tn
anbncn, ∀n≥0, 1.11
where{tn} ⊂0,1,∞
n0tn∞,bn◦tn, and∞
n0cn<∞.Thenan→0 asn→ ∞.
2. The main results
Now we give our main results in this paper.
Theorem 2.1. LetHbe a real Hilbert space,Ωa nonempty closed convex subset ofH, andT :Ω→2H a maximal monotone operator withT−10/∅.LetPΩbe the metric projection ofHontoΩ. Suppose that, for any givenxn∈H,βn>0, anden∈H, there existsxn∈Ωconforming to the SVME1.9, where {βn} ⊂0,∞withβn→∞asn→ ∞and∞
n0en2<∞. Let{αn}be a real sequence in0,1 such that
iαn→0 asn→ ∞, ii∞
n0αn∞.
For any fixedu∈Ω, define the sequence{xn}iteratively as follows:
xn1αnu 1−αn
PΩ
xn−en
, ∀n≥0. 2.1
Then{xn}converges strongly to a fixed pointzofT,wherezlimt→∞Jtu.
Proof
Claim 1. {xn}is bounded.
Fixp∈T−10 and setMmax{u−p2,x0−p2}.First, we prove that xn−p2≤Mn−1
j0
ej2, ∀n≥0. 2.2 Whenn0,2.2is true. Now, assume that2.2holds for somen≥0. We will prove that2.2 holds forn1. By using the iterative scheme2.1and Lemmas1.1and1.3, we have
xn1−p2 αnu−p2
1−αnPΩ
xn−en
−p2−αn
1−αnu−PΩ
xn−en2
≤αnM
1−αnxn−en−p2≤αnM
1−αnxn−p2en2
≤αnM 1−αn
Mn
j0
ej2Mn
j0
ej2.
2.3
By induction, we assert that
xn−p2≤Mn−1
j0
ej2< M∞
j0
ej2<∞, ∀n≥0. 2.4 This implies that{xn}is bounded and so is{Jβnxn}.
Claim 2. limn→∞u−z, xn1−z ≤0, wherezlimt→∞Jtu,which is guaranteed byLemma 1.2.
Noting thatT is maximal monotone,u−Jtu tTtu,Ttu ∈ TJtu,xn−Jβnxn βnTβnxn, Tβnxn∈TJβnxn, andβn→∞n→ ∞,we have
u−Jtu, Jβnxn−Jtu −t
Ttu, Jtu−Jβnxn
−t
Ttu−Tβnxn, Jtu−Jβnxn −t
Tβnxn, Jtu−Jβnxn
≤ − t βn
xn−Jβnxn, Jtu−Jβnxn
−→0 n−→ ∞, ∀t >0
2.5
and hence
n→∞lim
u−Jtu, Jβnxn−Jtu ≤0. 2.6
Note thatJβnxnen−Jβnxn ≤ en →0 asn→ ∞, and so it follows from2.6that
n→∞lim
u−Jtu, Jβn
xnen
−Jtu ≤0. 2.7
Note thatPΩxn−en−Jβnxnen ≤ en →0 asn→ ∞and so it follows from2.7that
n→∞lim
u−Jtu, PΩ
xn−en
−Jtu ≤0. 2.8
Sinceαn → 0 asn→ ∞, from2.1we have xn1−PΩ
xn−en
−→0 n−→ ∞. 2.9
It follows from2.8and2.9that
n→∞lim
u−Jtu, xn1−Jtu ≤0, ∀t >0, 2.10
and so, fromzlimt→∞Jtuand2.10, we have
n→∞lim
u−z, xn1−z ≤0. 2.11
Claim 3. xn→zasn→ ∞.
Observe that
1−αn PΩ
xn−en
−z
xn1−z
−αnu−z 2.12 and so
1−αn2PΩ
xn−en
−PΩz2≥xn1−z2−2αn
u−z, xn1−z , 2.13 which implies that
xn1−z2≤
1−αnxn−en−z22αn
u−z, xn1−z . 2.14 It follows fromLemma 1.3and2.14that
xn1−z2≤
1−αnxn−z2−
1−αnxn−xn2en22αn
u−z, xn1−z
≤
1−αnxn−z22αn
u−z, xn1−z en2. 2.15 Setσnmax{u−z, xn1−z ,0}.Thenσn → 0 asn → ∞. Indeed, by the definition ofσn, we see thatσn ≥ 0 for alln ≥0. On the other hand, by2.11, we know that for arbitrary > 0, there exists some fixed positive integerNsuch thatu−z, xn1−z ≤ for alln ≥ N. This implies that 0≤σn ≤for alln≥ N, and the desired conclusion follows. Setan xn−z2, bn2αnσn, andcnen2.Then2.15reduces to
an1≤ 1−αn
anbncn, ∀n≥0, 2.16
where∞
n0αn∞,bn◦αn, and∞
n0cn<∞. Thus it follows fromLemma 1.4thatan → 0 asn → 0, that is,xn→z∈T−10 asn→ ∞. This completes the proof.
Remark 2.2. The maximal monotonicity ofTis only used to guarantee the existence of solutions to the SVME1.9for any givenxn∈Handβn>0. If we assume thatT:Ω→2H is monotone need not be maximalandTsatisfies the range condition
DT Ω⊂
r>0
RIrT, 2.17
then for any givenxn ∈ Ωandβn > 0, we may findxn ∈Ωanden ∈Hsatisfying the SVME 1.9. Furthermore,Lemma 1.2also holds foru∈Ω, and henceTheorem 2.1still holds true for monotone operators which satisfy the range condition.
Following the proof lines ofTheorem 2.1, we can prove the following corollary.
Corollary 2.3. LetHbe a real Hilbert space,Ωa nonempty closed convex subset ofH, andS:Ω→Ω a continuous and pseudocontractive mapping with a fixed point inΩ. Suppose that, for any given xn∈Ω,βn>0, anden∈H, there existsxn∈Ωsuch that
xnen 1βn
xn−βnSxn, ∀n≥0, 2.18 whereβn→ ∞n→ ∞and{en}satisfies the condition∞
n0en2<∞. Let{αn} ⊂0,1be a real sequence such thatαn→0 asn→ ∞and∞
n0αn∞. For any fixedu∈Ω, define the sequence{xn} iteratively as follows:
xn1αnu 1−αn
PΩ
xn−en
, ∀n≥0. 2.19
Then{xn}converges strongly to a fixed pointzofS, wherezlimt→∞Jtu,andJt ItI−S−1 for allt >0.
Proof. LetT I−S. ThenT : Ω → 2H is continuous and monotone and satisfies the range condition
DT Ω⊂
r>0
RIrT. 2.20
Now we only need to verify the last assertion. For any y ∈ Ω andr > 0, define an operatorG:Ω→Ωby
Gx r
1rSx 1
1ry. 2.21
ThenG:Ω→Ωis continuous and strongly pseudocontractive. By Kamimura et al.7, Corol- lary 1,Ghas a unique fixed pointxinΩ, that is,x r/1rSx1/1ry,which implies thaty∈RIrTfor allr >0. In particular, for any givenxn∈Ωandβn>0, there existxn∈Ω anden∈Hsuch that
xnenxnβnT xn, ∀n≥0, 2.22 which means that
xnen 1βn
xn−βnS xn, ∀n≥0, 2.23 and the relation2.18follows. The reminder of proof is the same as in the corresponding part ofTheorem 2.1. This completes the proof.
Remark 2.4. InCorollary 2.3, we do not know wether the continuity assumption onScan be dropped or not.
Remark 2.5. InTheorem 2.1, if the operatorTis defined on the whole spaceH, then the metric projection mappingPΩis not needed.
Remark 2.6. Our convergence results are different from those results obtained by Kamimura et al.7.
Theorem 2.7. LetHbe a real Hilbert space,Ωa nonempty closed convex subset ofH, andT :Ω→2H a maximal monotone operator withT−10/∅.Suppose that, for any givenxn∈H,βn>0, anden∈H, there existsxn∈Ωconforming to the following relation:
xnen∈xnβnT xn, ∀n≥0, 2.24 where limn→∞βn >0 and∞
n0en2 <∞. Let{αn}be a sequence in0,1with limn→∞αn <1 and define the sequence{xn}iteratively as follows:
x0∈Ω
xn1αnxn 1−αn
PΩ
xn−en
, ∀n≥0. 2.25
Then{xn}converges weakly to a pointp∈T−10.
Proof
Claim 1. {xn}is bounded.
SinceT−10/∅,we can take somew∈T−10. By using2.25and Lemmas1.1and1.3, we obtain
xn1−w2
αnxn−w2
1−αnPΩ
xn−en
−w2−αn
1−αnxn−PΩ
xn−en2
≤αnxn−w2
1−αnxn−en−w2
≤αnxn−w2
1−αnxn−w2−
1−αnxn−xn2en2 xn−w2−
1−αnxn−xn2en2
≤xn−w2en2
2.26
and so2.26together with∞
n0en2 < ∞implies that limn→∞xn−w2 exists. Therefore, {xn}is bounded.
Claim 2. xn−Jβnxn→0 asn→ ∞.
It follows from2.26that
1−αnxn−xn2≤xn−w2−xn1−w2en2 2.27 and so2.26together with limn→∞αn<1 implies that
xn−xn−→0 n−→ ∞. 2.28
SincexnJβnxnenandJβn is nonexpansive, we have
xn−Jβnxn≤xn−xnxn−Jβnxn≤xn−xnen−→0 2.29 asn → ∞and consequently,xn−Jβnxn → 0 asn → ∞.
Claim 3. {xn}converges weakly to a pointp∈T−10 asn→ ∞.
Setyn Jβnxn and let p ∈ H be a weak subsequential limit of {xn} such that {xnj} converges weakly to a pointpasj → ∞. Thus it follows that{ynj}converges weakly topas j→ ∞. Observe that
yn−J1ynI−J1
ynT1yn≤inf
z:z∈Tyn
Tβnxn xn−yn
βn
. 2.30
By assumption limn→∞βn>0,we have
yn−J1yn−→0 n−→ ∞. 2.31 SinceJ1 is nonexpansive, by Browder’s demiclosedness principle, we assert thatp∈FJ1
T−10.Now Opial’s condition ofH guarantees that {xn}converges weakly top ∈ T−10as n→ ∞. This completes the proof.
FromTheorem 2.7and the same proof ofCorollary 2.3, we have the following corollary.
Corollary 2.8. LetHbe a real Hilbert space,Ωa nonempty closed convex subset ofH, andU:Ω→Ω a continuous and pseudocontractive mapping with a fixed point. SetT I−U.Suppose that, for any givenxn∈Ω,βn>0, anden∈H, there existsxn∈Ωsuch that
xnen 1βn
xn−βnUxn, ∀n≥0. 2.32 Define the sequence{xn}iteratively as follows:
x0∈Ω, xn1αnxn
1−αn PΩ
xn−en
, ∀n≥0, 2.33
where{αn} ⊂0,1with limn→∞αn <1,{βn} ⊂ 0,∞with limn→∞βn > 0, and{en} ⊂H with ∞
n0en2<∞. Then{xn}converges weakly to a fixed pointpofU.
3. Applications
We can apply Theorems2.1and2.7to find a minimizer of a convex functionf. LetHbe a real Hilbert space andf :H →−∞,∞a proper convex lower semicontinuous function. Then the subdifferential∂foffis defined as follows:
∂fz
v∗∈H:fy≥fz
y−z, v∗ , y∈H
, ∀z∈ H. 3.1
Theorem 3.1. LetH be a real Hilbert space andf : H →−∞,∞a proper convex lower semicon- tinuous function. Suppose that, for anyxn ∈ H,βn > 0, and en ∈ H, there existsxn conforming to
xnen∈xnβn∂f xn
, ∀n≥0, 3.2
where{βn}is a sequence in0,∞with βn → ∞n → ∞and ∞
n0en2 < ∞. Let{αn} be a sequence in0,1such thatαn →0n→ ∞and∞
n0αn∞. For any fixedu∈H,let{xn}be the sequence generated by
u, x0∈H, xnarg min
z∈H
fz 1
2βn
z−xn−en2 , xn1αnu
1−αn
xn−en
, ∀n≥0.
3.3
If ∂f−10/∅, then{xn}converges strongly to the minimizer offnearest tou.
Proof. Sincef :H → −∞,∞is a proper convex lower semicontinuous function, by2, the subdifferential∂foffis a maximal monotone operator. Noting that
xnarg min
z∈H
fz 1
2βn
z−xn−en2
3.4
is equivalent to
0∈∂f xn
1 βn
xn−xn−en
, 3.5
we have
xnen∈xnβn∂f xn
, ∀n≥0. 3.6
Therefore, usingTheorem 2.1, we have the desired conclusion. This completes the proof.
Theorem 3.2. LetH be a real Hilbert space andf : H →−∞,∞a proper convex lower semicon- tinuous function. Suppose that, for any givenxn ∈H,βn>0, anden∈H, there existsxn ∈H such that
xnen∈xnβn∂f xn
, ∀n≥0, 3.7
where{βn}is a sequence in0,∞with limn→∞βn>0 and∞
n0en2 <∞. Let{αn}be a sequence in0,1with limn→∞αn<1 and let{xn}be the sequence generated by
x0∈H, xnarg min
z∈H
fz 1
2βnz−xn−en2 , xn1αnxn
1−αn
xn−en
, ∀n≥0.
3.8
If∂f−10/∅, then{xn}converges weakly to the minimizer offnearest tou.
Proof. As shown in the proof lines ofTheorem 3.1,∂f:H →His a maximal monotone opera- tor, and so the conclusion ofTheorem 3.2follows fromTheorem 2.7.
Acknowledgment
The authors are grateful to the anonymous referee for his helpful comments which improved the presentation of this paper.
References
1J. Eckstein, “Approximate iterations in Bregman-function-based proximal algorithms,” Mathematical Programming, vol. 83, no. 1, pp. 113–123, 1998.
2R. T. Rockafellar, “Monotone operators and the proximal point algorithm,” SIAM Journal on Control and Optimization, vol. 14, no. 5, pp. 877–898, 1976.
3O. 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.
4H.-K. Xu, “Iterative algorithms for nonlinear operators,” Journal of the London Mathematical Society, vol. 66, no. 1, pp. 240–256, 2002.
5R. E. Bruck Jr., “A strongly convergent iterative solution of 0∈Uxfor a maximal monotone operator Uin Hilbert space,” Journal of Mathematical Analysis and Applications, vol. 48, no. 1, pp. 114–126, 1974.
6L. S. Liu, “Ishikawa and Mann iterative process with errors for nonlinear strongly accretive mappings in Banach spaces,” Journal of Mathematical Analysis and Applications, vol. 194, no. 1, pp. 114–125, 1995.
7S. Kamimura, S. H. Khan, and W. Takahashi, “Iterative schemes for approximating solutions of relations involving accretive operators in Banach spaces,” in Fixed Point Theory and Applications, Vol. 5, Y. J. Cho, J. K. Kim, and S. M. Kang, Eds., pp. 41–52, Nova Science Publishers, Hauppauge, NY, USA, 2004.
