Báo cáo hóa học: "Research Article Iterative Algorithm for Approximating Solutions of Maximal Monotone Operators in Hilbert Spaces"

Hindawi Publishing Corporation Fixed Point Theory and Applications Volume 2007, Article ID 32870, 8 pages doi:10.1155/2007/32870

Research Article Iterative Algorithm for Approximating Solutions of Maximal Monotone Operators in Hilbert Spaces

Yonghong Yao and Rudong Chen

Received 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 that H is a real Hilbert space and T : H → 2H is a maximal monotone operator. A well-known method for solving the equation 0 ∈ Tv in a Hilbert space H is the proximal point algorithm: x1 = x ∈ H and

(1.1) n = 1,2,..., xn+1 = Jrnxn,

where {rn} ⊂ (0, ∞) and Jr = (I + rT)−1 for all r > 0. This algorithm was first introduced by Martinet [1]. Rockafellar [2] proved that if liminf n→∞ rn > 0 and T −10 (cid:6)= ∅, then the sequence {xn} defined by (1.1) converges weakly to an element of T −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. Let T : H → 2H be a maximal monotone operator. Let {xn} be a sequence defined as follows: x1 = u ∈ H and

(cid:2) 1 − αn

(cid:3) Jrnxn,

(1.2) n = 1,2,..., xn+1 = αnu +

(cid:4)∞

2 Fixed Point Theory and Applications

where {αn} ⊂ [0,1] and {rn} ⊂ (0, ∞) satisfy limn→∞ αn = 0, n=1 αn = ∞, and limn→∞ rn = ∞. If T −10 (cid:6)= ∅, then the sequence {xn} defined by (1.2) converges strongly to Pu, where P is the metric projection of H onto T −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 mapping U : H → H is said to be nonexpansive if (cid:8)Ux − U y(cid:8) ≤ (cid:8)x − y(cid:8) for all x, y ∈ H. We denote the set of all fixed points of U by F(U). A multivalued operator T : H → 2H with domain D(T) and range R(T) is said to be monotone if for each xi ∈ D(T) and yi ∈ Txi, i = 1,2, we have (cid:10)x1 − x2, y1 − y2(cid:11) ≥ 0.

A monotone operator T is said to be maximal if its graph G(T) = {(x, y) : y ∈ Tx} is not properly contained in the graph of any other monotone operator. Let I denote the identity operator on H and let T : H → 2H be a maximal monotone operator. Then we can define, for each r > 0, a nonexpansive single-valued mapping Jr : H → H by Jr = (I + rT)−1. It is called the resolvent (or the proximal mapping) of T. We also define the Yosida approximation Ar by Ar = (I − Jr)/r. We know that Arx ∈ TJrx and (cid:8)Arx(cid:8) ≤ inf {(cid:8)y(cid:8) : y ∈ Tx} for all x ∈ 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 space X and let {αn} be a sequence in [0,1] with 0 < liminf n→∞ αn ≤ limsupn→∞ αn < 1. Suppose xn+1 = αnxn + (1 − αn)zn for all integers n ≥ 0 and limsupn→∞((cid:8)zn+1 − zn(cid:8) − (cid:8)xn+1 − xn(cid:8)) ≤ 0. Then, limn→∞ (cid:8)zn − xn(cid:8) = 0.

(cid:6)

(cid:6)

(cid:5)

Lemma 2.2 (the resolvent identity). For λ,μ > 0, there holds the identity

(cid:5) 1 − μ λ

, (2.1) x ∈ X. x + Jλx = Jμ Jλx μ λ

(cid:7)

Lemma 2.3 (see [9]). Let E be a real Banach space. Then for all x, y ∈ E

(cid:8)x + y(cid:8)2 ≤ (cid:8)x(cid:8)2 + 2

(cid:8) y, j(x + y)

∀ j(x + y) ∈ J(x + y).

(2.2)

(cid:4)∞

n=0 sn = ∞,

(cid:4)∞

|sntn| < ∞.

n=0

Lemma 2.4 (see[10]). Let {an} be a sequence of nonnegative real numbers satisfying the property an+1 ≤ (1 − sn)an + sntn, n ≥ 0, where {sn} ⊂ (0,1) and {tn} are such that

(i) (ii) either limsupn→∞ tn ≤ 0 or Then {an} converges to zero.

Y. Yao and R. Chen 3

3. Main result

Let T : H → 2H be a maximal monotone operator and let Jr : H → H be the resolvent of T for each r > 0. Then we consider the following algorithm: for fixed u ∈ H and given x0 ∈ H arbitrarily, let the sequence {xn} is generated by

(3.1) yn ≈ Jrnxn, xn+1 = αnu + βnxn + δn yn,

where {αn}, {βn}, {δn} are three real numbers in [0,1] and {rn} ⊂ (0, ∞). Here the crite- rion for the approximate computation of yn in (3.1) will be

(cid:9) (cid:9) ≤ σn,

(cid:9) (cid:9)yn − Jrnxn

(cid:4)∞

(3.2)

n=0 σn < ∞.

where

(cid:4)∞

n=0 αn = ∞;

Theorem 3.1. Let T : H → 2H be 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 (iii) 0 < liminf n→∞ βn ≤ limsupn→∞ βn < 1; (iv) rn ≥ (cid:2) > 0 for all n and rn+1 − rn → 0(n → ∞).

(cid:9) (cid:9)

(cid:9) (cid:9)xn+1 − p

(cid:3)

(cid:9) (cid:9)

If T −10 (cid:6)= ∅, then {xn} defined by (3.1) under criterion (3.2) converges strongly to Pu, where P is the metric projection of H onto T −10. Proof. From T −10 (cid:6)= ∅, there exists p ∈ T −10 such that Js p = p for all s > 0. Then we have

(cid:9) (cid:9) (cid:9) (cid:9) + δn (cid:9) ≤ αn(cid:8)u − p(cid:8) + βn (cid:9)xn − p (cid:9) (cid:9) (cid:9) + δn (cid:9)xn − p ≤ αn(cid:8)u − p(cid:8) + βn (cid:9) (cid:9) (cid:9) + δn (cid:9)xn − p ≤ αn(cid:8)u − p(cid:8) + βn (cid:3)(cid:9) (cid:2) (cid:9)xn − p = αn(cid:8)u − p(cid:8) + 1 − αn

(cid:9) (cid:9)yn − p (cid:9) (cid:2) (cid:9)Jrnxn − p σn + (cid:9) (cid:9) (cid:9)xn − p (cid:9) + δnσn (cid:9) (cid:9) + δnσn.

(3.3)

n(cid:12)

(cid:11)

(cid:10)

(cid:9) (cid:9)

(cid:9) (cid:9) ≤ max

An induction gives that

(cid:8)u − p(cid:8),

(cid:9) (cid:9)x0 − p

(cid:9) (cid:9)xn − p

k=0

+ (3.4) σk

for all n ≥ 0. This implies that {xn} is bounded. Hence {Jrnxn} and {yn} are also bounded. Define a sequence {zn} by

(cid:2) 1 − βn

(cid:3) zn,

(3.5) n ≥ 0. xn+1 = βnxn +

4 Fixed Point Theory and Applications

Then we observe that

− xn+1 − βnxn 1 − βn

(cid:5)

(cid:6)

(cid:2)

(cid:3)

=

− αn

zn+1 − zn = xn+2 − βn+1xn+1

(3.6) yn+1 − yn δn+1 1 − βn+1 u + (cid:6) 1 − βn − δn + yn. 1 − βn+1 αn+1 1 − βn+1 (cid:5) δn+1 1 − βn+1 1 − βn

(cid:5)

(cid:6)

If rn−1 ≤ rn, from Lemma 2.2, using the resolvent identity (cid:6)

(cid:5) 1 − rn−1 rn

, (3.7) xn + Jrnxn = Jrn−1 Jrnxn rn−1 rn

(cid:5)

(cid:9) (cid:9)

(cid:9) (cid:9)Jrnxn − Jrn−1xn−1

(cid:6) (cid:9) (cid:9)Jrnxn − xn−1

we obtain

(cid:13) (cid:13)

≤

(cid:9) (cid:9).

(cid:9) (cid:9) ≤ rn−1 rn (cid:9) (cid:9)xn − xn−1

(cid:9) rn − rn−1 (cid:9) + rn (cid:13) (cid:13)rn−1 − rn

(cid:9) (cid:9)Jrnxn − xn−1

(cid:9) (cid:9)xn − xn−1 (cid:9) 1 (cid:9) + (cid:2)

(3.8)

(cid:9) (cid:9)

(cid:9) (cid:9) +

(cid:9) (cid:9)yn+1 − yn

(cid:9) (cid:9)Jrn+1xn+1 − Jrnxn

Similarly, we can prove that the last inequality holds if rn−1 ≥ rn.

(cid:9) (cid:9)yn − Jrnxn (cid:9) (cid:9).

≤ σn+1 + σn +

(cid:9) (cid:9)

(cid:9) (cid:9) −

(cid:3)

(cid:9) (cid:9)

(cid:9) (cid:9)

≤

(cid:13) (cid:13) (cid:13) (cid:13)

(3.9) On the other hand, from (3.2), we have (cid:9) (cid:9) (cid:9) (cid:9) + (cid:9)yn+1 − Jrn+1xn+1 (cid:9) ≤ (cid:9) (cid:9)Jrn+1xn+1 − Jrnxn

(cid:2) (cid:8)u(cid:8) +

(cid:9) (cid:9)yn

(cid:9) (cid:9)xn+1 − xn

(cid:9) (cid:9)

(cid:13) (cid:13) ×

Thus it follows from (3.5) that (cid:9) (cid:9) (cid:9)xn+1 − xn (cid:9)zn+1 − zn (cid:13) (cid:13) − αn (cid:13) (cid:13) +

(cid:9) (cid:9)xn+1 − xn

≤

δn+1 1 − βn+1 (cid:9) (cid:9) + σn+1 + σn − (3.10)

(cid:9) (cid:9)Jrn+1xn+1 − xn (cid:9) (cid:9) (cid:3) (cid:9) (cid:9)yn

(cid:13) (cid:13) ×

1 (cid:2) − αn + (cid:13) (cid:13) (cid:13) (cid:13) 1 − βn (cid:13) (cid:13)rn+1 − rn (cid:13) (cid:13) (cid:2) (cid:13) (cid:8)u(cid:8) + (cid:13) + σn+1 + σn

(cid:9) (cid:9),

(cid:9) (cid:9)Jrn+1xn+1 − xn

+ 1 − βn (cid:13) (cid:13)rn+1 − rn 1 (cid:2) αn+1 1 − βn+1 δn+1 1 − βn+1 αn+1 1 − βn+1 δn+1 1 − βn+1

(cid:9) (cid:9)xn+1 − xn

(cid:3)(cid:9) (cid:9)zn − xn

(cid:2) 1 − βn

(cid:9) (cid:9) = lim n→∞

(3.11) which implies that limsupn→∞((cid:8)zn+1 − zn(cid:8) − (cid:8)xn+1 − xn(cid:8)) ≤ 0. Hence, by Lemma 2.1, we have limn→∞ (cid:8)zn − xn(cid:8) = 0. Consequently, it follows from (3.5) that (cid:9) (cid:9) = 0. lim n→∞

(cid:9) (cid:9) ≤

(cid:9) (cid:9)xn − yn

On the other hand,

≤

(cid:9) (cid:9),

(cid:9) (cid:9)xn+1 − xn (cid:9) (cid:9)xn+1 − xn

(cid:9) (cid:9) + (cid:9) (cid:9) + αn

(cid:9) (cid:9) (cid:9) (cid:9)xn+1 − yn (cid:9) (cid:9) (cid:9) + βn (cid:9)u − yn

(cid:9) (cid:9)xn − yn

(3.12)

Y. Yao and R. Chen 5

(cid:15)

(cid:9) (cid:15) (cid:9)

and so, by (ii), (iii), (3.11), and (3.12), we have limn→∞ (cid:8)xn − yn(cid:8) = 0. It follows that

(cid:9) (cid:9) +

−→ 0.

(cid:14)(cid:9) (cid:9)xn − yn

(cid:14)(cid:9) (cid:9)xn − yn

(cid:9) (cid:9) + σn

(cid:9) (cid:9)Arnxn

(cid:9) (cid:9)yn − Jrnxn

≤ 1 (cid:2)

(cid:9) (cid:9) ≤ 1 rn

(3.13)

(cid:7)

(cid:8)

We next prove that

≤ 0,

(3.14) u − Pu,xn+1 − Pu limsup n→∞

(cid:8)

(cid:7)

where P is the metric projection of H onto T −10. To prove this, it is sufficient to show limsupn→∞(cid:10)u − Pu,Jrnxn − Pu(cid:11) ≤ 0, because xn+1 − Jrnxn → 0. Now there exists a subse- quence {xni

− Pu

(cid:8) .

} ⊂ {xn} such that (cid:7) u − Pu,Jrni xni

= limsup n→∞

(3.15) u − Pu,Jrnxn − Pu lim i→∞

(cid:7)

(cid:8)

(cid:7)

(cid:8)

Since {Jrnxn} is bounded, we may assume that {Jrni xni } converges weakly to some v ∈ H. Then it follows that v ∈ T −10. Indeed, since Arnxn ∈ TJrnxn and T is monotone, we have (cid:10)s − Jrni xni,s(cid:14) − Arni xni (cid:11) ≥ 0, where s(cid:14) ∈ Ts. From Arnxn → 0, we obtain (cid:10)s − v,s(cid:14)(cid:11) ≥ 0 whenever s(cid:14) ∈ Ts. Hence, from the maximality of T, we have v ∈ T −10. Since P is the metric projection of H onto T −10, we obtain

− Pu

= (cid:10)u − Pu,v − Pu(cid:11) ≤ 0.

= lim i→∞

(3.16) u − Pu,Jrnxn − Pu u − Pu,Jrni xni limsup n→∞

(cid:7)

(cid:2)

(cid:8)

(cid:3)(cid:9) (cid:9)

(cid:9) (cid:9)2 ≤

That is, (3.14) holds.

(cid:3)2 + 2αn

(cid:7)

(cid:8)

≤

Finally, to prove that xn → p, we apply Lemma 2.3 to get (cid:9) (cid:3) (cid:9)xn+1 − Pu u − Pu,xn+1 − Pu

=

≤

(cid:2)(cid:9) (cid:2) (cid:9)βn yn − Pu xn − Pu + δn (cid:9) (cid:9) (cid:9) (cid:9) (cid:2) (cid:3)2 + 2αn (cid:9) + δnσn (cid:9)xn − Pu (cid:9) + δn (cid:9)xn − Pu βn (cid:9) (cid:3)(cid:9) (cid:7) (cid:3)2 + 2αn (cid:2)(cid:2) (cid:9) + δnσn (cid:9)xn − Pu u − Pu,xn+1 − Pu 1 − αn (cid:9) (cid:3)(cid:9) (cid:2) (cid:8) (cid:7) (cid:9)2 + 2αn (cid:9)xn − Pu u − Pu,xn+1 − Pu 1 − αn

u − Pu,xn+1 − Pu (cid:8) (3.17)

nσn ≤ M. An applica- (cid:2)

+ Mσn,

where M > 0 is some constant such that 2(1 − αn)δn(cid:8)xn − Pu(cid:8) + δ2 tion of Lemma 2.4 yields that (cid:8)xn − Pu(cid:8) → 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

(cid:10)

(cid:11)

Let f : H → (−∞, ∞] be a proper lower semicontinuous convex function. Then we can define the subdifferential ∂ f of f by

(4.1) z ∈ H : f (y) ≥ f (x) + (cid:10)y − x,z(cid:11) ∀y ∈ H ∂ f (x) =

6 Fixed Point Theory and Applications

for all x ∈ H. It is well known that ∂ f is a maximal monotone operator of H into itself; see Minty [11] and Rockafellar [12, 13].

(cid:16)

(cid:17)

(cid:9) (cid:9)2

In this section, we investigate our algorithm in the case of T = ∂ f . Our discussion fol- lows Rockafellar [14, Section 4]. If T = ∂ f , the algorithm (3.1) is reduced to the following algorithm:

(cid:9) (cid:9)z − xn

, f (z) + yn ≈ arg min z∈H (4.2) n ∈ N, 1 2rn xn+1 = αnu + βnxn + δn yn,

(cid:2)

(cid:3)(cid:3)

with the following criterion:

(cid:2) 0,Sn

≤ σn rn

(cid:4)∞

n=0 σn < ∞, Sn(z) = ∂ f (z) + (z − xn)/rn, and d(0,A) = inf {(cid:8)x(cid:8) : x ∈ A}. About

(4.3) , d yn

= (I + rn∂ f )−1.

where (4.3), the following lemma was proved in Rockafellar [2, Proposition 3].

Lemma 4.1. If yn is chosen according to criterion (4.3), then (cid:8)yn − Jrnxn(cid:8) ≤ σn holds, where Jrn 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 in Theorem 3.1. If (∂ f )−10 (cid:6)= ∅, then {xn} defined by (4.2) with criterion (4.3) converges strongly to v ∈ H, which is the minimizer of f nearest to u.

(cid:3)

Proof. Putting gn(z) = f (z) + (cid:8)z − xn(cid:8)2/2rn, we obtain

(cid:2) z − xn

= Sn(z)

(4.4) ∂gn(z) = ∂ f (z) + 1 rn

for all z ∈ H and Jrnxn = (I + rn∂ f )−1xn = argminz∈H gn(z). It follows from Theorem 3.1 and Lemma 4.1 that {xn} converges strongly to v ∈ H and f (v) = minz∈H f (z). This com- (cid:2) pletes the proof.

(cid:11)

Next we consider a variational inequality. Let C be a nonempty closed convex subset of H and let T be a single-valued operator of C into H. We denote by VI(C,T) the set of solutions of the variational inequality, that is,

(cid:10) w ∈ X : (cid:10)s − w,Tw(cid:11) ≥ 0, ∀s ∈ C

(4.5) . VI(C,T) =

⎧ ⎨

A single-valued operator T is called semicontinuous if T is continuous from each line segment of C to H with the weak topology. Let F be a single-valued monotone and semi- continuous operator of C into H and let NCz be the normal cone to C at z ∈ C, that is, NCz = {w ∈ H : (cid:10)z − s,w(cid:11) ≥ 0, ∀s ∈ C}. Letting

⎩

(4.6) Az = Fz + NCz, ∅, z ∈ C, z ∈ H \ C,

Y. Yao and R. Chen 7

we have that A is a maximal monotone operator (see Rockafellar [14, Theorem 3]). We can also check that 0 ∈ Av if and only if v ∈ VI(C,F) and that Jrx = VI(C,Fr,x) for all r > 0 and x ∈ H, where Fr,xz = Fz + (z − x)/r for all z ∈ C. Then we have the following result.

(cid:3) ,

Corollary 4.3. Let F be a single-valued monotone and semicontinuous operator of C into H. For fixed u ∈ H, let the sequence {xn} be generated by

(cid:2) C,Frn,xn

yn ≈ VI (4.7) xn+1 = αnu + βnxn + δn yn.

Here the criterion for the approximate computation of yn in (4.7) will be

(cid:9) (cid:9)yn − VI

(cid:3)(cid:9) (cid:9) ≤ σn,

(cid:2) C,Frn,xn

(cid:4)∞

n=0 σn < ∞. Assume {αn}, {βn}, {δn}, and {rn} satisfy the same conditions (i)–(iv) where as in Theorem 3.1. If VI(C,F) (cid:6)= ∅, then {xn} defined by (4.7) with criterion (4.8) converges strongly to the point of VI(C,F) nearest to u.

(4.8)

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

References

[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: yuyanrong@tjpu.edu.cn

Rudong Chen: Department of Mathematics, Tianjin Polytechnic University, Tianjin 300160, China Email address: chenrd@tjpu.edu.cn

8 Fixed Point Theory and Applications