A Projection-Type Method for Multivalued Variational Inequality

Proposition 1.   x ∈ K and ξ ∈ T(x) solves the problem (1) if and only if

Algorithm 2. Choose x₀ ∈ K and three parameters σ > 0,   μ ∈ (0,1/σ), and γ ∈ (0,1). Set i = 0.

Step 1. If r_μ(x_i, w) = 0 for some w ∈ T(x_i), stop; else take arbitrarily w_i ∈ T(x_i).

Step 2. For every positive integer k, let $$.

Step 3. Let k_i be the smallest nonnegative integer k satisfying

Set $$ and z_i = x_i − η_ir_μ(x_i, w_i).

Step 4. Compute $$, where

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, y_k in Step 2 of our algorithm is uniquely determined by k. Hence, it is easy to compute the value of y_k 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(x^k − γ^mr(x^k, ξ^k)) and $$ 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 {y_k} generated in Step 2 has the following properties:

Proof. See Lemma  2.1 in [5].

Lemma 5. For every x ∈ K and w ∈ T(x),

Proof. See Lemma  2.3 in [5].

Lemma 6. If r_μ(x_i, w_i) ≠ 0, there exists k satisfying (5).

Proof. In view of Lemma 4, we have lim _k→∞y_k = w_i. Therefore,

where the first inequality follows from Lemma 5 and the second one follows from μ⁻¹ > σ and r_μ(x_i, w_i) ≠ 0.

Lemma 7. Let K be a closed convex subset of ℝⁿ. For any x, y ∈ ℝⁿ and z ∈ K, the following statements hold:

• (i)

  〈Π_K(x) − x, z − Π_K(x)〉≥0,

• (ii)

  ∥ Π_K(x) − Π_K(y)∥² ≤ ∥ x − y∥² − ∥ Π_K(x) − x + y − Π_K(y)∥².

Proof. See [25].

Lemma 8. Let x^* ∈ S and $$. If r_μ(x_i, w_i) ≠ 0, then the hyperplane

strictly separates x_i and the solution set S.

Proof. Since z_i = x_i − η_ir_μ(x_i, w_i),

where the first inequality follows from (5) and the last one follows from r_μ(x_i, w_i)) ≠ 0. Since T satisfies the property (3), h_i(x^*) ≤ 0.

Lemma 9. If S ≠ ∅, then $$.

Proof. It follows from Lemma 8 that $$. Next, it is sufficient to prove that $$ for all i ≥ 0. The proof will be given by induction.

Obviously, $$. Suppose that

Then, $$.

Let x^* ∈ S. Since

it follows from Lemma 7 (i) that Thus, $$. Therefore, we obtain that $$ for all i.

Lemma 10. Let K ⊂ ℝⁿ be a nonempty bounded closed convex set, and let the mapping $$ 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].

Lemma 11. Let $$ be continuous with nonempty compact convex values on K, and suppose that S = ∅; then, $$ for all i.

Proof. On the contrary, suppose that there exists i₀ ≥ 0 such that $$. Then, there exists a positive number M such that

where Since T(x) is continuous with compact values, Proposition  3.11 in [26] implies that {T(x_i) : 0 ≤ i ≤ i₀} is a bounded set, and so {x_i − μw_i : w_i ∈ T(x_i),   0 ≤ i ≤ i₀} is bounded. Without loss of generality, we assume that Consider the variational inequality GVI(T, C), where It follows from Lemma 10 that the solution set of GVI(T, C), denoted by S₁, is nonempty. We denote the three sequences $$, and {x_i} by $$, and $$, respectively, when Algorithm 2 is applied to GVI(T, C) with starting point x₀. We claim that

• (i)

  the set $$ has at least i₀ + 1 elements;

• (ii)

  $$ for 0 ≤ i ≤ i₀;

• (iii)

  $$ 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

where w_i ∈ T(x_i), 0 ≤ i ≤ i₀.

Since

where the second inequality follows from $$ and Lemma 7 (ii), so Π_K(x_i − μw_i) ∈ B(x₀, 2M), and hence, Π_K(x_i − μw_i) ∈ K∩B(x₀, 2M) = C. Therefore,

Since S₁ ≠ ∅, it follows from Lemma 9 that $$. Therefore, $$ for 0 ≤ i ≤ i₀, which contradicts the supposition that $$.

Theorem 12. Let $$ be continuous with nonempty compact convex values on K satisfying condition (3). Suppose that Algorithm 2 generates an infinite sequence {x_i}. If the solution set S of GVI(T, K) is nonempty, then {x_i} globally converges to a solution x^* of  GVI(T, K) satisfying x^* = Π_S(x₀).

Proof. Since $$, by Lemma 9 and the definition of projection, it follows that

Therefore, {x_i} is a bounded sequence.

Since $$, $$. Since

it follows that Thus, it follows from Lemma 7 (ii) that that is, Thus, the sequence {∥x_i − x₀∥} is nondecreasing and bounded and hence convergent, which implies that On the other hand, since and since $$, we have where the second inequality follows from (5). Therefore, it follows from (27) that Since T is continuous with compact values, Proposition  3.11 in [26] implies that {T(x_i)} is a bounded set, and so the sequences {w_i} and {z_i} are bounded. Thus, the continuity of T implies that {T(z_i)} is a bounded set. Therefore, $$ is bounded. It follows that By the boundedness of {x_i}, there exists a convergent subsequence $$ converging to $$.

If $$ is a solution of the problem (1), we show next that the whole sequence {x_i} converges to $$. Let x^* = Π_S(x₀). Since x^* ∈ S, by Lemma 9,

Therefore, Thus, Letting j → ∞ in (34), we have where the last inequality follows from Lemma 7 (i) and the fact that x^* = Π_S(x₀) and $$. Therefore, Thus, the sequence {x_i} has a unique cluster point Π_S(x₀), which shows the global convergence of {x_i}.

Suppose now that $$ is not a solution of the problem (1). We show first that k_i in Algorithm 2 cannot tend to ∞. Since T is continuous with compact values, Proposition  3.11 in [26] implies that {T(x_i) : i ∈ N} is a bounded set, and so the sequence {w_i} is bounded. Therefore, there exists a subsequence $$ converging to $$. Since T is upper semicontinuous with compact values, Proposition  3.7 in [26] implies that T is closed, and so $$. By the definition of k_i, we have

If $$, then $$. The lower continuity of T, in turn, implies the existence of $$ such that $$ converges to $$. Since $$, we have $$ and $$. Therefore $$ and Letting j → ∞ in (38), we have with r_μ(·, ·) being continuous. It follows from Lemma 5 that Thus, we obtain the contradiction because μ  <  1/σ. Therefore, {k_i} is bounded and so is {η_i}.

By (31) and the boundedness of {η_i}, we obtain that lim _i→∞∥r_μ(x_i, w_i)∥ = 0. Since r_μ(·, ·) is continuous and the sequences {x_i} and {w_i} are bounded, there exists an accumulation point $$ of {(x_i, w_i)} such that $$. This implies that $$ solves the variational inequality (1). Similar to the preceding proof, we obtain that {x_i} globally converges to $$.

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. Let $$ be continuous with nonempty compact convex values on K satisfying condition (3). Suppose that Algorithm 2 generates an infinite sequence {x_i}. 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 Theorem 12, 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 {∥x_i − x₀∥} is still nondecreasing. We claim that

Otherwise, {x_i} is bounded, and hence it follows from (26) that A similar discussion as in Theorem 12 would lead to the conclusion that every cluster point of {x_i} is a solution of GVI(T, K), which contradicts the emptiness of the solution set to GVI(T, K).

Example 15. Let n = 3,

and $$ be defined by 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 x₀ = (0,1, 0) as the initial point (Tables 1– 4).