This paper investigates the set-valued complementarity problems (SVCP) which poses rather different features from those that classical complementarity problems hold, due to tthe fact that he index set is not fixed, but dependent on x. While comparing the set-valued complementarity problems with the classical complementarity problems, we analyze the solution set of SVCP. Moreover, properties of merit functions for SVCP are studied, such being as level bounded and error bounded. Finally, some possible research directions are discussed.

1. Motivations and Preliminaries

The set-valued complementarity problem (SVCP) is to find x ∈ ℝⁿ such that

()

where

is a set-valued mapping. The set-valued complementarity problem plays an important role in the sensitivity analysis of complementarity problems [1] and economic equilibrium problems [2]. However, there has been very little study on the set-valued complementarity problems compared to the classical complementarity problems. In fact, the SVCP (1) can be recast as follows, which is denoted by SVNCP(F, Ω) to find x ∈ ℝⁿ, such that

()

where F : ℝⁿ × ℝ^m → ℝⁿ and Ω : ℝⁿ⇉ℝ^m are a set-valued mapping. To see this, if letting

()

then (1) reduces to (2). Conversely, if F(x, w) = w and Ω(x) = Θ(x), then (2) takes the form of (1).

The SVNCP(F, Ω) given as in (2) provides an unified framework for several interesting and important problems in optimization fields described as below.

(i)
Nonlinear complementarity problem [1], which is to find x ∈ ℝⁿ, such that
()
This corresponds to F(x, w) : = F(x) + w and Ω(x) = {0} for all x ∈ ℝⁿ. In other words, the set-valued complementarity problem reduces to the classical complementarity problem under such case.
(ii)
Extended linear complementarity problem [3, 4], which is to find x, w ∈ ℝⁿ, such that
()
where M₁, M₂ ∈ ℝ^m×n and P⊆ℝ^m are a polyhedron. This corresponds to F(x, w) = w and Ω(x) = {w | M₁x − M₂w ∈ P}. In particular, when P = {q}, it further reduces to the horizontal linear complementarity problem and to the usual linear complementarity problem, in addition to M₂ being an identify matrix.
(iii)
Implicit complementarity problem [5], which is to find x, w ∈ ℝⁿ and z ∈ ℝ^m, such that
()

where F : ℝ^2n×m → ℝ^l. This can be rewritten as

()

This is clearly an SVNCP(F, Ω) where F(x, w) = w and

(iv)
Mixed nonlinear complementarity problem, which is to find x ∈ ℝⁿ, and w ∈ ℝ^m such that
()

This is an SVNCP(F, Ω) where it corresponds to Ω(x) = {x∣G(x, w) = 0} . Note that the mixed nonlinear complementarity problem is a natural extension of Karush-Kuhn-Tucker (KKT) conditions for the following nonlinear programming:

()

To see this, we first write out the KKT conditions as follows:

()

where g(x) : = (g₁(x), …, g_m(x)), h(x) : = (h₁(x), …, h_l(x)), and λ : = (λ₁, …, λ_m). Then, letting w : = (λ, μ), F(x, w) : = −g(x), and

()

implies that the KKT system (10) becomes a mixed complementarity problem.

Besides the above various complementarity problems, SVNCP(F, Ω) has a close relation with the Quasi-variational inequality, a special of the extended general variational inequalities [6, 7], and min-max programming, which is elaborated as below.

(v)
Quasi-variational inequality [2]. Given a point-to-point map F from ℝⁿ to itself and a point-to-set map K from ℝⁿ into subsets of ℝⁿ, the Quasi-variational inequality QVI(K, F) is to find a vector x ∈ K(x), such that
()

It is well-known that QVI(K, F) reduces to the classical nonlinear complementarity problem when K(x) is independent of x, say,

for all x. Now, let us explain why it is related to SVNCP(F, Ω). To this end, given x ∈ ℝⁿ, we define I(x) = {i∣F_i(x) > 0}, and let

()

Clearly, 0 ∈ K(x) which says 〈x, F(x)〉 ≤ 0 by taking y = 0 in (12). Note that x ≥ 0 because x ∈ K(x). Next, we will claim that F_i(x) ≥ 0 for all i = 1,2, …, n. It is enough to consider the case where i ∈ I∖I(x). Under such case, by taking y = βe_i in (12) with β being an arbitrarily positive scalar, we have βF_i(x) ≥ F(x)^Tx. Since β can be made sufficiently large, it implies that F_i(x) ≥ 0. Thus, we obtain F(x)^Tx ≥ 0. In summary, under such case, QVI(K, F) becomes

()

which is an SVNCP(F, Ω).

(vi)
Min-max programming [8], which is to solve the following problem:
()

where f : ℝⁿ × Ω → ℝ is a continuously differentiable function, and Ω is a compact subset in ℝ^m. First, we define ψ(x) : = max _w∈Ωf(x, w). Although ψ is not necessarily Frechet differentiable, it is directional differentiable (even semismooth), see [9]. Now, let us check the first-order necessary conditions for problem (15). In fact, if x^* is a local minimizer of (15), then

()

which is equivalent to

()

where Ω(x) means the active set at x, that is, Ω(x) : = {w ∈ Ω | ψ(x) = f(x, w)}. At our first glance, the formula (17) is not related to SVNCP(F, Ω). Nonetheless, we will show that if Ω is convex and the function f(x, ·) is concave over Ω, then the first-order necessary conditions form an SVNCP(F, Ω), see below proposition.

Proposition 1. Let Ω be nonempty, compact, and convex set in ℝ^m. Suppose that, for each x, the function f(x, ·) is concave over Ω. If x^* is a local optimal solution of (15), then there exists w^* ∈ Ω(x^*), such that

()

Proof. Note first that for each x the inner problem

()

is a concave optimization problem, since f(x, ·) is concave and Ω is convex. This ensures that Ω(x), which denotes the optimal solution set of (19), is convex as well. Now we claim that the function

()

is concave over Ω(x^*). Indeed, for w₁, w₂ ∈ Ω(x^*) and α ∈ [0,1], we have

()

where we use the fact that αw₁ + (1 − α)w₂ ∈ Ω(x^*) (since Ω(x^*) is convex) and f(x^*, w) = ψ(x^*) for all w ∈ Ω(x^*). On the other hand, applying the Min-Max Theorem [10, Corollary 37.3.2] to (17) yields

()

Hence, for arbitrary ε > 0, we can find w_ε ∈ Ω(x^*), such that

()

that is,

()

In particular, plugging in x = 0 in (24) implies

()

Since Ω is bounded and Ω(x^*) is closed, we can assume, without loss of generality, that w_ε → w^* ∈ Ω(x^*) as ε → 0. Thus, taking the limit in (25) gives

()

Now, let

. It follows from (24) that

()

which implies that

by letting k → ∞, and hence

for all i = 1,2, …, n, that is, ∇_xf(x^*, w^*) ≥ 0. This together with (26) means that 〈∇_xf(x^*, w^*), x^*〉 = 0. Thus, (18) holds.

From all the above, we have seen that SVNCP(F, Ω) given as in (2) covers a range of optimization problems. Therefore, in this paper, we mainly focus on SVNCP(F, Ω). Due to its equivalence to SVCP (1), our analysis and results for SVNCP(F, Ω) can be carried over to SVCP (1). This paper is organized as follows. In Section 1, connection between SVNCP(F, Ω) and various optimization problems is introduced. We recall some background materials in Section 2. Besides comparing the set-valued complementarity problems with the classical complementarity problems, we analyze the solution set of SVCP in Section 3. Moreover, properties of merit functions for SVCP are studied in Section 4, such as level bounded and error bound. Finally, some possible research directions are discussed.

A few words about the notations used throughout the paper. For any x, y ∈ ℝⁿ, the inner product is denoted by x^Ty or 〈x, y〉. We write x ≥ y (or x > y) if x_i ≥ y_i (or x_i > y_i) for all i = 1,2, …, n. Let e be the vector with all components being 1, and let e_i be the i-row of identity matrix. Denote

. While SVNCP(F, Ω) meaning the set-valued nonlinear complementary problem (2), SVLCP(M, q, Ω) denotes the linear case, that is, F(x, w) = M(w)x + q(w), where M : ℝ^m → ℝ^n×n and q : ℝ^m → ℝⁿ. For a continuously differentiable function F : ℝⁿ × ℝ^m → ℝ^l, we denote the l × n Jacobian matrix of partial derivatives of F at

with respect to x by

, whereas the transposed Jacobian is denoted by

. For a mapping H : ℝⁿ → ℝ^m, define

()

Given a set-valued mapping M : ℝⁿ⇉ℝ^m, define

()

We say that M is outer semicontinuous at

, if

()

and inner semicontinuous at

()

We say that M is continuous at

if it is both outer semicontinuous and inner semicontinuous at

. For more details about these functions, please refer to [9, 11]. Throughout this paper, we always assume that the set-valued mapping Ω : ℝⁿ⇉ℝ^m is closed valued; that is, Ω(x) is closed for all x ∈ ℝⁿ [11, Chapter 1].

2. Focus on SVLCP (M, q, Ω)

It is well known that various matrix classes paly different roles in the theory of linear complementarity problem, such as P-matrix, S-matrix, Q-matrix, and Z-matrix, see [1, 12] for more details. Here we recall some of them which will be needed in the subsequent analysis.

Definition 2. A matrix M ∈ ℝ^n×n is said to be an S-matrix if there exists x ∈ ℝⁿ, such that

()

Note that M ∈ ℝ^n×n is an S-matrix, if and only if the classical linear complementarity problem LCP(M, q) is feasible for all q ∈ ℝⁿ, see [12, Prop. 3.1.5]. Moreover, the above condition in Definition 2 is equivalent to

()

see [13, Remark 2.2]. However, such equivalence fails to hold for its corresponding cases in set-valued complementarity problem. In other words,

()

is not equivalent to

()

It is clear that (34) implies (35). But, the converse implication does not hold, which is illustrated in Example 3.

Example 3. Let

()

If M(w)x > 0, then w = 1, and such case holds only when x = (1,0). Therefore, (35) is satisfied, but (34) is not.

We point out that the set-valued mapping Ω(x) in Example 3 is indeed outer semi-continuous. A natural question arises: what happens if Ω(x) is inner semi-continuous? The answer is given in Theorem 4 as below.

Theorem 4. If Ω(x) is inner semicontinuous, and M(w) is continuous, then (34) and (35) are equivalent.

Proof. We only need to show (35)⇒(34). Let H(x) = max _w∈Ω(x)M(w)x, and denote by a_i(x) the ith row of M(w). Hence H_i(x) = max _w∈Ω(x)a_i(x)^Tx. With this, suppose x₀ is an arbitrary but fixed point, we know that for any ε > 0, there exists w₀ ∈ Ω(x₀) such that . Since Ω(x) is inner semi-continuous, for any x_n → x₀, there exists w_n ∈ Ω(x_n) satisfying w_n → w₀. This implies

()

Then, taking the lower limit yields

()

where the equality follows from the continuity of a_i(w), which is ensured by the continuity of M(w). Because ε > 0 is arbitrary, and {x_n} is an arbitrary sequence converging to x₀, we obtain

()

which says H_i is lower semi-continuous. This further implies

()

that is,

()

satisfies (35), then

()

which is equivalent to

()

On the other hand,

, and

for λ > 0. By taking λ > 0 small enough, we know

satisfies (34). Thus, the proof is complete.

There is another point worthy of pointing out. We mentioned that the classical linear complementarity problem LCP(M, q) is feasible for all q ∈ ℝⁿ if and only if M ∈ ℝ^n×n is a S-matrix; that is, there exists x ∈ ℝⁿ, such that

()

Is there any analogous result in the set-valued set? Yes, we have an answer for it in Theorem 5 below.

Theorem 5. Consider the set-valued linear complementarity problem SVLCP(M, q, Ω). If there exists x ∈ ℝⁿ, such that

()

then SVLCP(M, q, Ω) is feasible for all q : ℝ^m → ℝⁿ being bounded from below.

Proof. Let q be any mapping from ℝ^m to ℝⁿ being bounded from below, that is, there exists β ∈ ℝ, such that q(w ) ≥ βe. Suppose that x₀ and w₀ satisfy (45), which means

()

Then, for any

, we have

. In particular, we observe the following:

(1)
if taking , then there exists n₁, such that w₀ ∈ Ω(n₁x₀);
(2)
if taking , then there exists n₂ with n₂ > n₁, such that w₀ ∈ Ω(n₂x₀).

Repeating the above process yields a sequence {n_k}, such that w₀ ∈ Ω(n_kx₀) and n_k → ∞. Since M(w₀)x₀ > 0, it ensures the existence of α > 0, such that M(w₀)x₀ > αe. Taking k large enough to satisfy n_k > max {−β/α, 0} gives αn_ke > −βe ≥ −q(w). Then, it implies that

()

and hence

()

which says n_kx₀ is a feasible point of SVLCP(M, q, Ω).

Definition 6. A matrix M ∈ ℝ^n×n is said to be a P-matrix if all its principal minors are positive, or equivalently [12, Theorem 3.3.4],

()

From [12, Corollary 3.3.5], we know that every P-matrix is an S-matrix. In other words, if M satisfies (49), then the following system is solvable:

()

Their respective corresponding conditions in set-valued complementarity problem are

()

Example 7 shows that the aforementioned implication is not valid as well in set-valued complementarity problem.

Example 7. Let

()

For x₁ ≠ 0, we have M(w)x = (x₁, −x₂), and hence . For x₁ = 0, we know x₂ ≠ 0 (since x ≠ 0) which says M(w)x = (−x₁, x₂), and hence . Therefore, condition (51) is satisfied. But, condition (52) fails to hold because M(w)x = (x₁, −x₂) or (−x₁, x₂). Hence, M(w)x > 0 implies that x₂ < 0 or x₁ < 0, which contradicts with x ≥ 0.

Definition 8. A matrix M ∈ ℝ^n×n is said to be semimonotone if

()

For the classical linear complementarity problem, we know that M is semimonotone if and only if LCP(M, q) with q > 0 has a unique solution (zero solution), see [12, Theorem 3.9.3]. One may wonder whether such fact still holds in set-valued case. Before answering it, we need to know how to generalize concept of semi-monotonicity to its corresponding definition in the set-valued case.

Definition 9. The set of matrices {M(w)∣w ∈ Ω(x)} is said to be

(a)
strongly semimonotone if for any nonzero x ≥ 0,
()
(b)
weakly semimonotone if for any nonzero x ≥ 0,
()

Unlike the classical linear complementarity problem case, here are parallel results regarding set-valued linear complementarity problem which strong (weak) semi-monotonicity plays in.

Theorem 10. For the SVLCP(M, q, Ω), the following statements hold.

(a)
If the set of matrices {M(w)∣w ∈ Ω(x)} is strongly semi-monotone, then for any positive mapping q, that is, q(w) > 0 for all w, SVLCP(M, q, Ω) has zero as its unique solution.
(b)
If SVLCP(M, q, Ω) with q(w) > 0 has zero as its unique solution, then the set of matrices {M(w)∣w ∈ Ω(x)} is weakly semi-monotone.

Proof. (a) It is clear that, for any positive mapping q, x = 0 is a solution of SVLCP(M, q, Ω). Suppose there is another nonzero solution , that is, , such that

()

It follows from (55) that there exists k ∈ {1,2, …, n}, such that

and

, and hence

, which contradicts condition (57).

(b) Suppose {M(w)∣w ∈ Ω(x)} is not weakly semi-monotone. Then, there exists a nonzero , for all , for all . Choose . Let q(w) = 1 for all and

()

Therefore, q(w) > 0 for all w. According to the above construction, we have

()

that is, the nonzero vector

is a solution of SVLCP(M, q, Ω), which is a contradiction.

Theorem 10(b) says that the weak semi-monotonicity is a necessary condition for zero being the unique solution of SVLCP(M, q, Ω). However, it is not the sufficient condition, see Example 11.

Example 11. Let

()

For any nonzero x = (x₁, x₂, x₃) ≥ 0, we have M(0)x = (x₂, x₃, x₁) ≥ 0. If we plug in q = (1,1, 1), by a simple calculation, x = (1,0, 0) satisfies

()

which means that SVLCP(M, q, Ω) has a nonzero solution. We also notice that the set-valued mapping Ω(x) is even continuous in Example 11.

So far, we have seen some major difference between the classical complementarity problem and set-valued complementarity problem. Such phenomenon undoubtedly confirms that it is an interesting, important, and challenging task to study the set-valued complementarity problem, which, to some extent, is the main motivation of this paper.

To close this section, we introduce some other concepts which will be used later too. A function f : ℝⁿ → ℝ is level bounded, if the level set {x∣f(x) ≤ α} is bounded for all α ∈ ℝ. The metric projection of x to a closed convex subset A ⊂ ℝⁿ is denoted by Π_A(x), that is, Π_A(x) : = arg min _y∈A∥x − y∥. The distance function is defined as dist (x, A) : = ∥x − Π_A(x)∥.

3. Properties of Solution Sets

Recently, many authors study other classes of complementarity problems, in which another type of vector w ∈ Ω is involved, for example, the stochastic complementarity problem [14–17], to find x ∈ ℝⁿ, such that

()

where w is a random vector in a given probability space and the semi-infinite complementarity problem [18] to find x ∈ ℝⁿ, such that

()

which we denote it by SINCP(F, Ω). In addition, the authors introduce the following two complementarity problems in [18] to find x ∈ ℝⁿ, such that

()

where

()

These two problems are denoted by NCP(F_min) and NCP(F_max), respectively. Is there any relationship among their solutions sets? In order to further describing such relationship, we adapt the following notations:

(i)
SOL(F, Ω) means the solution set of SVNCP(F, Ω),
(ii)
SOL(M, q, Ω) means the solution set of SVLCP(F, Ω),
(iii)
means the solution set of SINCP(F, Ω),
(iv)
SOL(F_min) means the solution set of NCP(F_min),
(v)
SOL(F_max) means the solution set of NCP(F_max).

Besides, for the purpose of comparison, we restrict that Ω(x) is fixed; that is, there exists a subset Ω in ℝ^m, such that Ω(x) = Ω for all x ∈ ℝⁿ.

It is easy to see that the solution set of SINCP(F, Ω) is ⋂_w∈Ω SOL(F_w), but that of SVNCP(f, Ω) is ⋃_w∈Ω SOL(F_w), where F_w(x): = F(x, w). Hence, the solution set of SINCP(F, Ω) is included in that of SVNCP(F, Ω). In other words, we have

()

The inclusion (67) can be strict as shown in Example 12.

Example 12. Let F(x, w) = (w, 1) and Ω(x) = [0,1]. Then, we can verify that , whereas SOL(F, Ω) = {x∣x₁ ≥ 0, x₂ = 0}.

However, the solution set of SVNCP(F, Ω), NCP(F_min), and NCP(F_max) are not included each other. This is illustrated in Examples 13–14.

Example 13. SOL(F_min) ⊈ SOL(F, Ω) and SOL(F, Ω) ⊈ SOL(F_min).

(a)
Let F(x, w) = (1 − w, w) and Ω = [0,1]. Then, , .
(b)
Let F(x, w) = (w − 1, x₂) and Ω = [0,1]. Then, SOL(F_min) = ∅ and SOL(F, Ω) = {(x₁, x₂)∣x₁ ≥ 0, x₂ = 0}.

Example 14. SOL(F_max) ⊈ SOL(F, Ω) and SOL(F, Ω) ⊈ SOL(F_max).

(a)
Let F(x, w) = (w − 1, −w) and Ω = [0,1]. Then, and SOL(F, Ω) = ∅.
(b)
Let F(x, w) = (w, −w) and Ω = [0,1]. Then, SOL(F_max) = {(x₁, x₂)∣x₁ = 0, x₂ ≥ 0} and .

Similarly, Example 15 shows that the solution set of NCP (F_max) and NCP(F_min) cannot be included each other.

Example 15. SOL(F_max) ⊈ SOL(F_min) and SOL(F_min) ⊈ SOL(F_max).

(a)
Let F(x, w) = (w − 1,0) and Ω = [0,1]. Then, SOL(F_min) = ∅ and .
(b)
Let F(x, w) = (w, w) and Ω = [0,1]. Then, and SOL(F_max) = {(0,0)}.

In spite of these, we obtain some results which describe the relationship among them.

Theorem 16. Let Ω(x) = Ω for all x ∈ ℝⁿ. Then, we have

(a)
SOL(F, Ω)∩{x∣F_min(x) ≥ 0}⊆SOL(F_min);
(b)
SOL(F_max)∩{x∣F(x, w) ≥ 0 for some w ∈ Ω}⊆SOL(F, Ω);
(c)
SOL(F_min)∩{x∣x^TF_max(x) ≤ 0} = SOL(F_max)∩{x∣F_min(x) ≥ 0}⊆SOL(F, Ω).

Proof. Parts (a) and (b) follow immediately from the fact

()

Part (c) is from (67), since the two sets in the left side of (c) is

by [18].

For further characterizing the solution sets, we recall that for a set-valued mapping M : ℝⁿ⇉ℝ^m, its inverse mapping (see [9, Chapter 5]) is defined as

()

Theorem 17. For SVNCP(F, Ω), we have

()

Proof. In fact, the desired result follows from

()

where the second equality is due to the definition of inverse mapping given as above.

4. Merit Functions for SVNCP and SVLCP

It is well known that one of the important approaches for solving the complementarity problems is to transfer it to a system of equations or an unconstrained optimization via NCP functions or merit functions. Hence, we turn our attention in this section to address merit functions for SVNCP(F, Ω) and SVLCP(M, q, Ω).

A function ϕ : ℝ² → ℝ is called an NCP function if it satisfies

()

For example, the natural residual ϕ_NR(a, b) = min {a, b} and the Fischer-Burmeister function

are popular NCP-functions. Please also refer to [19] for a detailed survey on the existing NCP-functions. In addition, a real-valued function f : ℝⁿ → ℝ is called a merit (or residual) function for a complementarity problem if f(x) ≥ 0 for all x ∈ ℝⁿ and f(x) = 0 if and only if x is a solution of the complementarity problem. Given an NCP-function ϕ, we define

()

Then, it is not hard to verify that the function given by

()

is a merit function for SVNCP(F, Ω). Note that the merit function (74) is rather different from the traditional one, because the index set is not a fixed set, but dependent on x. We say that a merit function r(x) has a global error bound with a modulus c > 0 if

()

For more information about the error bound, please see [20] which is an excellent survey paper regarding the issue of error bounds.

Theorem 18. Assume that there exists a set Ω ⊂ ℝ^m, such that Ω(x) = Ω for all x ∈ ℝⁿ, and that for each w ∈ Ω, r(x, w) is a global error bound of NCP(F_w) with the modulus η(w) > 0, that is,

()

In addition, if

()

then r(x) = min _w∈Ωr(x, w) provides a global error bound for SVNCP(F, Ω) with the modulus η.

Proof. Noticing that if Ω(x) = Ω for all x ∈ ℝⁿ, then

()

It then follows from Theorem 17 that

()

Therefore,

()

Thus, the proof is complete.

One may ask when condition (77) is satisfied? Indeed, the condition (77) is satisfied if

(i)
Ω is a finite set;
(ii)
F(x, w) = M(w)x + q(w) where M(w) is continuous, and for each w ∈ Ω the matrix M(w) is a P-matrix. In this case the modulus η(w) takes an explicitly formula, that is,
()

see [21, 22]. Hence, we see that

()

is well defined because M(w) is continuous, and Ω is compact.

For simplification of notations, we write x → ∞ instead of ∥x∥ → ∞. We now introduce the following definitions which are similar to (29):

()

Definition 19. For SVLCP(M, q, Ω), the set of matrices {M(w)∣w ∈ Ω(x)} is said to have the limit-R₀ property if

()

In the case of a linear complementarity problem, that is, Ω(x) is a fixed single-point set, Definition 19 coincides with that of R₀-matrix.

Theorem 20. For SVLCP(M, q, Ω), suppose that there exists a bounded set Ω, such that Ω(x) ⊂ Ω for all x ∈ ℝⁿ, and M(w) and q(w) are continuous on Ω. If the set of matrices {M(w)∣w ∈ Ω(x)} has the limit-R₀ property, then the merit function r(x) = min _w∈Ω(x)∥min {x, M(w)x + q(w)}∥ is level bounded.

Proof. We argue this result by contradiction. Suppose there exists a sequence {x_n} satisfying ∥x_n∥ → ∞, and r(x_n) is bounded. Then,

()

where we assume the minimizer is attained at w_n ∈ Ω(x_n), whose existence is ensured by the compactness of Ω(x_n), since Ω(x) is closed and Ω is bounded. Taking a subsequence if necessary, we can assume that {x_n/∥x_n∥} and {w_n} are both convergent in which

and

represent their corresponding limit point. Thus, we have

()

Now, taking the limit in (85) yields

()

where we have used the fact that q(w_n)/∥x_n∥ → 0, because q is continuous, and w_n ∈ Ω is bounded. This contradicts (84) since

is a nonzero vector.

Note that the condition (84) is equivalent to

()

which is also equivalent to saying that each matrix M(w) for w ∈ lim sup _x→∞Ω(x) is a R₀-matrix.

Theorem 21. For SVLCP(M, q, Ω), suppose that there exists a compact set Ω, such that Ω(x) ⊂ Ω for all x ∈ ℝⁿ, and M(w) and q(w) are continuous on Ω. If r(x) = min _w∈Ω(x)∥min {x, M(w)x + q(w)}∥ is level bounded, then the following implication holds

()

Proof. Suppose that there exist a nonzero vector x₀, and , such that

()

Similar to the argument as in Theorem 5, there exists a sequence {n_k} with n_k → ∞ and w₀ ∈ Ω(n_kx₀). Hence,

()

Next, we proceed the arguments by discussing the following two cases.

Case 1. For , we have from (90). Since max _w∈Ωq(w) is finite due to the compactness of Ω and the continuity of q(w), for k sufficiently large. Therefore, we obtain

()

Case 2. For , by a simple calculation, we have

()

where the inequality in the latter case comes from the fact that

. Thus,

()

This contradicts the level boundedness of r(x) since n_kx₀ → ∞.

The above conclusion is equivalent to say that for each , the matrix M(w) is a R₀-matrix. Finally, let us discuss a special case where the set-valued mapping Ω(x) has an explicit form, for example, Ω(x) = {w∣H(x, w) = 0 and G(x, w) ≥ 0}, where and . Then, the solution set can be further characterized.

Theorem 22. If Ω(x): = {w∣G(x, w) ≥ 0, H(x, w) = 0}, then

()

where

is defined as

and

Proof. Noting that the problem (2) is to find w ∈ ℝ^m and x ∈ ℝⁿ, such that

()

namely, to find w ∈ ℝ^m and x ∈ ℝⁿ satisfying

()

In other words,

()

Then, the desired result follows.

The foregoing result indicates that the set-valued complementarity problem is different from the classical complementarity problem, since it restricts that some components of the solution must be positive or zero, which is not required in the classical complementarity problems.

Moreover, the set-valued complementarity problem can be further reformulated to be an equation, that is, finding x ∈ ℝⁿ and w ∈ ℝ^m to satisfy the following equation

()

where

. Note that when A is a closed convex set, then θ(x) : = dist ²(x, A) is continuously differentiable, and ∇θ(x) = 2(x − Π_A(x)). This fact together with

being continuously differentiable implies the following immediately.

Theorem 23. Suppose that G and H are continuously differentiable, and ϕ is the Fischer-Burmeister function, then Γ is continuously differentiable and

()

where

()

Here 𝒟_a(x, F(x, w)) and 𝒟_b(x, F(x, w)) mean the sets of n × n diagonal matrices diag (a₁(x, F(x, w)), …, a_n(x, F(x, w))) and diag (b₁(x, F(x, w)),…,b_n(x, F(x, w))), respectively, and

()

5. Further Discussions

In this paper, we have paid much attention to the set-valued complementarity problems which posses rather different features from those of classical complementarity problems. As suggested by one referee, we here briefly discuss the relation between stochastic variational inequalities and the set-valued complementarity problems. Given F : ℝⁿ × Ξ → ℝ, X_ξ ⊂ ℝⁿ and Ξ ⊂ ℝ^l, a set representing future states of knowledge, the stochastic variational inequalities is to find x ∈ X_ξ, such that

()

, then the stochastic variational inequalities reduce to the stochastic complementarity problem as follows:

()

The optimization problem corresponding to stochastic complementarity problem is

()

When Ξ is a discrete set, say Ξ : = {ξ₁, ξ₂, …, ξ_v}, then

()

where P(ξ_i) is the probability of ξ_i. If the optimal value of (105) is zero, then it follows from (106) that (104) coincides with

()

When Ξ is a continuous set, then

()

where P(x) is the density function. In this case, (104) takes the form of

()

or equivalently there exists a subset Ξ₀ ⊂ Ξ with P(Ξ₀) = 0, such that

()

Hence the stochastic complementarity problem is, in certain extent, a semi-infinite complementarity problem (SICP).

Due to some major difference between set-valued complementarity problems and classical complementarity problems, there are still many interesting, important, and challenging questions for further investigation as below, to name a few.

(i)
How to extend other important concepts used in classical linear complementarity problems to set-valued cases (like P₀, P_*, Z, Q, Q₀, S, , copositive, column sufficient matrix, etc.)?
(ii)
How to propose an effective algorithm to solve (99)?
(iii)
Can we provide some sufficient conditions to ensure the existence of solutions? One possible direction is to use fixed-point theory. In fact, the set-valued complementarity problem is to find x ∈ ℝⁿ, such that
()

that is,

()

where

. Note that (112) is a fixed point of a set-valued mapping

, where I denotes the identify mapping.

Acknowledgments

The authors would like to thank three referees for their carefully reading and suggestions which help to improve this paper. J. Zhou is supported by National Natural Science Foundation of China (11101248, 11271233), Shandong Province Natural Science Foundation (ZR2010AQ026, ZR2012AM016), and Young Teacher Support Program of Shandong University of Technology. J. S. Chen is supported by National Science Council of Taiwan. G. M. Lee is supported by the National Research Foundation of Korea (NRF) Grant funded by the Korea government (MEST) (no. 2012-0006236).

References

1 Facchinei F. and Pang J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I and II, 2003, Springer, New York, NY, USA.
Google Scholar
2 Pang J. S. and Fukushima M., Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Computational Management Science. (2005) 2, no. 1, 21–56, 2-s2.0-20444502586, https://doi.org/10.1007/s10287-004-0010-0, ZBL1115.90059.
10.1007/s10287-004-0010-0
Google Scholar
3 Gowda M. S., On the extended linear complementarity problem, Mathematical Programming B. (1996) 72, no. 1, 33–50, 2-s2.0-0001993123, ZBL0853.90109.
10.1007/BF02592330
Web of Science® Google Scholar
4 Mangasarian O. L. and Pang J. S., The extended linear complementarity problem, SIAM Journal on Matrix Analysis and Application. (1995) 16, 359–368, https://doi.org/10.1137/S0895479893262734, ZBL0835.90103.
10.1137/S0895479893262734
Web of Science® Google Scholar
5 Pang J. S., O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, The implicit complementarity problem, Nonlinear Programming, 1981, 4 edition, Academic Press, New York, NY, USA, ZBL0534.90090.
Google Scholar
6 Noor M. A., Some developments in general variational inequalities, Applied Mathematics and Computation. (2004) 152, no. 1, 199–277, 2-s2.0-1842530697, https://doi.org/10.1016/S0096-3003(03)00558-7, ZBL1134.49304.
10.1016/S0096-3003(03)00558-7
Web of Science® Google Scholar
7 Noor M. A., Extended general variational inequalities, Applied Mathematics Letters. (2009) 22, no. 2, 182–185, 2-s2.0-56949083102, ZBL1163.49303.
10.1016/j.aml.2008.03.007
Web of Science® Google Scholar
8 Polak E., Optimization: Algorithms and Consistent Approximation, 1997, Springer, New York, NY, USA.
10.1007/978-1-4612-0663-7
Google Scholar
9 Rockafellar R. T., Wets R. J., and R. J., Variational Analysis, 1998, Springer, New York, NY, USA.
10.1007/978-3-642-02431-3
Web of Science® Google Scholar
10 Rockafellar R. T., Convex Analysis, 1970, Princeton University Press, Princeton, NJ, USA.
10.1515/9781400873173
Google Scholar
11 Aubin J. P. and Frankowska H., Set-Valued Analysis, 1990, Birkhauser, Boston, Mass, USA, ZBL0745.17013.
Google Scholar
12 Cottle R., Pang J. S., and Stone R., The Linear Complementarity Problem, 1992, Academic Press, New York, NY, USA.
Google Scholar
13 Fiedler M. and Pták V., Some generalizations of positive definiteness and monotonicity, Numerische Mathematik. (1966) 9, no. 2, 163–172, 2-s2.0-0001326068, https://doi.org/10.1007/BF02166034, ZBL0148.25801.
10.1007/BF02166034
Web of Science® Google Scholar
14 Chen X. and Fukushima M., Expected residual minimization method for stochastic linear complementarity problems, Mathematics of Operations Research. (2005) 30, no. 4, 1022–1038, 2-s2.0-31144459305, https://doi.org/10.1287/moor.1050.0160, ZBL1162.90527.
10.1287/moor.1050.0160
Web of Science® Google Scholar
15 Chen X., Zhang C., and Fukushima M., Robust solution of monotone stochastic linear complementarity problems, Mathematical Programming. (2009) 117, no. 1-2, 51–80, 2-s2.0-46749143296, https://doi.org/10.1007/s10107-007-0163-z, ZBL1165.90012.
10.1007/s10107-007-0163-z
Web of Science® Google Scholar
16 Fang H., Chen X., and Fukushima M., Stochastic R₀ matrix linear complementarity problems, SIAM Journal on Optimization. (2007) 18, no. 2, 482–506, 2-s2.0-42449155183, https://doi.org/10.1137/050630805.
10.1137/050630805
Web of Science® Google Scholar
17 Zhang C. and Chen X., Smoothing projected gradient method and its application to stochastic linear complementarity problems, SIAM Journal on Optimization. (2009) 20, no. 2, 627–649, 2-s2.0-70450260767, https://doi.org/10.1137/070702187, ZBL1204.65073.
10.1137/070702187
Web of Science® Google Scholar
18 Zhou J. C., Xiu N. H., and Chen J. S., Solution properties and error bounds for semi-infinite complementarity problems, Journal of Industrial and Management Optimization. (2013) 9, 99–115.
10.3934/jimo.2013.9.99
Web of Science® Google Scholar
19 Galantai A., Properties and construction of NCP functions, Computational Optimization and Applications. (2012) 52, 805–824, https://doi.org/10.1007/s10589-011-9428-9.
10.1007/s10589-011-9428-9
Web of Science® Google Scholar
20 Pang J. S., Error bounds in mathematical programming, Mathematical Programming B. (1997) 79, no. 1–3, 299–332, 2-s2.0-0000150038, ZBL0887.90165.
10.1007/BF02614322
Web of Science® Google Scholar
21 Chen X. and Xiang S., Computation of error bounds for P-matrix linear complementarity problems, Mathematical Programming. (2006) 106, no. 3, 513–525, 2-s2.0-33644513089, https://doi.org/10.1007/s10107-005-0645-9, ZBL1134.90043.
10.1007/s10107-005-0645-9
Web of Science® Google Scholar
22 Gabriel S. A. and More J. J., M. C. Ferris and J. S. Pang, Smoothing of mixed complementarity problems, Complementarityand Variational Problems, 1997, SIAM Publications, Philadelphia, Pa, USA, ZBL0886.90154.
Google Scholar

Citing Literature

All articles

On Set-Valued Complementarity Problems

Abstract

1. Motivations and Preliminaries

2. Focus on SVLCP (M, q, Ω)

3. Properties of Solution Sets

4. Merit Functions for SVNCP and SVLCP

5. Further Discussions

Acknowledgments

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

On Set-Valued Complementarity Problems

Abstract

1. Motivations and Preliminaries

2. Focus on SVLCP (M, q, Ω)

3. Properties of Solution Sets

4. Merit Functions for SVNCP and SVLCP

5. Further Discussions

Acknowledgments

References

Citing Literature

References

Related

Information