# A Projection-Type Method for Multivalued Variational Inequality

Authors: Changjie Fang; Shenglan Chen; Jiming Zheng
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We propose a projection-type method for multivalued variational inequality. The iteration sequence generated by the algorithm is proven to be globally convergent to a solution, provided that the multivalued mapping is continuous with nonempty compact convex values. Moreover, we present a necessary and sufficient condition on the nonemptiness of the solution set. Preliminary computational experience is also reported.


---

## Body

## 1. Introduction

We consider the following multivalued variational inequality, denoted byGVI(T,K) to find x*∈K and w*∈T(x*) such that
(1)〈w*,y-x*〉≥0,∀y∈K,
where K is a nonempty closed convex set in ℝn, T is a multivalued mapping from K into ℝn with nonempty values, and 〈·,·〉 and ∥·∥ denote the inner product and norm in ℝn, respectively.Projection-type algorithms have been extensively studied in the literature; see [1–8] and the references therein. Reference [2] proposes a subgradient extragradient algorithm for solving single-valued variational inequality in which the next iterate is a projection onto a halfspace whose bounding hyperplane supports the feasible set K at a certain point. Reference [6] proposes a projection method for variational inequality problems in which the hyperplane strictly separates the current iterate from the solution set of (1). Theory and algorithm of multivalued variational inequality have been much studied in the literature [1, 9–18]. Various algorithms for computing the solution of (1) are proposed. The well-known proximal point algorithm [19] requires the multivalued mapping T to be monotone. Relaxing the monotonicity assumption, [12] proposed the double projection algorithm for solving (1); also see [5]. Assume that T is pseudomonotone; [20] described a combined relaxation method for solving (1); see also [21]. Recently, [22] proposed an extragradient method for generalized variational inequality. In [22], the next iterate is the projection of the current iterate onto the feasible set K; also see [23].In this paper, we introduce a projection-type method for multivalued variational inequality in which the next iterate is a projection of the initial iterate onto intersection of two halfspaces containing the solution set. We obtain a global convergence theorem, assuming thatT is pseudomonotone on K with respect to the solution set; see (3) in the following. Moreover, we show that the iterative sequence diverges if and only if the solution set is empty. We also present numerical results of the proposed method. Now let us compare our algorithm with algorithms in [5, 12, 22, 23]. First, the next iterate in our method relates to the initial point. In [5, 12], the next iterate is the projection of the current iterate onto the intersection of the hyperplane and the feasible set K. Secondly, the next iterate in our method is a projection of the initial point onto the intersection of the two hyperplanes and the feasible set K. In addition, our Armijo-type linesearch procedure is also different from those in [12, 22, 23].The organization of this paper is as follows. In the next section, we present the algorithm details and some lemmas. We prove several preliminary results for convergence analysis in Section3. Numerical results are reported in the last section.


## 2. Algorithms

Let us recall the definition of continuous multivalued mapping.T is said to be upper semicontinuous at x∈K if, for every open set V containing T(x), there is an open set U containing x such that T(y)⊂V for all y∈K∩U. T is said to be lower semicontinuous at x∈K if, given any sequence {xk} converging to x and any y∈T(x), there exists a sequence yk∈T(xk) that converges to y. T is said to be continuous at x∈T if, it is both upper semicontinuous and lower semicontinuous at x. If T is single valued, then both upper semicontinuity and lower semicontinuity reduce to the continuity of T.T is called pseudomonotone on K in the sense of Karamardian [24], if, for any x,y∈K,
(2)〈v,x-y〉≥0,∀v∈T(y)⟹〈u,x-y〉≥0,∀u∈T(x).LetS be the solution set of (1), that is, those points x*∈K satisfying (1). Throughout this paper, we assume that the solution set S of the problem (1) is nonempty and T is continuous on K with nonempty compact convex values satisfying the following property:
(3)〈ζ,y-x〉≥0,∀y∈K,ζ∈T(y),∀x∈S.
The property (3) holds if T is pseudomonotone on K.LetΠK denote the projector onto K, and let μ>0 be a parameter.Proposition 1.
x
∈
K and ξ∈T(x) solves the problem (1) if and only if
(4)rμ(x,ξ):=x-ΠK(x-μξ)=0.Algorithm 2.
Choosex0∈K and three parameters σ>0,μ∈(0,1/σ), and γ∈(0,1). Set i=0.Step 1.
Ifrμ(xi,w)=0 for some w∈T(xi), stop; else take arbitrarily wi∈T(xi).Step 2.
For every positive integerk, let yk=ΠT(xi-γkrμ(xi,wi))(wi).Step 3.
Letki be the smallest nonnegative integer k satisfying
(5)〈yk,rμ(xi,wi)〉≥σ∥rμ(xi,wi)∥2.
Set ηi=γki and zi=xi-ηirμ(xi,wi).Step 4.
Computexi+1:=ΠHi1∩Hi2∩K(x0), where
(6)Hi1:={x∈Rn:〈yki,x-zi〉≤0},Hi2:={x∈Rn:〈x-xi,x0-xi〉≤0}.
Let i:=i+1, and go to Step 1.Remark 3.
Let us compare the previous algorithm with Algorithm  3.1 in [11]. First, the parameter σ>0 is required to be strictly less than 1, and μ is assumed to be equal to 1 in their Algorithm 3.1. In our Algorithm 2, the parameter σ can take any positive scalar and μ∈(0,1/σ). Secondly, since T has compact convex values, T has closed convex values. Therefore, yk in Step 2 of our algorithm is uniquely determined by k. Hence, it is easy to compute the value of yk satisfying (5). In Step 1 of their Algorithm 3.1, since F is a multivalued mapping, it is very difficult in practice to compute the value of ζk satisfying ζk∈F(xk-γmr(xk,ξk)) and 〈ζk,r(xk,ξk)〉≥σ∥r(xk,ξk)∥2 at the same time. In addition, we report numerical results concerning our algorithm, while [11] does not present numerical experiments for the proposed algorithm. Finally, we compare the performance of our algorithm and Algorithm  3.1 in [11] (see Table 4).Lemma 4.
The sequence{yk} generated in Step 2 has the following properties:
(7)yk∈T(xi-γkrμ(xi,wi)),limk→∞yk=wi.Proof.
See Lemma  2.1 in [5].Lemma 5.
For everyx∈K and w∈T(x),
(8)〈w,rμ(x,w)〉≥μ-1∥rμ(x,w)∥2.Proof.
See Lemma  2.3 in [5].We show that Algorithm2 is well defined and implementable.Lemma 6.
Ifrμ(xi,wi)≠0, there exists k satisfying (5).Proof.
In view of Lemma4, we have limk→∞yk=wi. Therefore,
(9)limk→∞〈yk,rμ(xi,wi)〉=〈wi,rμ(xi,wi)〉≥μ-1∥rμ(xi,wi)∥2>σ∥rμ(xi,wi)∥2,
where the first inequality follows from Lemma 5 and the second one follows from μ-1>σ and rμ(xi,wi)≠0.Lemma 7.
LetK be a closed convex subset of ℝn. For any x,y∈ℝn and z∈K, the following statements hold:(i)
〈ΠK(x)-x,z-ΠK(x)〉≥0,(ii)
∥ΠK(x)-ΠK(y)∥2≤∥x-y∥2-∥ΠK(x)-x+y-ΠK(y)∥2.Proof.
See [25].Lemma 8.
Letx*∈S and hi(x):=〈yki,x-zi〉. If rμ(xi,wi)≠0, then the hyperplane
(10)∂Hi1={x∈ℝn:hi(x)=0}
strictly separates xi and the solution set S.Proof.
Sincezi=xi-ηirμ(xi,wi),
(11)hi(xi)=〈yki,xi-zi〉=ηi〈yki,rμ(xi,wi)〉≥σηi∥rμ(xi,wi)∥2>0,
where the first inequality follows from (5) and the last one follows from rμ(xi,wi))≠0. Since T satisfies the property (3), hi(x*)≤0.Lemma 9.
IfS≠∅, then S⊂Hi1∩Hi2∩K.Proof.
It follows from Lemma8 that S⊂Hi1∩K. Next, it is sufficient to prove that S⊂Hi2 for all i≥0. The proof will be given by induction.
Obviously,S⊂H02=ℝn. Suppose that
(12)S⊂Hi2,fori=m≥0.
Then, S⊂Hm1∩Hm2∩K.
Letx*∈S. Since
(13)xm+1=ΠHm1∩Hm2∩K(x0),
it follows from Lemma 7 (i) that
(14)〈x*-xm+1,x0-xm+1〉≤0.
Thus, S⊂Hm+12. Therefore, we obtain that S⊂Hi2 for all i.Lemma 10.
LetK⊂ℝn be a nonempty bounded closed convex set, and let the mapping T:K→2ℝn be lower semicontinuous with nonempty closed convex values; then, the solution set S of GVI(T,K) is nonempty.Proof.
See Lemma  2.9 in [22].The following lemma says that if the solution setS is empty, then Hi1∩Hi2∩K is a nonempty set, which implies the feasibility of Algorithm 2.Lemma 11.
LetT:K→2ℝn be continuous with nonempty compact convex values on K, and suppose that S=∅; then, Hi1∩Hi2∩K≠∅ for all i.Proof.
On the contrary, suppose that there existsi0≥0 such that Hi01∩Hi02∩K=∅. Then, there exists a positive number M such that
(15){xi:0≤i≤i0}⊆B(x0,M),
where
(16)B(x0,M):={x∈Rn:∥x-x0∥≤M}.
Since T(x) is continuous with compact values, Proposition  3.11 in [26] implies that {T(xi):0≤i≤i0} is a bounded set, and so {xi-μwi:wi∈T(xi),0≤i≤i0} is bounded. Without loss of generality, we assume that
(17){xi-μwi:wi∈T(xi),0≤i≤i0}⊆B(x0,M).
Consider the variational inequality GVI(T,C), where
(18)C=K∩B(x0,2M).
It follows from Lemma 10 that the solution set of GVI(T,C), denoted by S1, is nonempty. We denote the three sequences {Hi1},{Hi2}, and {xi} by {H~i1},{H~i2}, and {x~i}, respectively, when Algorithm 2 is applied to GVI(T,C) with starting point x0. We claim that(i)
the set{x~i} has at least i0+1 elements;(ii)
xi=x~i,Hi1=H~i1,andHi2=H~i2 for 0≤i≤i0;(iii)
xi0 is not a solution of GVI(T,C).
Items (i) and (iii) are obvious. Next we prove the item (ii). It is sufficient to prove that(19)ΠK(xi-μwi)=ΠC(xi-μwi),
where wi∈T(xi),0≤i≤i0.
Since(20)∥x0-ΠK(xi-μwi)∥≤∥x0-ΠK(x0)∥+∥ΠK(x0)-ΠK(xi-μwi)∥≤∥x0-xi0∥+∥x0-(xi-μwi)∥≤2M,
where the second inequality follows from xi0∈K and Lemma 7 (ii), so ΠK(xi-μwi)∈B(x0,2M), and hence, ΠK(xi-μwi)∈K∩B(x0,2M)=C. Therefore,
(21)ΠK(xi-μwi)=ΠC(xi-μwi).
SinceS1≠∅, it follows from Lemma 9 that H~i1∩H~i2∩C≠∅. Therefore, Hi1∩Hi2∩K≠∅ for 0≤i≤i0, which contradicts the supposition that Hi01∩Hi02∩K=∅.


## 3. Main Results

Theorem 12.
LetT:K→2ℝn be continuous with nonempty compact convex values on K satisfying condition (3). Suppose that Algorithm 2 generates an infinite sequence {xi}. If the solution set S of GVI(T,K) is nonempty, then {xi} globally converges to a solution x* of  GVI(T,K) satisfying x*=ΠS(x0).Proof.
Sincexi+1=ΠHi1∩Hi2∩K(x0), by Lemma 9 and the definition of projection, it follows that
(22)∥xi+1-x0∥≤∥x*-x0∥,∀x*∈S.
Therefore, {xi} is a bounded sequence.
Sincexi+1∈Hi1∩Hi2∩K⊂Hi2, PHi2(xi+1)=xi+1. Since
(23)〈z-xi,x0-xi〉≤0,∀z∈Hi2,
it follows that
(24)xi=ΠHi2(x0).
Thus, it follows from Lemma 7 (ii) that
(25)∥ΠHi2(xi+1)-ΠHi2(x0)∥2m≤∥xi+1-x0∥2m-∥ΠHi2(xi+1)-xi+1+x0-ΠHi2(x0)∥2;
that is,
(26)∥xi+1-xi∥2≤∥xi+1-x0∥2-∥xi-x0∥2.
Thus, the sequence {∥xi-x0∥} is nondecreasing and bounded and hence convergent, which implies that
(27)limi→∞∥xi+1-xi∥2=0.
On the other hand, since
(28)ΠHi1(xi)=xi-[〈yki,xi-zi〉∥yki∥2]yki
and since xi+1∈Hi1, we have
(29)∥xi-xi+1∥≥∥xi-ΠHi1(xi)∥=〈yki,xi-zi〉∥yki∥≥σηi∥rμ(xi,wi)∥2∥yki∥,
where the second inequality follows from (5). Therefore, it follows from (27) that
(30)limi→∞ηi∥rμ(xi,wi)∥2∥yki∥=0.
Since T is continuous with compact values, Proposition  3.11 in [26] implies that {T(xi)} is a bounded set, and so the sequences {wi} and {zi} are bounded. Thus, the continuity of T implies that {T(zi)} is a bounded set. Therefore, {yki} is bounded. It follows that
(31)limi→∞ηi∥rμ(xi,wi)∥2=0.
By the boundedness of {xi}, there exists a convergent subsequence {xij} converging to x¯.
Ifx¯ is a solution of the problem (1), we show next that the whole sequence {xi} converges to x¯. Let x*=ΠS(x0). Since x*∈S, by Lemma 9,
(32)x*∈Hij-11∩Hij-12∩K,∀j≥1.
Therefore,
(33)∥xij-x0∥≤∥x*-x0∥.
Thus,
(34)∥xij-x*∥2=∥xij-x0∥2+∥x0-x*∥2+2〈xij-x0,x0-x*〉≤2∥x0-x*∥2+2〈xij-x0,x0-x*〉.
Letting j→∞ in (34), we have
(35)∥x¯-x*∥2≤2∥x0-x*∥2+2〈x¯-x0,x0-x*〉=2〈x¯-x*,x0-x*〉≤0,
where the last inequality follows from Lemma 7 (i) and the fact that x*=ΠS(x0) and x¯∈S. Therefore,
(36)x¯=x*=ΠS(x0).
Thus, the sequence {xi} has a unique cluster point ΠS(x0), which shows the global convergence of {xi}.
Suppose now thatx¯ is not a solution of the problem (1). We show first that ki in Algorithm 2 cannot tend to ∞. Since T is continuous with compact values, Proposition3.11 in [26] implies that {T(xi):i∈N} is a bounded set, and so the sequence {wi} is bounded. Therefore, there exists a subsequence {wij} converging to w¯. Since T is upper semicontinuous with compact values, Proposition 3.7 in [26] implies that T is closed, and so w¯∈T(x¯). By the definition of ki, we have
(37)〈ui,rμ(xi,wi)〉<σ∥rμ(xi,wi)∥2,∀ui=ΠT(xi-γki-1rμ(xi,wi))(wi).
If kij→∞, then xij-γkij-1rμ(xij,wij)→x¯. The lower continuity of T, in turn, implies the existence of w¯ij∈T(xij-γkij-1rμ(xij,wij)) such that w¯ij converges to w¯. Since uij=ΠT(xij-γkij-1rμ(xij,wij))(wij), we have uij∈T(xij-γkij-1rμ(xij,wij)) and ∥uij-wij∥≤∥w¯ij-wij∥. Therefore limj→∞uij=w¯ and
(38)〈uij,rμ(xij,wij)〉<σ∥rμ(xij,wij)∥2.
Letting j→∞ in (38), we have
(39)〈w¯,rμ(x¯,w¯)〉≤σ∥rμ(x¯,w¯)∥2,
with rμ(·,·) being continuous. It follows from Lemma 5 that
(40)μ-1∥rμ(x¯,w¯)∥2≤σ∥rμ(x¯,w¯)∥2.
Thus, we obtain the contradiction because μ<1/σ. Therefore, {ki} is bounded and so is {ηi}.
By (31) and the boundedness of {ηi}, we obtain that limi→∞∥rμ(xi,wi)∥=0. Since rμ(·,·) is continuous and the sequences {xi} and {wi} are bounded, there exists an accumulation point (x¯,w¯) of {(xi,wi)} such that rμ(x¯,w¯)=0. This implies that x¯ solves the variational inequality (1). Similar to the preceding proof, we obtain that {xi} globally converges to x¯=ΠS(x0).Remark 13.
In [11], the mapping F is required to be pseudomonotone. Since the pseudomonotonicity implies condition (3), our assumptions of the mapping T are more general.Theorem 14.
LetT:K→2ℝn be continuous with nonempty compact convex values on K satisfying  condition (3). Suppose that Algorithm 2 generates an infinite sequence {xi}. Then the solution set S of GVI(T,K) is empty if and only if the sequence generated by Algorithm 2 diverges.Proof.
In view of Theorem12, it is sufficient to prove that if the solution set is empty, then the sequence generated by Algorithm 2 diverges. Since inequality (26) also holds in this case, the sequence {∥xi-x0∥} is still nondecreasing. We claim that
(41)limi→∞∥xi-x0∥2=∞.
Otherwise, {xi} is bounded, and hence it follows from (26) that
(42)limi→∞∥xi+1-xi∥2=0.
A similar discussion as in Theorem 12 would lead to the conclusion that every cluster point of {xi} is a solution of GVI(T,K), which contradicts the emptiness of the solution set to GVI(T,K).


## 4. Numerical Experiments

In this section, we present some numerical experiments for the proposed algorithm. The MATLAB codes are run on a PC (with CPU Intel P-T2390) under MATLAB Version 7.0.1.24704(R14) Service Pack 1. We compare the performance of our Algorithm2 and the algorithms in [5, 11, 12, 22]. In Tables 1, 2, 3, and 4, “It.” denotes number of iteration, and “CPU" denotes the CPU time in seconds. The tolerance ε means that when ∥rμ(x,w)∥≤ε, the procedure stops.Table 1
Example15.
ε
Algorithm2
[5, Algorithm 1]
It. (no.)
CPU (Sec.)
It. (no.)
CPU  (Sec.)
10
-
7
23
0.34375
80
1.01563
10
-
5
17
0.3125
57
0.828125
10
-
3
10
0.265625
34
0.5625Table 2
Example15.
ε
Algorithm2
[12, Algorithm 1]
It. (no.)
CPU (Sec.)
It. (no.)
CPU  (Sec.)
10
-
7
23
0.34375
35
0.375
10
-
5
17
0.3125
25
0.3125
10
-
3
10
0.265625
15
0.28125Table 3
Example15.
ε
Algorithm2
[22, Algorithm 2.2]
It. (no.)
CPU (Sec.)
It. (no.)
CPU  (Sec.)
10
-
7
23
0.34375
27
0.390625
10
-
5
17
0.3125
21
0.375
10
-
3
10
0.265625
14
0.3125Table 4
Example15.
ε
Algorithm2
[11, Algorithm 3.1]
It. (no.)
CPU (Sec.)
It. (no.)
CPU  (Sec.)
10
-
7
23
0.34375
190
1.15625
10
-
5
17
0.3125
134
0.875
10
-
3
10
0.265625
79
0.5625Example 15.
Letn=3,
(43)K:={x∈ℝ+n:∑i=1n‍xi=1},
and T:K→2ℝn be defined by
(44)T(x):={(t,t-x1,t-x2):t∈[0,1]}.
Then, the set K and the mapping T satisfy the assumptions of Theorem 12, and (0,0,1) is a solution of the multivalued variational inequality. Example 15 is tested in [5, 12, 22]. We choose σ=0.8,γ=0.6, and μ=1 for our algorithm and Algorithm  1 in [5]; σ=0.4,γ=0.9, and μ=1 for Algorithm  1 in [12]; σ=4,γ=0.8, and μ=0.01 for Algorithm  1 in [22]; σ=0.9,γ=0.4 for Algorithm  3.1 in [11]. We use x0=(0,1,0) as the initial point (Tables 1– 4).



---

*Source: 836720-2013-09-25.xml*