Strong and Weak Convergence of the Modified Proximal Point Algorithms in Hilbert Space

Volume 2010, Article ID 240450,11pages doi:10.1155/2010/240450

Research Article

Strong and Weak Convergence of the Modified Proximal Point Algorithms in Hilbert Space

Xinkuan Chai,

Bo Li,

and Yisheng Song

1College of Mathematics and Information Science, Henan Normal University, XinXiang 453007, China

2School of Mathematics and Statistics, AnYang Normal University, AnYang 455000, China

Correspondence should be addressed to Yisheng Song,[email protected] Received 26 October 2009; Revised 25 November 2009; Accepted 10 December 2009 Academic Editor: Tomonari Suzuki

Copyrightq2010 Xinkuan Chai 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.

For a monotone operatorT, we shall show weak convergence of Rockafellar’s proximal point algorithm to some zero ofT and strong convergence of the perturbed version of Rockafellar’s toPZuunder some relaxed conditions, wherePZis the metric projection fromHontoZT⁻¹0.

Moreover, our proof techniques are simpler than some existed results.

1. Introduction

Throughout this paper, letHbe a real Hilbert space with inner product·,·and norm · , and letIbe on identity operator inH. We shall denote byNthe set of all positive integers, by Zthe set of all zeros ofT, that is,Z T⁻¹0 {x ∈DT; 0∈ Tx}and byFTthe set of all fixed points ofT, that is,FT {x∈E;Txx}. When{x_n}is a sequence inE, thenx_n → x resp.,xn x,xn x∗ will denote strongresp., weak, weak^∗convergence of the sequence {xn}tox.

LetT be an operator with domainDTand rangeRTinH. Recall thatT is said to be monotone if

x−y, x−y

≥0, ∀x, y∈DT, x ∈Tx, y ∈Ty. 1.1

A monotone operatorT is said to be maximal monotone ifT is monotone andRIrT H for allr >0.

In fact, theory of monotone operator is very important in nonlinear analysis and is connected with theory of differential equations. It is well known see 1 that many physically significant problems can be modeled by the initial-value problems of the form

xt Txt 0,

x0 x0, 1.2

where T is a monotone operator in an appropriate space. Typical examples where such evolution equations occur can be found in the heat and wave equations or Schrodinger equations. On the other hand, a variety of problems, including convex programming and variational inequalities, can be formulated as finding a zero of monotone operators. Then the problem of finding a solutionx∈Hwith 0∈Txhas been investigated by many researchers;

see, for example, Bruck 2, Rockafellar3, Br´ezis and Lions 4, Reich5,6, Nevanlinna and Reich7, Bruck and Reich8, Jung and Takahashi9, Khang10, Minty11, Xu12, and others. Some of them dealt with the weak convergence of1.4and others proved strong convergence theorems by imposing strong assumptions onT.

One popular method of solving 0∈Txis the proximal point algorithm of Rockafellar 3which is recognized as a powerful and successful algorithm in finding a zero of monotone operators. Starting from any initial guessx0 ∈H, this proximal point algorithm generates a sequence{xk}given by

xk1 J_c^T_kxkek, 1.3

where J_r^T IrT⁻¹ for all r > 0 is the resolvent of T on the space H. Rockafellar’s 3 proved the weak convergence of his algorithm 1.3 provided that the regularization sequence {ck} remains bounded away from zero and the error sequence {ek} satisfies the condition _∞

k0e_k < ∞. G ¨uler’s example 13 however shows that in an infinite- dimensional Hilbert space, Rochafellar’s algorithm 1.3 has only weak convergence.

Recently several authors proposed modifications of Rochafellar’s proximal point algorithm 1.3to have strong convergence. For examples, Solodov and Svaiter14and Kamimura and Takahashi15studied a modified proximal point algorithm by an additional projection at each step of iteration. Lehdili and Moudafi16obtained the convergence of the sequence {x_k}generated by the algorithm

xk1J_λ^T_k^kxk, k≥0, 1.4

whereTkμkIT, μk>0,is viewed as a Tikhonov regularization ofT. Using the technique of variational distance, Lehdili and Moudafi16were able to prove convergence theorems for the algorithm1.4and its perturbed version, under certain conditions imposed upon the sequences{λk}and{μk}. For a maximal monotone operatorT, Xu12and Song and Yang 17 used the technique of nonexpansive mappings to get convergence theorems for{x_k} defined by the perturbed version of the algorithm1.4:

xk1J_r^T_ktku 1−tkxk. 1.5

In this paper, under more relaxed conditions on the sequences{rk}and{tk}, we shall show that the sequence{x_k}generated by1.5converges strongly toP_Zu∈T⁻¹0whereP_Z is the metric projection fromH ontoZand the sequence {xk} generated by1.3 weakly converges to some x^∗ ∈ T⁻¹0. Moreover, our proof techniques are simpler than those of Lehdili and Moudafi16, Xu12, and Song and Yang17.

2. Preliminaries and Basic Results

Let T be a monotone operator with Z /∅. We useJ_r^T and Ar to denote the resolvent and Yosida’s approximation ofT, respectively. Namely,

J_r^T IrT⁻¹, Ar I−J_r^T

r , r >0. 2.1

ForJ_r^T andAr, the following is well known. For more details, see18, Pages 369–400 or3,19.

iA_rx∈TJ_r^Txfor allx∈RIrT;

iiA_rx ≤ |Tx|inf{y;y∈Tx}for allx∈DT∩RIrT;

iiiJ_r^T :RIrT → DIrT DTis a single-valued nonexpansive mapping for eachr >0i.e.,J_r^Tx−J_r^Ty ≤ x−yfor allx, y∈RIrT;

ivZT⁻¹0FJ_r^T {x∈DJr;J_r^Txx}is closed and convex;

v The Resolvent IdentityForr >0 andt >0 andx∈E,

J_r^TxJ_t^T t

rx

1− t r

J_r^Tx

. 2.2

In the rest of this paper, it is always assumed thatZis nonempty so that the metric projection PZ from H onto Z is well defined. It is known that PZ is nonexpansive and characterized by the inequality: givenx∈Handv∈Z; thenvPZxif and only if

x−v, y−v ≤0, ∀y∈Z. 2.3

In order to facilitate our investigation in the next section we list a useful lemma.

Lemma 2.1 see Xu 20, Lemma 2.5. Let {a_k} be a sequence of nonnegative real numbers satisfying the property:

ak1≤1−λkakλkβkσk, ∀k≥0, 2.4

where{λ_k},{β_k}, and{σ_k}satisfy the conditions (i)_∞

k0λ_k∞; (ii) either lim sup_{k→ ∞}β_k≤0 or _∞

k0|λkβk|<∞; (iii)σk≥0 for allkand_∞

k0σk<∞.Then{ak}converges to zero ask → ∞.

3. Strongly Convergence Theorems

LetTbe a monotone operator on a Hilbert spaceH. ThenJ_r^Tis a single-valued nonexpansive mapping fromRIrTtoDIrT DT∩DI DT. WhenKis a nonempty closed convex subset ofHsuch thatDT ⊂ K ⊂ RIrTfor allr > 0 hereDTis closure of DT, then we havetku 1−tkxk∈K ⊂RIrkTforu, xk∈Kand allk ∈N, and hence the following iteration is well defined

xk1J_r^T_ktku 1−tkxk. 3.1 Next we will show strong convergence of{x_k}defined by3.1to find a zero ofT. For reaching this objective, we always assumeZT⁻¹0/∅in the sequel.

Theorem 3.1. LetT be a monotone operator on a Hilbert spaceHwithZ T⁻¹0/∅. Assume that Kis a nonempty closed convex subset ofHsuch thatDT⊂K ⊂RIrTfor allr >0 and for an anchor pointu∈Kand an initial valuex0 ∈K,{xk}is iteratively defined by3.1. If{tk} ⊂0,1 and{rk} ⊂0,∞satisfy

ilim_{k→ ∞}tk0;

ii_∞

k0tk∞;

iiilim_{k→ ∞}r_k∞,

then the sequence{x_k}converges strongly toP_Zu, whereP_Zis the metric projection fromHontoZ.

Proof. The proof consists of the following steps:

Step 1. The sequence{x_k}is bounded. Lety_kt_ku1−t_kx_k, thenx_k1 J_r^T_ky_kand for some z∈T⁻¹0FJ_r^T, we have

x_k1−zJ_r^T_ky_k−z≤y_k−zt_ku 1−t_kx_k−z

≤t_ku−z 1−t_kx_k−z

≤max{xk−z,u−z}

...

≤max{x0−z,u−z}.

3.2

So, the sequences{xk},{yk}, and{J_r^T_kyk}are bounded.

Step 2. lim_{k→ ∞}xk−J_r^Txk0 for eachr >0. Since

x_k1−J_r^Tx_k1J_r^T_ky_k−J_r^TJ_r^T_ky_k

I−J_r^T J_r^T_ky_k rA_rJ_r^T_ky_k≤rTJ_r^T_ky_k≤rA_rky_k ryk−J_r^T_kyk

rk −→0 k−→ ∞,

3.3

we have

klim→ ∞

x_k−J_r^Tx_k0. 3.4

Step 3. lim sup_{k→ ∞}u−P_Zu, x_k−P_Zu ≤0.Indeed, we can take a subsequence{x_ki}of{x_k} such that

lim sup

k→ ∞ u−P_Su, x_k−P_Su lim

i→ ∞u−P_Su, x_ki−P_Su. 3.5

We may assume thatx_ki x^∗by the reflexivity of Hand the boundedness of{x_k}. Then x^∗∈ZT⁻¹0FJ_r^T. In fact, since

x_ki−J_r^Tx^∗2x_ki−x^∗x^∗−J_r^Tx^∗2 xki−x^∗22

xki−x^∗, x^∗−J_r^Tx^∗

x^∗−J_r^Tx^∗2, xki−J_r^Tx^∗xki−J_r^TxkiJ_r^Txki−J_r^Tx^∗

≤xki−J_r^TxkiJ_r^Txki−J_r^Tx^∗

≤xki−J_r^Txkixki−x^∗,

3.6

then, for some constantL >0, we have xki −x^∗22

xki−x^∗, x^∗−J_r^Tx^∗

x^∗−J_r^Tx^∗2 xki −J_r^Tx^∗2≤xki−J_r^Txkixki−x^{∗ 2}

x_ki−J_r^Tx_ki2x_ki −x^∗ x_ki−J_r^Tx_kix_ki−x^∗2≤Lx_ki−J_r^Tx_kix_ki−x^∗2. 3.7

Thus,

2x_ki−x^∗, x^∗−J_r^Tx^∗x^∗−J_r^Tx^∗2≤Lx_ki−J_r^Tx_ki. 3.8 Take i → ∞ on two sides of the above equation by means of 3.4, we must have x^∗−J_r^Tx^∗20. So,x^∗∈Z. Hence, noting the projection inequality2.3, we obtain

lim sup

k→ ∞ u−P_Zu, x_k−P_Zu lim

i→ ∞u−P_Zu, x_ki−P_Zuu−P_Zu, x^∗−P_Zu ≤0. 3.9

Step 4. xk → PZu. Indeed,

x_k1−P_Zu²J_r^T_kt_ku 1−t_kx_k−P_Zu²

J_r^T_kyk−PZu²≤yk−PZu²

≤ tku−PZu 1−tkxk−PZu²

≤1−tk²xk−PZu²t²_ku−PZu²2tk1−tku−PZu, xk−PZu.

3.10

Therefore,

xk1−PZu² ≤1−tkxk−PZu²tkβk, 3.11

whereβktku−PZu²21−tku−PZu, xk−PZu.So, an application ofLemma 2.1onto 3.11yields the desired result.

Theorem 3.2. Let T,H,Z,K,{xk},{tk} be as Theorem 3.1, the condition (iii) lim_{k→ ∞}rk ∞ is replaced by the following condition:

∞ k0

|t_k1−t_k|<∞; 0<lim inf

k→ ∞ r_k, ^∞

k0

1− rk

r_k1

<∞. 3.12

Then the sequence{xk}converges strongly toPZu, wherePZis the metric projection fromHontoZ.

Proof. From the proof ofTheorem 3.1, we can observe that Steps1,3and4still hold. So we only need show toStep 2: lim_{k→ ∞}xk−J_r^Txk0 for eachr >0.

We first estimatexk1−xk.From the resolvent identity2.2, we have

J_r^T_kykJ_r^T_k−1 r_k−1

rk yk

1−r_k−1 rk

J_r^T_kyk

. 3.13

Therefore, for a constantM >0 withM≥max{u,x_k,J_r^T_ky_k,y_k},

x_k1−x_kJ_r^T_ky_k−J_r^T_k−1y_k−1≤ r_k−1

rk y_k

1− r_k−1 rk

J_r^T_ky_k−y_k−1

≤ rk−1

r_k

yk−yk−1

1− rk−1

r_k

J_r^T_kyk−yk−1

≤y_k−y_k−1 1−r_k−1

rk

J_r^T_ky_k−y_k

≤ |tk−tk−1|uxk−1 1−tkxk−xk−12M 1−rk−1

r_k

≤1−tkxk−xk−12M

|tk−tk−1| 1−r_k−1

rk

.

3.14

It follows fromLemma 2.1that

k→ ∞limxk1−xk0. 3.15

Asyk−J_r^T_kykyk−xk1 ≤tku−xk1 1−tkxk−xk1,then

klim→ ∞

y_k−J_r^T_ky_k0. 3.16

Since 0 <lim inf_{k→ ∞}rk, then there existsε >0 and a positive integerN >0 such that for all k > N,r_k≥ε. Thus for eachr >0, we also have

x_k1−J_r^Tx_k1J_r^T_ky_k−J_r^TJ_r^T_ky_k

I−J_r^T J_r^T_ky_k rA_rJ_r^T_ky_k≤rTJ_r^T_ky_k≤rA_rky_k ry_k−J_r^T_ky_k

rk ≤ r

εyk−J_r^T_kyk−→0 k−→ ∞;

3.17

we have lim_{k→ ∞}x_k−J_r^Tx_k0.

Corollary 3.3. LetH,{tk},{rk}, Zbe asTheorem 3.1or3.2. Suppose thatTis a maximal monotone operator onHand forx0, u∈H,{xk}is defined by3.1. Then the sequence{xk}converges strongly toP_Zu, whereP_Zis the metric projection fromHontoZ.

Proof. SinceT is a maximal monotone, thenTis monotone and satisfies the conditionDT⊂ HRIrTfor allr >0. PuttingKH, the desired result is reached.

Corollary 3.4. LetH,{t_k},{r_k}, Zbe asTheorem 3.1or3.2. Suppose thatTis a monotone operator onHsatisfying the conditionDT⊂RIrTfor allr >0 and forx0, u∈DT,{x_k}is defined by3.1. IfDTis convex, then the sequence{xk}converges strongly toPZu, wherePZis the metric projection fromHontoZ.

Proof. TakingKDT, followingTheorem 3.1or3.2, we easily obtain the desired result.

4. Weakly Convergence Theorems

For a monotone operatorT, ifDT⊂RIrTfor allr >0 andx0∈DT, then the iteration xk1 J_r^T_kxk k ∈ Nis well defined. Next we will show weak convergence of {xk} under some assumptions.

Theorem 4.1. LetT be a monotone operator on a Hilbert spaceHwithZ T⁻¹0/∅. Assume that DT⊂RIrTfor allr >0 and for an initial valuex0∈DT, iteratively define

xk1J_r^T_kxk. 4.1

If{r_k} ⊂0,∞satisfies

klim→ ∞rk∞, 4.2

then the sequence{x_k}converges weakly to somex^∗∈Z.

Proof. Takez∈ZT⁻¹0FJ_r^T, we have

xk1−zJ_r^T_kxk−z≤ xk−z. 4.3 Therefore,{xk−z}is nonincreasing and bounded below, and hence the limit lim_{k→ ∞}xk−z exists for eachz∈Z. Further,{x_k}is bounded. So we have

x_k1−J_r^Tx_k1J_r^T_kx_k−J_r^TJ_r^T_kx_k

I−J_r^T J_r^T_kx_k rA_rJ_r^T_kx_k≤rTJ_r^T_kx_k≤rA_rkx_k rxk−J_r^T_kxk

r_k rxk−xk1

r_k −→0 k−→ ∞.

4.4

Hence,

klim→ ∞

xk−J_r^Txk0. 4.5 As{x_k}is weakly sequentially compact by the reflexivity ofH, and hence we may assume that there exists a subsequence{xki}of{xk}such thatxki x^∗. Using the proof technique of Step 3inTheorem 3.1, we must have thatx^∗∈ZT⁻¹0.

Now we prove that{x_n}converges weakly tox^∗. Supposed that there exists another subsequence{x_kj}of{x_k}which weakly converges to somey ∈ K. We also havey ∈ Z T⁻¹0. Because lim_{k→ ∞}xk−zexists for eachz∈ZT⁻¹0 and

xkj−y²xkj−x^∗22

xkj−x^∗, x^∗−y

x^∗−y², xki−x^∗2xki −y²2

xki−y, y−x^∗

y−x^∗2,

4.6

thus,

klim→ ∞xk−y²lim sup

j→ ∞

xkj−y² lim sup

j→ ∞

xkj−x^∗22

xkj−x^∗, x^∗−y

x^∗−y²

≤ lim

k→ ∞xk−x^∗2−x^∗−y².

4.7

Similarly, we also have

klim→ ∞x_k−x^∗2≤ lim

k→ ∞x_k−y²−x^∗−y². 4.8

Adding up the above two equations, we must have−x^∗−y²≥0. So,x^∗y.

In a summary, we have proved that the set{xk}is weakly sequentially compact and each cluster point in the weak topology equals tox^∗ ∈ Z. Hence,{x_k}converges weakly to x^∗∈T⁻¹0. The proof is complete.

Theorem 4.2. LetT be a maximal monotone operator on a Hilbert spaceHwithZ T⁻¹0/∅. For an initial valuex0∈H, iteratively define

x_k1J_r^T_kx_ke_k. 4.9

If{rk} ⊂0,∞andek∈Hsatisfy

klim→ ∞r_k∞, ^∞

k0

e_k<∞, 4.10

then the sequence{xk}converges weakly to somex^∗∈Z.

Proof. Takez∈ZT⁻¹0FJ_r^Tandy_kx_ke_k, we have

xk1−zJ_r^T_kyk−z≤ xk−zek. 4.11 It follows from Liu21, Lemma 2that the limit lim_{k→ ∞}x_k−zexists for eachz ∈ Zand hence both{x_k}and{y_k}are bounded. So we have

x_k1−J_r^Tx_k1J_r^T_ky_k−J_r^TJ_r^T_ky_k

I−J_r^T J_r^T_ky_k rA_rJ_r^T_ky_k≤rTJ_r^T_ky_k≤rA_rky_k ryk−J_r^T_kyk

rk ry_k−x_k1

rk −→0 k−→ ∞.

4.12

Hence,

klim→ ∞

x_k−J_r^Tx_k0. 4.13

The remainder of the proof is the same asTheorem 4.1; we omit it.

Acknowledgments

The authors are grateful to the anonymous referee for his/her valuable suggestions which helps to improve this manuscript. This work is supported by Youth Science Foundation of Henan Normal University2008qk02 and by Natural Science Research Projects Basic Research Projectof Education Department of Henan Province2009B110011, 2009B110001.

References

1 E. Zeidler, Nonlinear Functional Analysis and Its Applications, Part II: Monotone Operators, Springer, Berlin, Germany, 1985.

2 R. 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, pp. 114–126, 1974.

3 R. T. Rockafellar, “Monotone operators and the proximal point algorithm,” SIAM Journal on Control and Optimization, vol. 14, no. 5, pp. 877–898, 1976.

4 H. Br´ezis and P.-L. Lions, “Produits infinis de r´esolvantes,” Israel Journal of Mathematics, vol. 29, no. 4, pp. 329–345, 1978.

5 S. Reich, “Weak convergence theorems for nonexpansive mappings in Banach spaces,” Journal of Mathematical Analysis and Applications, vol. 67, no. 2, pp. 274–276, 1979.

6 S. Reich, “Strong convergence theorems for resolvents of accretive operators in Banach spaces,”

Journal of Mathematical Analysis and Applications, vol. 75, no. 1, pp. 287–292, 1980.

7 O. Nevanlinna and S. Reich, “Strong convergence of contraction semigroups and of iterative methods for accretive operators in Banach spaces,” Israel Journal of Mathematics, vol. 32, no. 1, pp. 44–58, 1979.

8 R. E. Bruck and S. Reich, “A general convergence principle in nonlinear functional analysis,” Nonlinear Analysis: Theory, Methods & Applications, vol. 4, no. 5, pp. 939–950, 1980.

9 J. S. Jung and W. Takahashi, “Dual convergence theorems for the infinite products of resolvents in Banach spaces,” Kodai Mathematical Journal, vol. 14, no. 3, pp. 358–365, 1991.

10 D. B. Khang, “On a class of accretive operators,” Analysis, vol. 10, no. 1, pp. 1–16, 1990.

11 G. J. Minty, “On the monotonicity of the gradient of a convex function,” Pacific Journal of Mathematics, vol. 14, pp. 243–247, 1964.

12 H.-K. Xu, “A regularization method for the proximal point algorithm,” Journal of Global Optimization, vol. 36, no. 1, pp. 115–125, 2006.

13 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.

14 M. V. Solodov and B. F. Svaiter, “Forcing strong convergence of proximal point iterations in a Hilbert space,” Mathematical Programming. Series A, vol. 87, no. 1, pp. 189–202, 2000.

15 S. Kamimura and W. Takahashi, “Strong convergence of a proximal-type algorithm in a Banach space,” SIAM Journal on Optimization, vol. 13, no. 3, pp. 938–945, 2002.

16 N. Lehdili and A. Moudafi, “Combining the proximal algorithm and Tikhonov regularization,”

Optimization, vol. 37, no. 3, pp. 239–252, 1996.

17 Y. Song and C. Yang, “A note on a paper “A regularization method for the proximal point algorithm”,”

Journal of Global Optimization, vol. 43, no. 1, pp. 171–174, 2009.

18 J.-P. Aubin and I. Ekeland, Applied Nonlinear Analysis, Pure and Applied MathematicsNew York, John Wiley & Sons, New York, NY, USA, 1984.

19 W. Takahashi, Nonlinear Functional Analysis—Fixed Point Theory and Its Applications, Yokohama Publishers, Yokohama, Japan, 2000.

20 H.-K. Xu, “Strong convergence of an iterative method for nonexpansive and accretive operators,”

Journal of Mathematical Analysis and Applications, vol. 314, no. 2, pp. 631–643, 2006.

21 Q. Liu, “Iterative sequences for asymptotically quasi-nonexpansive mappings with error member,”

Journal of Mathematical Analysis and Applications, vol. 259, no. 1, pp. 18–24, 2001.