Relatively Inexact Proximal Point Algorithm and Linear Convergence Analysis

Volume 2009, Article ID 691952,11pages doi:10.1155/2009/691952

Research Article

Relatively Inexact Proximal Point Algorithm and Linear Convergence Analysis

Ram U. Verma

Department of Mathematical Sciences, Florida Institute of Technology, Melbourne, FL 32901, USA

Correspondence should be addressed to Ram U. Verma,[email protected] Received 30 July 2009; Accepted 9 November 2009

Recommended by Petru Jebelean

Based on a notion of relatively maximalm-relaxed monotonicity, the approximation solvability of a general class of inclusion problems is discussed, while generalizing Rockafellar’s theorem 1976on linear convergence using the proximal point algorithm in a real Hilbert space setting.

Convergence analysis, based on this new model, is simpler and compact than that of the celebrated technique of Rockafellar in which the Lipschitz continuity at 0 of the inverse of the set-valued mapping is applied. Furthermore, it can be used to generalize the Yosida approximation, which, in turn, can be applied to first-order evolution equations as well as evolution inclusions.

Copyrightq2009 Ram U. Verma. 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

LetXbe a real Hilbert space with the inner product·,·and with the norm · onX.We consider the inclusion problem. Find a solution to

0∈Mx, 1.1

whereM:X → 2^Xis a set-valued mapping onX.

Rockafellar 1, Theorem 2 discussed general convergence of the proximal point algorithm in the context of solving 1.1, by showing forM maximal monotone, that the sequence{x^k}generated for an initial pointx⁰by the proximal point algorithm

x^k1≈P_k x^k

1.2

converges strongly to a solution of1.1,provided that the approximation is made sufficiently accurate as the iteration proceeds, whereP_k I c_kM⁻¹ is the resolvent operator for a sequence{ck}of positive real numbers, that is bounded away from zero. We observe from 1.2thatx^k1is an approximate solution to inclusion problem

0∈Mx c_k⁻¹ x−x^k

. 1.3

Next, we state the theorem of Rockafellar1, Theorem 2, where an approach of using the Lipschitz continuity ofM⁻¹instead of the strong monotonicity ofMis considered, that turned out to be more application enhanced to convex programming. Moreover, it is well- known that the resolvent operatorP_k Ic_kM⁻¹is nonexpansive, so it does not seem to be possible to achieve a linear convergence without having the Lipschitz continuity constant less than one in that setting. This could have been the motivation behind looking for the Lipschitz continuity ofM⁻¹ at zero which helped achieving the Lipschitz continuity of P_k with Lipschitz constant that is less than one instead.

Theorem 1.1. LetX be a real Hilbert space, and letM : X → 2^X be maximal monotone. For an arbitrarily chosen initial pointx⁰,let the sequence{x^k}be generated by the proximal point algorithm 1.2such that

x^k1−P_k

x^k≤_k, 1.4

wherePk IckM⁻¹, and the scalar sequences{k}and{ck},respectively, satisfyΣ^∞_k0k < ∞ and{c_k}is bounded away from zero.

We further suppose that sequence{x^k}is generated by the proximal point algorithm 1.2such that

x^k1−P_k

x^k≤δ_kx^k1−x^k, 1.5 where scalar sequences{δ_k}and{c_k},respectively, satisfyΣ^∞_k0δ_k<∞andc_k↑c≤ ∞.

Also, assume that {x^k} is bounded in the sense that the solution set to 1.1 is nonempty, and thatM⁻¹isa-Lipschitz continuous at 0 fora >0.Let

μk a

a²c_k² <1. 1.6

Then the sequence{x^k}converges strongly tox^∗,a unique solution to1.1with

x^k1−x^∗≤α_kx^k−x^∗ ∀k≥k, 1.7

where

0≤α_k μ_kδ_k

1−δk <1 ∀k≥k, α_k−→0 as c_k−→ ∞.

1.8

As we observe that most of the variational problems, including minimization or maximization of functions, variational inequality problems, quasivariational inequality problems, minimax problems, decision and management sciences, and engineering sciences can be unified into form1.1, the notion of the general maximal monotonicity has played a crucially significant role by providing a powerful framework to develop and use suitable proximal point algorithms in exploring and studying convex programming and variational inequalities. Algorithms of this type turned out to be of more interest because of their roles in certain computational methods based on duality, for instance the Hestenes-Powell method of multipliers in nonlinear programming. For more details, we refer the reader to1–15.

In this communication, we examine the approximation solvability of inclusion problem 1.1 by introducing the notion of relatively maximal m-relaxed monotone mappings, and derive some auxiliary results involving relatively maximal m-relaxed monotone and cocoercive mappings. The notion of the relatively maximal m-relaxed monotonicity is based on the notion of A-maximal m-relaxed monotonicity introduced and studied in9,10, but it seems more application-oriented. We note that our approach to the solvability of1.1differs significantly than that of1in the sense thatMis without the monotonicity assumption; there is no assumption of the Lipschitz continuity on M⁻¹, and the proof turns out to be simple and compact. Note that there exists a huge amount of research on new developments and applications of proximal point algorithms in literature to approximating solutions of inclusion problems of the form1.1in different space settings, especially in Hilbert as well as in Banach space settings.

2. Preliminaries

In this section, first we introduce the notion of the relatively maximalm-relaxed monotonicity, and then we derive some basic properties along with some auxiliary results for the problem on hand.

LetXbe a real Hilbert space with the norm · forX, and with the inner product·,·.

Definition 2.1. LetXbe a real Hilbert space, and letM:X → 2^Xbe a multivalued mapping andA:X → Xa single-valued mapping onX.The mapMis said to be the following.

iMonotone if

u^∗−v^∗, u−v ≥0 ∀u, u^∗,v, v^∗∈graphM. 2.1

iiStrictly monotone ifMis monotone and equality holds only ifuv.

iii r-strongly monotone if there exists a positive constantrsuch that

u^∗−v^∗, u−v ≥ru−v² ∀u, u^∗,v, v^∗∈graphM. 2.2

iv r-expanding if there exists a positive constantrsuch that

u^∗−v^∗ ≥ru−v ∀u, u^∗,v, v^∗∈graphM. 2.3

vStrongly monotone if

u^∗−v^∗, u−v ≥ u−v² ∀u, u^∗,v, v^∗∈graphM. 2.4

viExpanding if

u^∗−v^∗ ≥ u−v ∀u, u^∗,v, v^∗∈graphM. 2.5

vii m-relaxed monotone if there is a positive constantmsuch that

u^∗−v^∗, u−v ≥ −mu−v² ∀u, u^∗,v, v^∗∈graphM. 2.6

viii c-cocoercive if there exists a positive constantcsuch that

u^∗−v^∗, u−v ≥cu^∗−v^∗2 ∀u, u^∗,v, v^∗∈graphM. 2.7

ixMonotone with respect toAif

u^∗−v^∗, Au−Av ≥0 ∀u, u^∗,v, v^∗∈graphM. 2.8

xStrictly monotone with respect toAifMis monotone with respect toAand equality holds only ifuv.

xi r-strongly monotone with respect toAif there exists a positive constantr such that

u^∗−v^∗, Au−Av ≥ru−v² ∀u, u^∗,v, v^∗∈graphM. 2.9

xii m-relaxed monotone with respect toAif there exists a positive constantmsuch that

u^∗−v^∗, Au−Av ≥ −mu−v² ∀u, u^∗,v, v^∗∈graphM. 2.10

xiii h-hybrid relaxed monotone with respect toAif there exists a positive constanth such that

u^∗−v^∗, Au−Av ≥ −hAu−Av² ∀u, u^∗,v, v^∗∈graphM. 2.11

xiv m-cocoercive with respect toAif there exists a positive constantmsuch that u^∗−v^∗, Au−Av ≥mu^∗−v^∗2 ∀u, u^∗,v, v^∗∈graphM. 2.12

Definition 2.2. Let X be a real Hilbert space, and let M : X → 2^X be a mapping on X.

Furthermore, letA : X → X be a single-valued mapping on X.The mapMis said to be the following.

iNonexpansive if

u^∗−v^∗ ≤ u−v ∀u, u^∗,v, v^∗∈graphM. 2.13

iiCocoercive if

u^∗−v^∗, u−v ≥ u^∗−v^∗2 ∀u, u^∗,v, v^∗∈graphM. 2.14

iiiCocoercive with respect toAif

u^∗−v^∗, Au−Av ≥ u^∗−v^∗2 ∀u, u^∗,v, v^∗∈graphM. 2.15

Definition 2.3. LetXbe a real Hilbert space. LetA:X → Xbe a single-valued mapping. The mapM:X → 2^Xis said to be relatively maximalm-relaxed monotonewith respect toA if

iMism-relaxed monotone with respect toAform >0, iiRIρM Xforρ >0.

Definition 2.4. LetXbe a real Hilbert space. LetA:X → Xbe a single-valued mapping. The mapM:X → 2^Xis said to be relatively maximal monotonewith respect toAif

iMis monotone with respect toA, iiRIρM Xforρ >0.

Definition 2.5. LetXbe a real Hilbert space, and letA : X → Xber-strongly monotone.

LetM:X → 2^Xbe a relatively maximalm-relaxed monotone mapping. Then the resolvent operatorJ_ρ,m,A^M :X → Xis defined by

J_ρ,m,A^M u

IρM₋₁

u forr−ρm >0. 2.16

Proposition 2.6. Let X be a real Hilbert space. Let A : X → X be anr-strongly monotone mapping, and letM :X → 2^X be a relatively maximalm-relaxed monotone mapping. Then the resolvent operatorJ_ρ,m,A^M IρM⁻¹is single valued forr−ρm >0.

Proof. For anyz∈X,assumex, y∈IρM⁻¹z.Then we have

−xz∈ρMx, −yz∈ρM y

. 2.17

Since M is relatively maximal m-relaxed monotone, andA is r-strongly monotone, it follows that

−ρmx−y²≤ −

x−y, Ax−A

y ≤ −rx−y² ⇒

r−ρmx−y²≤0 ⇒xy forr−ρm >0.

2.18

Definition 2.7. Let X be a real Hilbert space. A map M : X → 2^X is said to be maximal monotone if

iMis monotone,

iiRIρM Xforρ >0.

Note that all relatively monotone mappings are relativelym-relaxed monotone for m >0.We include an example of the relative monotonicity and other of the relativeh-hybrid relaxed monotonicity, a new notion to the problem on hand.

Example 2.8. LetX −∞,∞, Ax −1/2x,and Mx −xfor all x ∈ X.ThenM is relatively monotone but not monotone, whileMis relatively m-relaxed monotone for m >0.

Example 2.9. LetX be a real Hilbert space, and letM : X → 2^X be maximal m-relaxed monotone. Then we have the Yosida approximationMρρ⁻¹I−J_ρ^M,whereJ_ρ^M IρM⁻¹ is the resolvent ofM,that satisfies

Mρu−Mρv, J_ρ^Mu−J_ρ^Mv

≥ −mJ_ρ^Mu−J_ρ^Mv², 2.19

that is,M_ρis relativelym-hybrid relaxed monotonewith respect toJ_ρ^M.

3. Generalization to Rockafellar’s Theorem

This section deals with a generalization to Rockafellar’s theorem1, Theorem 2in light of the new framework of relative maximalm-relaxed monotonicity, while solving1.1.

Theorem 3.1. LetXbe a real Hilbert space, letA:X → Xber-strongly monotone, and letM: X → 2^X be relatively maximalm-relaxed monotone. Then the following statements are mutually

equivalent:

ian elementu∈Xis a solution to1.1, iifor anu∈X,one has

uR^M_ρ,m,Au, 3.1

where

R^M_ρ,m,Au

IρM₋₁

u forr−ρm >0. 3.2

Proof. To showi⇒ii, ifu∈Xis a solution to1.1, then forρ >0 we have 0∈ρMu

or u∈

IρM u or R^M_ρ,m,Au u.

3.3

Similarly, to showii⇒i,we have

uR^M_ρ,m,Au ⇒ u∈

IρM u ⇒ 0∈ρMu ⇒ 0∈Mu.

3.4

Theorem 3.2. Let X be a real Hilbert space, let A : X → X ber-strongly monotone, and let M:X → 2^Xbe relatively maximalm-relaxed monotone. Furthermore, suppose thatM:X → 2^X is relativelyh-hybrid relaxed monotone and (AoR^M_ρk,m,Aisγ-cocoercive with respect toR^M_ρk,m,A.

i For an arbitrarily chosen initial point x⁰, suppose that the sequence {x^k} is generated by the proximal point algorithm1.2such that

x^k1−R^M_ρk,m,A

x^k≤_k, 3.5

whereΣ^∞_k0k<∞, r−ρ_km >0, R^M_ρk,m,A Iρ_kM⁻¹, and the scalar sequence{ρ_k}satisfies ρ_k ↑ ρ ≤ ∞.Suppose that the sequence{x^k}is bounded in the sense that the solution set of 1.1is nonempty.

iiIn addition to assumptions ini, we further suppose that, for an arbitrarily chosen initial pointx⁰,the sequence{x^k}is generated by the proximal point algorithm1.2such that

x^k1−R^M_ρk,m,A

x^k≤δ_kx^k1−x^k, 3.6

whereδk → 0, R^M_ρk,m,A IρkM⁻¹, and the scalar sequences{δk}and{ρk}, respectively, satisfyΣ^∞_k0δ_k<∞,andρ_k↑ρ≤ ∞.Then the following implications hold:

iiithe sequence{x^k}converges strongly to a solution of1.1, ivrate of convergences

0≤ lim

k→ ∞

δk

γ−hρk r₋₁

1−δk <1, 3.7

where 1/γ−hρ_kr<1.

Proof. Suppose thatx^∗is a zero ofM.We begin with the proof for R^M_ρk,m,A

x^k

−R^M_ρk,m,Ax^∗≤ 1 γ−hρ_k

rx^k−x^∗, 3.8 whereγ−hρ_k>0.It follows from the definition of the generalized resolvent operatorR^M_ρk,m,A, the relativeh-hybrid relaxed monotonicity ofMwith respect toAand theγ-cocoercivity ofAoR^M_ρk,m,Awith respect toR^M_ρk,m,Athat

x^k−x^∗−

R^M_ρk,m,A x^k

−R^M_ρk,m,Ax^∗ , A

R^M_ρk,m,A x^k

−A

R^M_ρk,m,Ax^∗

≥ −hρ_kAR^M_ρk,m,Ax^k−A

R^M_ρk,m,Ax^∗2

3.9

or

x^k−x^∗, A

R^M_ρk,m,A x^k

−A

R^M_ρk,m,Ax^∗

≥

R^M_ρk,m,A x^k

−R^M_ρk,m,Ax^∗, A

R^M_ρk,m,A x^k

−A

R^M_ρk,m,Ax^∗

−hρ_kAR^M_ρk,m,Ax^k−A

R^M_ρk,m,Ax^∗2

≥γAR^M_ρk,m,Ax^k−A

R^M_ρk,m,Ax^∗2

−hρkAR^M_ρk,m,Ax^k−A

R^M_ρk,m,Ax^∗2.

3.10

Next, we move to estimate

x^k1−x^∗≤R^M_ρk,m,A x^k

−x^∗k

R^M_ρk,m,A x^k

−R^M_ρk,m,Ax^∗k

≤ 1

γ−hρk

rx^k−x^∗_k.

3.11

Forγ−hρkr >1,combining the previous inequality for allk, we have x^k1−x^∗≤x⁰−x^∗k

i0

_i ≤x⁰−x^∗∞

k0

_k. 3.12

Hence,{x^k}is bounded.

Next we turn our attention to convergence part of the proof. Since x^k1−x^∗≤x^k1−R^M_ρk,m,A

x^kR^M_ρk,m,A x^k

−R^M_ρk,m,Ax^∗, x^k1−R^M_ρk,m,A

x^k≤δkx^k1−x^k≤δkx^k1−x^∗x^k−x^∗ ,

3.13

we get

x^k1−x^∗≤x^k1−R^M_ρk,m,A x^k R^M_ρk,m,A

x^k

−R^M_ρk,m,Ax^∗

≤δkx^k1−x^∗x^k−x^∗ 1

γ−hρ_k

rx^k−x^∗,

3.14

where 1/γ−hρkr <1.

It follows that

x^k1−x^∗≤

γ−hρk r₋₁

δk

1−δ_k x^k−x^∗. 3.15

It appears that3.15holds since 1/γ−hρ_kr <1seems to holdandδ_k → 0.

Hence, the sequence{x^k}converges strongly tox^∗.

To conclude the proof, we need to show the uniqueness of the solution to1.1. Assume thatx^∗is a zero ofM.Then usingx^k−x^∗ ≤ x⁰−x^∗_∞

k0k ∀k,we have that a^∗ lim

k→ ∞infx^k−x^∗ 3.16

is nonnegative and finite, and as a result,x^k−x^∗ → a^∗.Considerx₁^∗andx₂^∗to be two limit points of{x^k},then we have

x^k−x^∗₁a1, x^k−x^∗₂a2, 3.17

and both exist and are finite. If we express x^k−x^∗₂²x^k−x₁^∗22

x^k−x₁^∗, x₁^∗−x^∗₂

x^∗₁−x^∗₂², 3.18

then it follows that

klim→ ∞

x^k−x^∗₁, x^∗₁−x^∗₂ 1

2

a²₂−a²₁−x^∗₁−x₂^∗2

. 3.19

Sincex^∗₁is a limit point of{x^k},the left hand side limit must tend to zero. Therefore,

a²₁a²₂−x^∗₁−x^∗₂². 3.20

Similarly, we obtain

a²₂a²₁−x^∗₁−x^∗₂². 3.21

This results inx^∗₁x^∗₂.

Remark 3.3. WhenM:X → 2^X∗equals∂f,the subdifferential off, wheref:X → −∞,∞ is a functional on a Hilbert spaceX,can be applied for minimizingf.The functionfis proper iff /≡ ∞and is convex if

f

1−λxλy

≤1−λfx λf y

, 3.22

wherex, y ∈X and 0< λ <1.Furthermore, the functionfis lower semicontinuous onXif the set

x:x∈X, fx≤λ∀λ∈R

3.23

is closed inX.

The subdifferential∂f:X → 2^X∗offatxis defined by

∂fx

x^∗∈X^∗:f y

−fx≥

y−x, x^∗ ∀y∈X

. 3.24

In an earlier work7, Rockafellar has shown that iff is a lower semicontinuous proper convex functional onX,then∂f :X → 2^X∗is maximal monotone onX,whereXis any real Banach space. Several other special cases can be derived.

Suppose thatA:X → Xis strongly monotone andγ-cocoercive, and letf :X → R beτ-locally Lipschitzforτ ≥ 0such that∂f : X → 2^X∗ ism-relaxed monotone with

respect toA, that is,

u^∗−v^∗, Au−Av ≥ −u−v² ∀u, v∈X, 3.25

whereu^∗∈∂fu,andv^∗∈∂fv.Then∂fis relatively maximalm-relaxed monotone.

Acknowledgment

The author is greatly indebted to Professor Petru Jebelean and reviewers for their valuable comments and suggestions leading to the revised version.

References

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

2 R. P. Agarwal and R. U. Verma, “The over-relaxed η−proximal point algorithm and nonlinear variational inclusion problems,” Nonlinear Functional Analysis and Applications. In press.

3 R. P. Agarwal and R. U. Verma, “Role of relativeA-maximal monotonicity in overrelaxed proximal point algorithms with applications,” Journal of Optimization Theory and Applications, vol. 143, no. 1, pp.

1–15, 2009.

4 H.-Y. Lan, Y. J. Cho, and R. U. Verma, “Nonlinear relaxed cocoercive variational inclusions involving A, η-accretive mappings in Banach spaces,” Computers & Mathematics with Applications, vol. 51, no.

9-10, pp. 1529–1538, 2006.

5 A. Moudafi and M. Th´era, “Finding a zero of the sum of two maximal monotone operators,” Journal of Optimization Theory and Applications, vol. 94, no. 2, pp. 425–448, 1997.

6 R. T. Rockafellar, “Augmented Lagrangians and applications of the proximal point algorithm in convex programming,” Mathematics of Operations Research, vol. 1, no. 2, pp. 97–116, 1976.

7 R. T. Rockafellar, “On the maximal monotonicity of subdifferential mappings,” Pacific Journal of Mathematics, vol. 33, pp. 209–216, 1970.

8 P. Tossings, “The perturbed proximal point algorithm and some of its applications,” Applied Mathematics and Optimization, vol. 29, no. 2, pp. 125–159, 1994.

9 R. U. Verma, “A-monotonicity and its role in nonlinear variational inclusions,” Journal of Optimization Theory and Applications, vol. 129, no. 3, pp. 457–467, 2006.

10 R. U. Verma, “A-monotone nonlinear relaxed cocoercive variational inclusions,” Central European Journal of Mathematics, vol. 5, no. 2, pp. 386–396, 2007.

11 R. U. Verma, “A generalization to variational convergence for operators,” Advances in Nonlinear Variational Inequalities, vol. 11, no. 2, pp. 97–101, 2008.

12 R. U. Verma, “Approximation solvability of a class of nonlinear set-valued variational inclusions involvingA, η-monotone mappings,” Journal of Mathematical Analysis and Applications, vol. 337, no.

2, pp. 969–975, 2008.

13 E. Zeidler, Nonlinear Functional Analysis and Its Applications. I, Fixed-Point Theorems, Springer, New York, NY, USA, 1986.

14 E. Zeidler, Nonlinear Functional Analysis and Its Applications. II/B, Nonlinear Monotone Operators, Springer, New York, NY, USA, 1990.

15 E. Zeidler, Nonlinear Functional Analysis and Its Applications. III, Variational Methods and Optimiza- tion, Springer, New York, NY, UAS, 1985.