# Iterative Algorithms for Variational Inequalities Governed by Boundedly Lipschitzian and Strongly Monotone Operators

Authors: Caiping Yang; Songnian He
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

Consider the variational inequalityVI(C,F) of finding a point x*∈C satisfying the property 〈Fx*,x-x*〉≥0 for all x∈C, where C is a level set of a convex function defined on a real Hilbert space H and F:H→H is a boundedly Lipschitzian (i.e., Lipschitzian on bounded subsets of H) and strongly monotone operator. He and Xu proved that this variational inequality has a unique solution and devised iterative algorithms to approximate this solution (see He and Xu, 2009). In this paper, relaxed and self-adaptive iterative algorithms are proposed for computing this unique solution. Since our algorithms avoid calculating the projection PC (calculating PC by computing a sequence of projections onto half-spaces containing the original domain C) directly and select the stepsizes through a self-adaptive way (having no need to know any information of bounded Lipschitz constants of F (i.e., Lipschitz constants on some bounded subsets of H)), the implementations of our algorithms are very easy. The algorithms in this paper improve and extend the corresponding results of He and Xu.


---

## Body

## 1. Introduction

LetH be a real Hilbert space with inner product 〈·,·〉 and norm ·, let C be a nonempty closed convex subset of H, and let F:C→H be a nonlinear operator. We consider the problem of finding a point x*∈C with the property
(1)Fx*,x-x*≥0,∀x∈C.
This is known as the variational inequality problem VI⁡(C,F), initially introduced and studied by Stampacchia [1] in 1964. In recent years, variational inequality problems have been extended to study a large variety of problems arising in structural analysis, economics, optimization, operations research, and engineering sciences; see [1–21] and the references therein. Using the projection technique, one can easily show that VI⁡(C,F) is equivalent to a fixed-point problem (see, e.g., [15]).Lemma 1.
x
*
∈
C is a solution of VI(C,F) if and only if x*∈C satisfies the fixed-point relation:
(2)x*=PC(I-λF)x*,
where λ>0 is an arbitrary constant, PC is the orthogonal projection onto C, and I is the identity operator on H.Recall that an operatorF:C→H is called monotone, if
(3)Fx-Fy,x-y≥0∀x,y∈C.
Moreover, a monotone operator F is called strictly monotone if the equality “=” holds only when x=y in the last relation. It is easy to see that VI⁡(C,F)(1) has at most one solution if F is strictly monotone.For variational inequality (1), F is generally assumed to be Lipschitzian and strongly monotone on C; that is, for some constants κ,η>0,  F satisfies the conditions
(4)Fx-Fy≤κx-y,∀x,y∈C,(5)〈Fx-Fy,x-y〉≥ηx-y2,∀x,y∈C.
In this case, F is also called a κ-Lipschitzian and η-strongly monotone operator. It is not difficult to show the following result.Lemma 2.
Assume thatF satisfies conditions (4) and (5) and λ and μ are constants such that λ∈(0,1) and μ∈(0,2η/κ2), respectively. Let Tμ=PC(I-μF) (or I-μF) and Tλ,μ=PC(I-λμF) (or I-λμF). Then Tμ and Tλ,μ are all contractions with coefficients 1-τ and 1-λτ, respectively, where τ=(1/2)μ(2η-μL2).By using the well-known Banach contraction mapping principle, this fact together with Lemma1 leads to the following classical result.Theorem 3.
Assume thatF satisfies conditions (4) and (5). Then VI(C,F) has a unique solution. Moreover, for any 0<λ<2η/κ2, the sequence {xn} with initial guess x0∈C and defined recursively by
(6)xn+1=PC(I-λF)xn,n≥0,
converges strongly to the unique solution of VI(C,F).Attempts are worth making to weaken the Lipschitz condition (4) or the strong monotonicity condition (5) so that existence of solutions of variational inequality (1) is still guaranteed. In 2009, He and Xu [14] weakened the Lipschitz condition (4) successfully to the bounded Lipschitz condition. A mapping F:C→H is boundedly Lipschitzian on C if it is Lipschitzian on each bounded subset of C; namely, for each nonempty bounded subset B of C, there exists a positive constant κB depending only on the set B such that
(7)Fx-Fy≤κBx-y,∀x,y∈B.He and Xu [14] not only proved existence and uniqueness of solutions of VI⁡(C,F) under conditions (5) and (7) but also estimated the range of this unique solution.Theorem 4 (see [14]).
Assume thatF:C→H is boundedly Lipschitzian on C (i.e., for each bounded subset B of C, F is Lipschitzian on B). Assume also that F is η-strongly monotone on C. Then variational inequality (1) has a unique solution x*∈C such that
(8)x*-u≤1ηFu,
where u∈C is an arbitrary fixed element.Similarly, we can also introduce bounded strong monotonicity of an operator. An operatorF:C→H is called boundedly strong monotone on C, if, for arbitrary bounded subset B of C, there exists a positive constant ηB depending only on the set B such that
(9)Fx-Fy,x-y≥ηBx-y2,∀x,y∈B.
So a natural question gives rise to this: is it possible also to replace the strong monotonicity of F by bounded strong monotonicity so that the result of Theorem 4 is still guaranteed? Unfortunately, a simple example [14] gives us a negative answer.He and Xu [14] also consider the iterative algorithms for solving VI⁡(C,F), where F:C→H is boundedly Lipschitzian and η-strongly monotone on C. Denote by u an arbitrary fixed element in C and denote by r a positive fixed constant such that
(10)r≥1ηFu.
Set Cr=S(u,r)∩C (S(u,r) is a closed ball of H, i.e., S(u,r)={x∈H:x-u≤r}) and denote by κr the Lipschitz constant of F on the bounded closed convex subset Cr.Using Theorem4, it is easy to see that VI⁡(C,F) and VI⁡(Cr,F) have the same solution. Thus one can devise iterative methods for VI⁡(Cr,F) and get the unique solution of VI⁡(C,F).Theorem 5 (see [14]).
Define a sequence{xn} recursively by the iterative algorithm
(11)x0∈Crarbitrarily,xn+1=PCr(I-λF)xn,
where 0<λ<2η/κr2. Then {xn} converges strongly to the unique solution x* of VI(C,F).However, algorithms (6) and (11) all have two evident weaknesses. On the one hand, they involve calculating the projections PC and PCr, respectively, while the computation of a projection onto a closed convex subset is generally difficult. Particularly, the computation of PCr is maybe more difficult since the structure of Cr is more complicated. On the other hand, the determination of the stepsize λ depends on the constants κ (or κr) and η. This means that, in order to implement algorithm (6) (or algorithm (11)), one has first to compute (or estimate) the constants κ (or κr) and η, which is sometimes not an easy work in practice.He and Yang [22] proposed relaxed and self-adaptive algorithms in order to overcome the above weaknesses of algorithm (6) and proved strong convergence theorems.In order to overcome the above weaknesses of algorithm (11), new relaxed and self-adaptive algorithms are proposed in this paper to solve VI⁡(C,F), where C is a level set of a convex function defined on H and F:H→H is a boundedly Lipschitzian and η-strongly monotone operator. Our methods calculate PCr by computing PS(u,r) (the computation of PS(u,r) is very easy) and a sequence of projections onto half-spaces containing the original level set C and select the stepsizes through a self-adaptive way. The implementations of our algorithms are very easy since they avoid computing PCr directly and have no need to know any information about κr (but η is assumed to be known, so our methods partly overcome the second weakness above). The algorithms in this paper improve and extend the above corresponding result of He and Xu.The rest of this paper is organized as follows. Some useful lemmas are listed in the next section. In the last section, a relaxed algorithm for the case whereη and κr are all known and a relaxed self-adaptive algorithm for the case where η is known but κr is unknown are proposed, respectively. The strong convergence theorems of our algorithms are proved.


## 2. Preliminaries

Throughout the rest of this paper, we denote byH a real Hilbert space and by I the identity operator on H. If f:H→R is a differentiable functional, then we denote by ∇f the gradient of f. We will also use the following notations.(i)
→ denotes strong convergence.(ii)
⇀ denotes weak convergence.(iii)
S(u,r)={x∣x-u≤r} denotes a closed ball in H with center u and radius r.(iv)
ωw(xn)={x∣∃{xnk}⊂{xn} such that xnk⇀x} denotes the weak ω-limit set of {xn}.Recall a trivial inequality, which is well known and in common use.Lemma 6.
For allx,y∈H, there holds the relation
(12)x+y2≤x2+2〈y,x+y〉.Recall that a mappingT:H→H is said to be nonexpansive if
(13)Tx-Ty≤x-y,x,y∈H.T:H→H is said to be firmly nonexpansive if, for x,y∈H,
(14)Tx-Ty2≤x-y2-(I-T)x-(I-T)y2.The following are characterizations of firmly nonexpansive mappings (see [7] or [23]).Lemma 7.
LetT:H→H be an operator. The following statements are equivalent.(i)
T is firmly nonexpansive.(ii)
I-T is firmly nonexpansive.(iii)
Tx-Ty2≤〈x-y,Tx-Ty〉, x,y∈H.We know that the orthogonal projectionPC from H onto a nonempty closed convex subset C⊂H is a typical example of a firmly nonexpansive mapping, which is defined by
(15)PCx≔argmin⁡y∈Cx-y2,x∈H.
It is well known that PCx is characterized by the inequality (for x∈H)
(16)PCx∈C,x-PCx,y-PCx≤0,∀y∈C.The following recent result [22] is likely to become a new fundamental tool for proving strong convergence of some algorithms. Its key effect on the proofs of our main results will be illustrated in the next section.Lemma 8 (see [22]).
Assumesn is a sequence of nonnegative real numbers such that
(17)sn+1≤(1-γn)sn+γnδn,n≥0,(18)sn+1≤sn-ηn+αn,n≥0,
where (γn) is a sequence in (0,1), (ηn) is a sequence of nonnegative real numbers, and (δn) and (αn) are two sequences in R such that(i)
∑n=0∞‍γn=∞,(ii)
limn→∞αn=0,(iii)
limk→∞ηnk=0 implies limsup⁡k→∞δnk≤0 for any subsequence (nk)⊂(n). Then limn→∞sn=0.Recall that a functionf:H→R is called convex if
(19)fλx+1-λy≤λfx+1-λfy,iiiiiiiiiiiiiiiiiiiiiiiiiiii∀λ∈0,1,∀x,y∈H.
A differentiable function f is convex if and only if there holds the relation
(20)f(z)≥f(x)+∇fx,z-x,∀z∈H.
Recall that an element g∈H is said to be a subgradient of f:H→R at x if
(21)f(z)≥f(x)+〈g,z-x〉,∀z∈H.A functionf:H→R is said to be subdifferentiable at x, if it has at least one subgradient at x. The set of subgradients of f at the point x is called the subdifferential of f at x and is denoted by ∂f(x). The last relation above is called the subdifferential inequality of f at x. A function f is called subdifferentiable, if it is subdifferentiable at all x∈H. If a function f is differentiable and convex, then its gradient and subgradient coincide.Recall that a functionf:H→R is said to be weakly lower semicontinuous (w-lsc) at x if xn⇀x implies
(22)f(x)≤liminf⁡n→∞f(xn).


## 3. Iterative Algorithms

In this section, we consider the iterative algorithms for solving a particular kind of variational inequality (1) in which the closed convex subset C is of the particular structure, that is, the level set of a convex function given as follows:
(23)C={x∈H:c(x)≤0},
where c:H→R is a convex function. We always assume that c is subdifferentiable on H and ∂c is bounded operator (i.e., bounded on bounded sets). We also assume that F:H→H is a boundedly Lipschitzian and η-strongly monotone operator. Using Theorem 4, we assert that in this case VI⁡(C,F) has a unique solution, henceforth, which is denoted by x*.The computation of a projection onto a closed convex subset is generally difficult. To overcome this difficulty, Fukushima [21] suggested a way to calculate the projection onto a level set of a convex function by computing a sequence of projections onto half-spaces containing the original level set. This idea is followed by Yang [24] and Lopez et al. and so forth [25], respectively, who introduced the relaxed CQ algorithms for solving the split feasibility problem in a finite-dimensional and infinite-dimensional Hilbert space, respectively. He and Yang [22] also used this idea to devise iterative algorithms for solving variational inequalities governed by Lipschitzian and strongly monotone operators.In the sequel, we always assume thatη is known and denote by x0∈H a selected arbitrarily fixed element. Using Theorem 4, the unique solution x* of VI⁡(C,F) belongs to a closed ball S(x0,r), where r is a fixed positive constant such that r>∥Fx0∥/η. We also always denote by κr the Lipschitz constant of F on S(x0,r).Based on Theorem4, we are now in a position to introduce a relaxed algorithm for computing the unique solution x* of VI⁡(C,F), where C is given as in (23). This scheme applies to the case where κr is easy to be determined.Algorithm 9.
Choose an arbitrary initial guessx0∈H and the sequence (xn) is constructed via the formula
(24)xn+1=PS(x0,r)PCn(I-λnμrF)xn,n≥0,
where
(25)Cn={x∈H:c(xn)≤〈ξn,xn-x〉},
where ξn∈∂c(xn), the sequence (λn) in (0,1), and μr is a constant such that μr∈(0,2η/κr2).We now analyze strong convergence of Algorithm9, which also illustrates the application of Lemma 8.Theorem 10.
Assume thatλn→0(n→∞) and ∑n=1+∞‍λn=+∞. Then the sequence (xn) generated by Algorithm 9 converges strongly to the unique solution x* of VI(C,F).Proof.
Obviously, it follows from (24) that (xn) is bounded (indeed (xn)⊂S(x0,r)) and so is (Fxn) noting the bounded Lipschitz condition of F. It is easy to see from the subdifferential inequality and the definition of Cn that Cn⊃C holds for all n≥0, and hence it follows that S(x0,r)∩Cn⊃S(x0,r)∩C=Cr. Observing that x*∈Cr, a projection is nonexpansive, and Tλn=I-λnμrF:S(x0,r)→H is a contraction with coefficient 1-λnτr for all n≥0 (using Lemma 2), where τr=(1/2)μr(2η-μrκr2), we obtain using (24) and Lemma 6 that
(26)xn+1-x*2=PS(x0,r)PCn(I-λnμrF)xn-PS(x0,r)PCnx*2≤(I-λnμrF)xn-(I-λnμrF)x*-λnμrFx*2≤(1-τrλn)xn-x*2-2λnμr〈Fx*,xn-x*-λnμrFxn〉≤(1-τrλn)xn-x*2-2λnμr〈Fx*,xn-x*〉+2λn2μr2Fx*Fxn.
On the other hand, we also have(27)xn+1-x*2=PS(x0,r)PCn(I-λnμrF)xn-PS(x0,r)PCnx*2=PS(x0,r)PCn(I-λnμrF)xn-PS(x0,r)PCnxn+PSx0,rPCnxn-PSx0,rPCnx*2≤PS(x0,r)PCnxn-PS(x0,r)PCnx*2+2λnμrFxn·xn-x*+λn2μr2Fxn2≤PS(x0,r)PCnxn-PS(x0,r)PCnx*2+λnM,
where M is a positive constant such that M≥sup⁡n{2μrFxn·xn-x*+λnμr2Fxn2}. Observing that a projection is firmly nonexpansive, we have
(28)PSx0,rPCnxn-PSx0,rPCnx*2≤PCnxn-PCnx*2-PCnxn-PSx0,rPCnxn2≤xn-x*2-xn-PCnxn2-PCnxn-PSx0,rPCnxn2,
and the combination of (27) and (28) leads to
(29)xn+1-x*2≤xn-x*2-xn-PCnxn2-PCnxn-PS(x0,r)PCnxn2+λnM.
Setting
(30)sn=xn-x*2,γn=τrλn,δn=-2μrτrFx*,xn-x*+2λnμr2τrFx*Fxn,ηn=xn-PCnxn2+PCnxn-PS(x0,r)PCnxn2,αn=Mλn,
then (26) and (29) can be rewritten as the following forms, respectively:
(31)sn+1≤(1-γn)sn+γnδn,(32)sn+1≤sn-ηn+αn.
Since ∑n=1∞‍γn=∞ and αn→0 hold, in order to complete the proof using Lemma 8, it suffices to verify that
(33)limk→∞ηnk=0
implies
(34)limsup⁡k→∞δnk≤0
for any subsequence (nk)⊂(n). In fact, if ηnk→0 as k→∞, then xnk-PCnkxnk→0 and PCnkxnk-PS(x0,r)PCnkxnk→0 hold. Since ∂c is bounded on bounded sets, we have a positive constant σ such that ξnk≤σ for all k≥0. From (25) and the trivial fact that PCnkxnk∈Cnk, it follows that
(35)cxnk≤ξnk,xnk-PCnkxnk≤σxnk-PCnkxnk.
Take x′∈ωw(xnk) arbitrarily and assume that xnk⇀x′ without loss of the generality; then the w-lsc of c and (35) imply that
(36)c(x′)≤liminf⁡k→∞c(xnk)≤0.
This means that x′∈C holds. On the other hand, we assert from (xn)⊂S(x0,r) that x′∈S(x0,r). Moreover, we obtain that x′∈S(x0,r)∩C=Cr and hence ωw(xnk)⊂Cr.
Noting the fact that2λn(μr2/τr)Fx*Fxn→0(n→∞) and x* is the unique solution of VI⁡(Cr,F) (i.e., the unique solution of VI⁡(C,F)), it turns out that
(37)limsup⁡k→∞δnk=-2μτliminf⁡k→∞Fx*,xnk+1-x*≤-2μτliminf⁡k→∞Fx*,xnk-x*=-2μτinf⁡Fx*,w-x*≤0,w∈ωw(xnk).It is worth mentioning that ifPC is easy to be calculated, then PCn in Algorithm 9 can be replaced with PC and it is easy to see that the whole proof of Theorem 10 is valid for this case. Therefore, if C=H, VI⁡(C,F) reduces to the operator equation problem: finding x*∈H such that Fx*=0, and the following result holds.Corollary 11.
Assume thatλn→0(n→∞), ∑n=1+∞‍λn=+∞, and C=H. Then the sequence (xn) generated by algorithm
(38)xn+1=PS(x0,r)(I-λnμrF)xn,n≥0,
converges strongly to the unique solution x* of the operator equation Fx=0.Sometimes, the constantκr is difficult to be obtained or estimated in practice (but we assume that η has been obtained). In this case, Algorithm 9 is indeed not fit for solving VI⁡(Cr,F) (i.e., VI⁡(C,F)). Then we now turn to introducing a relaxed and self-adaptive algorithm for the case where constant κr is unknown.Algorithm 12.
Choose an arbitrary initial guessx0∈C and an arbitrary element x1∈S(x0,r) such that x1≠x0. Assume that the nth iterate xn (n≥1) has been constructed. Continue and calculate the (n+1)th iterate xn+1 via the formula
(39)xn+1=PS(x0,r)PCn(I-λnμnF)xn,n≥1,
where Cn is given as in (25), the sequence (λn) is in (0,1), r is a constant such that r>∥Fx0∥/η, and the sequence (μn) is determined via the relation
(40)μn=ηxn-xn-12Fxn-Fxn-12,ifxn≠xn-1,μn-1,ifxn=xn-1,iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiin≥1.Firstly, we show that the sequence(xn) is well defined. Noting strong monotonicity of F, x1≠x0 implies that Fx1≠Fx0 and μ1 is well defined via the first formula of (40). Consequently, μn(n≥2) is well defined inductively according to (40) and thus the sequence (xn) is also well defined using (39).Next, we estimate(μn) roughly. If xn≠xn-1 (i.e., Fxn≠Fxn-1), set
(41)κn=Fxn-Fxn-1xn-xn-1.
Observing the fact that (xn)⊂S(x0,r) from (39), it turns out that
(42)η≤Fxn-Fxn-1,xn-xn-1xn-xn-12≤Fxn-Fxn-1xn-xn-1=κn≤κr.
Consequently
(43)ηκr2≤μn=ηκn2≤1η.
By the definition of (μn), we can assert that (43) holds for all n≥1.Now we analyze the strong convergence of Algorithm12.Theorem 13.
Assume thatλn→0(n→∞) and ∑n=1+∞‍λn=+∞. Then the sequence (xn) generated by Algorithm 12 converges strongly to the unique solution x* of VI(C,F).Proof.
Obviously,(xn) is bounded and so is (Fxn). Setting γn=λnμn and βn=(1/2)(2η-γnκr2), observing λn→0 and (43), it is concluded that there exists some positive integer n0 such that
(44)0<γn<ηκr2,n≥n0,
and consequently
(45)12η≤βn≤η,n≥n0.
Using Lemma 2, we have from (44) that, for all n≥n0,I-γnF:S(x0,r)→H is a contraction with coefficient 1-γnβn. This concludes that, for all n≥n0,
(46)xn+1-x*2=PS(x0,r)PCn(I-γnF)xn-PS(x0,r)PCnx*2≤(I-γnF)xn-(I-γnF)x*-γnFx*2≤(1-γnβn)xn-x*2-2γn〈Fx*,xn-x*-γnFxn〉.≤(1-γnβn)xn-x*2-2γn〈Fx*,xn-x*〉+2γn2Fx*Fxn.
By an argument similar to getting (27)–(29), we have
(47)xn+1-x*2≤xn-x*2-xn-PCnxn2-PCnxn-PS(x0,r)PCnxn2+γnM,
where M is a positive constant, which has nothing to do with n. Setting
(48)sn=xn-x*2,δn=-2βn〈Fx*,xn-x*〉+2γnβnFx*Fxn,σn=xn-PCnxn2+PCnxn-PS(x0,r)PCnxn2,αn=Mγn,
then (46) and (47) can be rewritten as the following forms, respectively:
(49)sn+1≤(1-γnβn)sn+γnβnδn,(50)sn+1≤sn-σn+αn.
Clearly, λn→0 and ∑n=1∞‍λn=∞, together with (43)–(45), imply that αn→0 and ∑n=1∞‍γnβn=∞.
By an argument very similar to the proof of Theorem10, it is not difficult to verify that
(51)limk→∞σnk=0
implies
(52)limsup⁡k→∞δnk≤0
for any subsequence (nk)⊂(n). Thus we can complete the proof by using Lemma 8.Similar to Algorithm9, if PC is easy to be calculated, then PCn in Algorithm 12 can also be replaced with PC and it is easy to see that the whole proof of Theorem 13 is valid for this case. The following result similar to Corollary 11 also holds.Corollary 14.
Assume thatλn→0(n→∞), ∑n=1+∞‍λn=+∞, and C=H. Then the sequence (xn) generated by algorithm
(53)xn+1=PS(x0,r)(I-λnμnF)xn,n≥0,
where μn is given as in (40), converges strongly to the unique solution x* of the operator equation Fx=0.Finally, we give an iterative algorithm for solving a classVI⁡(C,F), in which the closed convex subset C is the intersection of finite level sets of convex functions given as follows:
(54)C=⋂i=1m‍{x∈H:ci(x)≤0},
where m is a positive integer and ci:H→R(i=1,…,m) is a convex function. We always assume that ci(i=1,…,m) is subdifferentiable on H and ∂ci(i=1,…,m) is bounded operator (i.e., bounded on bounded sets).Without loss of generality, we will consider only the casem=2; that is, C=C1∩C2, where
(55)C1=x∈H:c1x≤0,C2=x∈H:c2x≤0.Algorithm 15.
Choose an arbitrary initial guessx0∈C and an arbitrary element x1∈S(x0,r) such that x1≠x0. Assume that the nth iterate xn (n≥1) has been constructed. Continue and calculate the (n+1)th iterate xn+1 via the formula
(56)xn+1=PS(x0,r)PCn2PCn1(I-λnμnF)xn,n≥1,
where the sequence (λn) is in (0,1), r is a constant such that r>∥Fx0∥/η, the sequence (μn) is given as in (40), and Cni(i=1,2) is determined via the relation
(57)Cn1=x∈H:c1xn≤ξn1,xn-x,Cn2=x∈H:c2PCn1xn≤ξn2,PCn1xn-x.By an argument similar to the proof of Theorem13 (together with the proof of Theorem 3.4 of [22]), we have the following result.Theorem 16.
Assume thatλn→0(n→∞) and ∑n=1+∞‍λn=+∞. Then the sequence (xn) generated by Algorithm 15 converges strongly to the unique solution x* of VI(C,F), where C=C1∩C2 and Ci(i=1,2) is given as in (55).



---

*Source: 175254-2015-03-01.xml*