# On Set-Valued Complementarity Problems

Authors: Jinchuan Zhou; Jein-Shan Chen; Gue Myung Lee
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

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 onx. 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.


---

## Body

## 1. Motivations and Preliminaries

Theset-valued complementarity problem (SVCP) is to find x∈ℝn such that
(1)x≥0,y≥0,xTy=0,forsomey∈Θ(x),
where Θ:ℝ+n⇉ℝn 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∈ℝn, such that
(2)x≥0,F(x,w)≥0,xTF(x,w)=0,forsomew∈Ω(x),
where  F:ℝn×ℝm→ℝn and Ω:ℝn⇉ℝm are  a set-valued mapping. To see this, if letting
(3)Θ(x)=⋃w∈Ω(x){F(x,w)},
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∈ℝn, such that
(4)x≥0,F(x)≥0,〈x,F(x)〉=0.This corresponds toF(x,w):=F(x)+w and Ω(x)={0} for all  x∈ℝn. 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∈ℝn, such that
(5)x≥0,w≥0,xTw=0,withM1x-M2w∈P,whereM1,M2∈ℝm×n and P⊆ℝm are a polyhedron. This corresponds to F(x,w)=w and Ω(x)={w|M1x-M2w∈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  M2  being an identify matrix.(iii)
Implicit complementarity problem [5], which is to find  x,w∈ℝn and z∈ℝm, such that
(6)x≥0,w≥0,xTw=0,withF(x,w,z)=0,where  F:ℝ2n×m→ℝl. This can be rewritten as
(7)x≥0,w≥0,xTw=0,withwsatisfyingF(x,w,z)=0forsomez.
This is clearly an SVNCP(F,Ω) where  F(x,w)=w and  Ω(x)=∪z∈ℝm{w∣F(x,w,z)=0}. (iv)
Mixed nonlinear complementarity problem, which is to find  x∈ℝn, and w∈ℝm such that
(8)x≥0,F(x,w)≥0,〈x,F(x,w)〉=0,withG(x,w)=0.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:
(9)minf(x)s.t.gi(x)≤0,i=1,2,…,m,hj(x)=0,j=1,…,l.
To see this, we first write out the KKT conditions as follows:
(10)∇f(x)+∑i=1mλi∇gi(x)+∑j=1lμj∇hj(x)=0,h(x)=0,g(x)≤0,λ≥0,〈λ,g(x)〉=0,
where g(x):=(g1(x),…,gm(x)), h(x):=(h1(x),…,hl(x)), and λ:=(λ1,…,λm). Then, letting  w:=(λ,μ), F(x,w):=-g(x),  and
(11)G(x,w):=(∇f(x)+∑i=1mλi∇gi(x)+∑j=1lμ∇hj(x)h(x))
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  ℝn to itself and a point-to-set map K from ℝn into subsets of  ℝn, the Quasi-variational inequality QVI(K,F) is to find a vector  x∈K(x),  such that
(12)〈F(x),y-x〉≥0,∀y∈K(x).It is well-known that QVI(K,F) reduces to the classical nonlinear complementarity problem when  K(x) is independent of  x, say,  K(x)=ℝ+n for all  x. Now, let us explain why it is related to SVNCP(F,Ω). To this end, given x∈ℝn, we define  I(x)={i∣Fi(x)>0}, and let
(13)K(x)={x∣xi≥0fori∈I∖I(x)andxi=0fori∈I(x)}.
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 Fi(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=βei  in (12) with β being an arbitrarily positive scalar, we have βFi(x)≥F(x)Tx. Since β can be made sufficiently large, it implies that  Fi(x)≥0. Thus, we obtain F(x)Tx≥0. In summary, under such case, QVI(K,F) becomes
(14)x≥0,F(x)≥0,xTF(x)=0,withx∈K(x)
which is an SVNCP(F,Ω). (vi)
Min-max programming [8], which is to solve the following problem:
(15)minx∈ℝ+nmaxw∈Ωf(x,w),where  f:ℝn×Ω→ℝ is a continuously differentiable function, and  Ω is a compact subset in ℝm. First, we define ψ(x):=maxw∈Ω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
(16)ψ′(x*;x-x*)=maxw∈Ω(x*)〈∇xf(x*,w),x-x*〉≥0,∀x∈ℝ+n,
which is equivalent to
(17)infx∈ℝ+nmaxw∈Ω(x*)〈∇xf(x*,w),x-x*〉=0,
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
(18)x*≥0,∇xf(x*,w*)≥0,〈∇xf(x*,w*),x*〉=0.Proof.
Note first that for eachx the inner problem
(19)ψ(x):=maxw∈Ωf(x,w)
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
(20)h(w):=〈∇xf(x*,w),x-x*〉
is concave over Ω(x*). Indeed, for  w1,w2∈Ω(x*) and α∈[0,1], we have
(21)h(αw1+(1-α)w2)=〈∇xf(x*,αw1+(1-α)w2),x-x*〉=limt↓0(f(x*+t(x-x*),αw1+(1-α)w2)-f(x*,αw1+(1-α)w2))(t)-1=limt↓0f(x*+t(x-x*),αw1+(1-α)w2)-ψ(x*)t≥limt↓0(αf(x*+t(x-x*),w1)+(1-α)×f(x*+t(x-x*),w2)-ψ(x*))(t)-1=limt↓0α[f(x*+t(x-x*),w1)-f(x*,w1)]t+limt↓0(1-α)[f(x*+t(x-x*),w2)-f(x*,w2)]t=α〈∇xf(x*,w1),x-x*〉+(1-α)×〈∇xf(x*,w2),x-x*〉=αh(w1)+(1-α)h(w2),
where we use the fact that αw1+(1-α)w2∈Ω(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
(22)maxw∈Ω(x*)infx∈ℝ+n〈∇xf(x*,w),x-x*〉=0.
Hence, for arbitrary  ε>0, we can find  wε∈Ω(x*), such that
(23)infx∈ℝ+n〈∇xf(x*,wε),x-x*〉≥-ε,
that is,
(24)〈∇xf(x*,wε),x-x*〉≥-ε,∀x∈ℝ+n.
In particular, plugging in  x=0  in (24) implies
(25)〈∇xf(x*,wε),x*〉≤ε.
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
(26)〈∇xf(x*,w*),x*〉≤0.
Now, let x=x*+kei∈ℝ+n. It follows from (24) that
(27)(∇xf(x*,wε))i≥-εk,
which implies that (∇xf(x*,wε))i≥0 by letting k→∞, and hence (∇xf(x*,w*))i≥0 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 anyx,y∈ℝn, the inner product is denoted by xTy or 〈x,y〉. We write x≥y (or x>y) if xi≥yi (or  xi>yi) for all  i=1,2,…,n. Let e be the vector with all components being  1, and let ei be the i-row of identity matrix. Denote N∞:=∪n=1∞{{n,n+1,…}}. 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→ℝn. For a continuously differentiable function F:ℝn×ℝm→ℝl, we denote the l×n Jacobian matrix of partial derivatives of F at (x-,w-) with respect to x by JxF(x-,w-), whereas the transposed Jacobian is denoted by ∇xF(x-,w-). For a mapping  H:ℝn→ℝm, define
(28)liminfx→x-H(x):=(liminfx→x-H1(x)liminfx→x-H2(x)⋮liminfx→x-Hm(x)).
Given a set-valued mapping  M:ℝn⇉ℝm, define
(29)limsupx→x-M(x):={u∣∃xn→x-,∃un→uwithun∈M(xn)},liminfx→x-M(x):={u∀xn→x-,∃un→uwithun∈M(xn)}.
We say that M is  outer semicontinuous at x-, if
(30)limsupx→x-M(x)⊂M(x-),
and  inner semicontinuous at x- if
(31)liminfx→x-M(x)⊃M(x-).
We say that M is continuous at x- if it is both outer semicontinuous and inner semicontinuous at x-. For more details about these functions, please refer to [9, 11]. Throughout this paper, we always assume that the set-valued mapping Ω:ℝn⇉ℝm is closed valued; that is, Ω(x) is closed for all x∈ℝn [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 asP-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 matrixM∈ℝn×n is said to be an  S-matrix if there exists x∈ℝn, such that
(32)x>0,Mx>0.Note thatM∈ℝn×n is an S-matrix, if and only if the classical linear complementarity problem LCP(M,q) is feasible for all q∈ℝn, see [12, Prop. 3.1.5]. Moreover, the above condition in Definition 2 is equivalent to
(33)x≥0,Mx>0,
see [13, Remark  2.2]. However, such equivalence fails to hold for its corresponding cases in set-valued complementarity problem. In other words,
(34)x>0,M(w)x>0,forsomew∈Ω(x)
is not equivalent to
(35)x≥0,M(w)x>0,forsomew∈Ω(x).
It is clear that (34) implies (35). But, the converse implication does not hold, which is illustrated in Example 3.Example 3.
Let(36)M(w)=(w00w),Ω(x)={{0,1},x=(1,0)∈ℝ2;{0},otherwise.IfM(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)=maxw∈Ω(x)M(w)x, and denote by ai(x) the ith row of M(w). Hence Hi(x)=maxw∈Ω(x)ai(x)Tx. With this, suppose x0 is an arbitrary but fixed point, we know that for any  ε>0, there exists w0∈Ω(x0) such that ai(w0)Tx0>Hi(x0)-ε. Since Ω(x) is inner semi-continuous, for any xn→x0, there exists wn∈Ω(xn) satisfying wn→w0. This implies
(37)Hi(xn)=maxw∈Ω(xn)ai(w)Txn≥ai(wn)Txn.
Then, taking the lower limit yields
(38)liminfn→∞Hi(xn)≥limn→∞ai(wn)Txn=ai(w0)Tx0>Hi(x0)-ε,
where the equality follows from the continuity of  ai(w), which is ensured by the continuity of M(w). Because  ε>0 is arbitrary, and {xn} is an arbitrary sequence converging to x0, we obtain
(39)liminfx→x0Hi(x)≥Hi(x0),
which says Hi is lower semi-continuous. This further implies
(40)liminfx→x0H(x)=(liminfx→x0H1(x)⋮liminfx→x0Hn(x))≥(H1(x0)⋮Hn(x0))=H(x0),
that is,
(41)liminfx→x0maxw∈Ω(x)M(w)x≥maxw∈Ω(x0)M(w)x0.
If x- satisfies (35), then
(42)x-≥0,M(w-)x->0,forsomew-∈Ω(x-)
which is equivalent to
(43)x-≥0,H(x-)>0.
On the other hand, liminfλ→0+H(x-+λe)≥H(x-)>0, and x-+λe>0 for λ>0. By taking λ>0 small enough, we know  x-+λe 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∈ℝn if and only if M∈ℝn×n is a S-matrix; that is, there exists x∈ℝn, such that
(44)x>0,Mx>0.
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∈ℝn, such that
(45)x≥0,M(w)x>0,forsomew∈⋂N~∈N∞‍⋃n∈N~‍Ω(nx),
then  SVLCP(M,q,Ω) is feasible for all q:ℝm→ℝn being bounded from below.Proof.
Letq be any mapping from ℝm to ℝn being bounded from below, that is, there exists β∈ℝ, such that q(w)≥βe. Suppose that x0 and w0 satisfy (45), which means
(46)x0≥0,M(w0)x0>0,w0∈⋂N~∈N∞‍⋃n∈N~‍Ω(nx0).
Then, for any  N~∈N∞, we have  w0∈∪n∈N~Ω(nx0). In particular, we observe the following:  (1)
if takingN~={1,2,…,}, then there exists n1, such that w0∈Ω(n1x0);(2)
if takingN~={n1+1,…,}, then there exists n2 with n2>n1, such that w0∈Ω(n2x0).
Repeating the above process yields a sequence{nk}, such that w0∈Ω(nkx0) and nk→∞. Since M(w0)x0>0, it ensures the existence of α>0, such that M(w0)x0>αe. Taking k large enough to satisfy nk>max{-β/α,0} gives αnke>-βe≥-q(w). Then, it implies that
(47)M(w0)nkx0>αnke≥-q(w),
and hence
(48)nkx0≥0,M(w0)(nkx0)+q(w)>0,w0∈Ω(nkx0),
which says nkx0 is a feasible point of SVLCP(M,q,Ω).Definition 6.
A matrixM∈ℝn×n is said to be a  P-matrix if all its principal minors are positive, or equivalently [12, Theorem  3.3.4],
(49)∀x≠0,∃k∈{1,2,…,n}suchthatxk(Mx)k>0.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:
(50)x≥0,Mx>0.
Their respective corresponding conditions in set-valued complementarity problem are
(51)∀x≠0,∃k∈{1,…,n}suchthatxk(M(w)x)k>0,forsomew∈Ω(x),(52)x≥0,M(w)x>forsomew∈Ω(x).
Example 7 shows that the aforementioned implication is not valid as well in set-valued complementarity problem.Example 7.
Let(53)M(w)=(w00-w),Ω(x)={-1,x1=0;1,otherwise.Forx1≠0, we have M(w)x=(x1,-x2), and hence x1(M(w)x)1=x12>0. For x1=0, we know x2≠0 (since x≠0) which says M(w)x=(-x1,x2), and hence x2(M(w)x)2=x22>0. Therefore, condition (51) is satisfied. But, condition (52) fails to hold because M(w)x=(x1,-x2) or (-x1,x2). Hence, M(w)x>0 implies that x2<0 or x1<0, which contradicts with x≥0.Definition 8.
A matrixM∈ℝn×n is said to be  semimonotone if
(54)∀0≠x≥0⇒∃xk>0suchthat(Mx)k≥0.For the classical linear complementarity problem, we know thatM 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 nonzerox≥0,
(55)∃xk>0suchthat(M(w)x)k≥0∀w∈Ω(x);(b)
weakly semimonotone if for any nonzerox≥0,
(56)∃xk>0suchthat(M(w)x)k≥0forsomew∈Ω(x).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 mappingq, x=0 is a solution of SVLCP(M,q,Ω). Suppose there is another nonzero solution x-, that is, ∃w-∈Ω(x-), such that
(57)x-≥0,M(w-)x-+q(w-)≥0,x-T(M(x-)+q(w-))=0.
It follows from (55) that there exists k∈{1,2,…,n}, such that x-k>0 and (M(w-)x-)k≥0, and hence (M(w-)x-+q(w-))k>0, which contradicts condition (57).
(b) Suppose{M(w)∣w∈Ω(x)} is not weakly semi-monotone. Then, there exists a nonzero  x-≥0, for all  k∈I+(x-):={i∣x-i>0}, (M(w)x-)k<0 for all w∈Ω(x-). Choose  w-∈Ω(x-). Let q(w)=1 for all w≠w- and
(58)qk(w-)={-(M(w-)x-)k,k∈I+(x-);max{(M(w-)x-)k,0}+1,otherwise.
Therefore, q(w)>0 for all w. According to the above construction, we have
(59)x-≥0,M(w-)x-+q(w-)≥0,x-T(M(w-)x-+q(w-))=0,withw-∈Ω(x-),
that is, the nonzero vector x- is a solution of SVLCP(M,q,Ω), which is a contradiction.Theorem10(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(60)M(w)=(-w10001100),Ω(x)={0,1}.For any nonzerox=(x1,x2,x3)≥0, we have M(0)x=(x2,x3,x1)≥0. If we plug in q=(1,1,1), by a simple calculation, x=(1,0,0) satisfies
(61)x≥0,M(1)x+q≥0,xT(M(1)+q)=0
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 functionf:ℝn→ℝ 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⊂ℝn is denoted by ΠA(x), that is, ΠA(x):=argminy∈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 vectorw∈Ω is involved, for example, the stochastic complementarity problem [14–17], to find x∈ℝn, such that
(62)x≥0,F(x,w)≥0,xTF(x,w)=0,a.e.w∈Ω,
where w is a random vector in a given probability space and thesemi-infinite complementarity problem [18] to find x∈ℝn, such that
(63)x≥0,F(x,w)≥0,xTF(x,w)=0,∀w∈Ω,
which we denote it by SINCP(F,Ω). In addition, the authors introduce the following two complementarity problems in [18] to find x∈ℝn, such that
(64)x≥0,Fmin(x)≥0,xTFmin(x)=0,x≥0,Fmax(x)≥0,xTFmax(x)=0,
where
(65)Fmin(x):=(minw∈ΩF1(x,w)⋮minw∈ΩFn(x,w)),(66)Fmax(x):=(maxw∈ΩF1(x,w)⋮maxw∈ΩFn(x,w)).
These two problems are denoted by NCP(Fmin) and NCP(Fmax), 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)
SOL^(F,Ω) means the solution set of SINCP(F,Ω),(iv)
SOL(Fmin) means the solution set of NCP(Fmin),(v)
SOL(Fmax) means the solution set of NCP(Fmax).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∈ℝn.It is easy to see that the solution set of SINCP(F,Ω) is ⋂w∈Ω‍SOL(Fw), but that of SVNCP(f,Ω) is ⋃w∈Ω‍SOL(Fw), where Fw(x):=F(x,w). Hence, the solution set of SINCP(F,Ω) is included in that of SVNCP(F,Ω). In other words, we have
(67)SOL^(F,Ω)⊆SOL(F,Ω).
The inclusion (67) can be strict as shown in Example 12.Example 12.
LetF(x,w)=(w,1) and Ω(x)=[0,1]. Then, we can verify that SOL^(F,Ω)={0,0}, whereas SOL(F,Ω)={x∣x1≥0,x2=0}.However, the solution set of SVNCP(F,Ω), NCP(Fmin), and NCP(Fmax) are not included each other. This is illustrated in Examples 13–14.Example 13.
SOL
(
F
min
)
⊈
SOL
(
F
,
Ω
) and SOL(F,Ω)⊈SOL(Fmin).  (a)
LetF(x,w)=(1-w,w)  and Ω=[0,1]. Then, SOL(Fmin)=ℝ+2,  SOL(F,Ω)=⋃w∈Ω‍SOL(Fw)={(x1,x2)T∣x1≥0,x2≥0,andx1x2=0}.(b)
LetF(x,w)=(w-1,x2) and Ω=[0,1]. Then, SOL(Fmin)=∅ and SOL(F,Ω)={(x1,x2)∣x1≥0,x2=0}.Example 14.
SOL
(
F
max
)
⊈
SOL
(
F
,
Ω
) and SOL(F,Ω)⊈SOL(Fmax).  (a)
LetF(x,w)=(w-1,-w) and Ω=[0,1]. Then, SOL(Fmax)=ℝ+2 and  SOL(F,Ω)=∅.(b)
LetF(x,w)=(w,-w) and Ω=[0,1]. Then,  SOL(Fmax)={(x1,x2)∣x1=0,x2≥0} and  SOL(F,Ω)=ℝ+2.Similarly, Example15 shows that the solution set of NCP (Fmax) and NCP(Fmin) cannot be included each other.Example 15.
SOL
(
F
max
)
⊈
SOL
(
F
min
) and SOL(Fmin)⊈SOL(Fmax).  (a)
LetF(x,w)=(w-1,0) and Ω=[0,1]. Then,  SOL(Fmin)=∅ and  SOL(Fmax)=ℝ+2.(b)
LetF(x,w)=(w,w) and Ω=[0,1]. Then, SOL(Fmin)=ℝ+2 and SOL(Fmax)={(0,0)}.In spite of these, we obtain some results which describe the relationship among them.Theorem 16.
LetΩ(x)=Ω for all x∈ℝn. Then, we have  (a)
SOL(F,Ω)∩{x∣Fmin(x)≥0}⊆SOL(Fmin);(b)
SOL(Fmax)∩{x∣F(x,w)≥0forsomew∈Ω}⊆SOL(F,Ω);(c)
SOL(Fmin)∩{x∣xTFmax(x)≤0}=SOL(Fmax)∩{x∣Fmin(x)≥0}⊆SOL(F,Ω).Proof.
Parts (a) and (b) follow immediately from the fact(68)xTFmin(x)≤xTF(x,w)≤xTFmax(x)∀w∈Ω,x∈ℝ+n.
Part (c) is from (67), since the two sets in the left side of (c) is SOL^(F,Ω) by [18].For further characterizing the solution sets, we recall that for a set-valued mappingM:ℝn⇉ℝm, its inverse mapping (see [9, Chapter 5]) is defined as
(69)M-1(y):={x∣y∈M(x)}.Theorem 17.
For  SVNCP(F,Ω), we have
(70)SOL(F,Ω)=⋃w∈ℝm‍[SOL(Fw)∩Ω-1(w)].Proof.
In fact, the desired result follows from(71)SOL(F,Ω)={x∣x∈SOL(Fw)andw∈Ω(x)forsomew∈ℝm}={x∣x∈SOL(Fw)andx∈Ω-1(w)forsomew∈ℝm}=⋃w∈ℝm‍[SOL(Fw)∩Ω-1(w)],
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ϕ:ℝ2→ℝ is called an NCP function if it satisfies
(72)ϕ(a,b)=0⟺a≥0,b≥0,ab=0.
For example, the natural residual ϕNR(a,b)=min{a,b} and the Fischer-Burmeister function ϕFB(a,b)=a2+b2-(a+b) 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:ℝn→ℝ is called a merit (or residual) function for a complementarity problem if f(x)≥0 for all x∈ℝn and f(x)=0 if and only if x is a solution of the complementarity problem. Given an NCP-function ϕ, we define
(73)r(x,w)≔∥Φ(x,F(x,w))∥whereΦ(x,y):=(ϕ(x1,y1),…,ϕ(xn,yn)).
Then, it is not hard to verify that the function given by
(74)r(x):=minw∈Ω(x)r(x,w)
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
(75)dist(x,SOL(F,Ω))≤c·r(x),∀x∈ℝn.
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∈ℝn, and that for each w∈Ω, r(x,w) is a global error bound of NCP(Fw) with the modulus η(w)>0, that is,
(76)dist(x,SOL(Fw))≤η(w)r(x,w),∀x∈ℝn.
In addition, if
(77)η:=maxw∈Ωη(w)<+∞,
then r(x)=minw∈Ωr(x,w) provides a global error bound for  SVNCP(F,Ω) with the modulus η.Proof.
Noticing that ifΩ(x)=Ω for all x∈ℝn, then
(78)Ω-1(w)={ℝn,w∈Ω,∅,w∉Ω.
It then follows from Theorem 17 that
(79)SOL(F,Ω)=⋃w∈ℝm‍[SOL(Fw)∩Ω-1(w)]=⋃w∈Ω‍SOL(Fw).
Therefore,
(80)dist(x,SOL(F,Ω))=dist(x,⋃w∈Ω‍SOL(Fw))≤minw∈Ωdist(x,SOL(Fw))≤minw∈Ωη(w)·r(x,w)≤minw∈Ωmaxw∈Ωη(w)·r(x,w)=maxw∈Ωη(w)minw∈Ωr(x,w)=η·r(x).
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,
(81)η(w)=maxd∈[0,1]n∥(I-D+DM(w))-1∥,see [21, 22]. Hence, we see that
(82)η=maxd∈[0,1]nw∈Ω∥(I-D+DM(w))-1∥
is well defined because M(w) is continuous, and Ω is compact.For simplification of notations, we writex→∞ instead of ∥x∥→∞. We now introduce the following definitions which are similar to (29):
(83)limsupx→∞M(x):={u∣∃xn→∞,∃un→uwithun∈M(xn)},liminfx→∞M(x):={u∀xn→∞,∃un→uwithun∈M(xn)}.Definition 19.
For  SVLCP(M,q,Ω), the set of matrices {M(w)∣w∈Ω(x)} is said to have the limit-R0 property if
(84)x≥0,M(w)x≥0,xTM(w)x=0forsomew∈limsupx→∞Ω(x)⇒x=0.In the case of a linear complementarity problem, that is,Ω(x) is a fixed single-point set, Definition 19 coincides with that of  R0-matrix.Theorem 20.
For  SVLCP(M,q,Ω), suppose that there exists a bounded set Ω, such that Ω(x)⊂Ω for all x∈ℝn, and M(w) and q(w) are continuous on Ω. If the set of matrices {M(w)∣w∈Ω(x)} has the limit-R0 property, then the merit function r(x)=minw∈Ω(x)∥min{x,M(w)x+q(w)}∥ is level bounded.Proof.
We argue this result by contradiction. Suppose there exists a sequence{xn} satisfying ∥xn∥→∞, and r(xn) is bounded. Then,
(85)r(xn)∥xn∥=minw∈Ω(xn)∥min{xn∥xn∥,M(w)xn∥xn∥+q(w)∥xn∥}∥=∥min{xn∥xn∥,M(wn)xn∥xn∥+q(wn)∥xn∥}∥,
where we assume the minimizer is attained at wn∈Ω(xn), whose existence is ensured by the compactness of Ω(xn), since Ω(x) is closed and Ω is bounded. Taking a subsequence if necessary, we can assume that {xn/∥xn∥} and {wn} are both convergent in which x- and w- represent their corresponding limit point. Thus, we have
(86)w-∈limsupn→∞Ω(xn)⊂limsup∥x∥→∞Ω(x).
Now, taking the limit in (85) yields
(87)∥min{x-,M(w-)x-}∥=0,
where we have used the fact that q(wn)/∥xn∥→0, because q is continuous, and wn∈Ω is bounded. This contradicts (84) since x- is a nonzero vector.Note that the condition (84) is equivalent to
(88)⋃w∈limsupx→∞Ω(x)‍SOL(M(w))={0},
which is also equivalent to saying that each matrix M(w) for w∈limsupx→∞Ω(x) is a R0-matrix.Theorem 21.
For  SVLCP(M,q,Ω), suppose that there exists a compact set Ω, such that Ω(x)⊂Ω for all x∈ℝn, and M(w) and q(w) are continuous on Ω. If r(x)=minw∈Ω(x)∥min{x,M(w)x+q(w)}∥ is level bounded, then the following implication holds
(89)x≥0,M(w)x≥0,xTM(w)x=0forsomew∈⋂N~∈N∞‍⋃n∈N~‍Ω(nx)⇒x=0.Proof.
Suppose that there exist a nonzero vectorx0,  and w0∈∩N~∈N∞∪n∈N~Ω(nx0), such that
(90)x0≥0,M(w0)x0≥0,x0TM(w0)x0=0.
Similar to the argument as in Theorem 5, there exists a sequence {nk} with nk→∞ and w0∈Ω(nkx0). Hence,
(91)r(nkx0)=minw∈Ω(nkx0)∥min{nkx0,nkM(w)x0+q(w)}∥≤∥min{nkx0,nkM(w0)x0+q(w0)}∥≤∑i=1n∥min{nk(x0)i,nk(M(w0)x0)i+q(w0)i}∥.
Next, we proceed the arguments by discussing the following two cases.
Case1. For (x0)i>0, we have (M(w0)x0)i=0 from (90). Since maxw∈Ωq(w) is finite due to the compactness of Ω and the continuity of q(w), nk(x0)i>maxw∈Ωq(w) for k sufficiently large. Therefore, we obtain
(92)∥min{nk(x0)i,nk(M(w0)x0)i+qi(w0)}∥=∥qi(w0)∥.
Case2. For (x0)i=0, by a simple calculation, we have
(93)∥min{nk(x0)i,nk(M(w0)x0)i+qi(w0)}∥×{=0,ifnk(M(w0)x0)i+qi(w0)≥0,≤∥qi(w0)∥,ifnk(M(w0)x0)i+qi(w0)<0,},
where the inequality in the latter case comes from the fact that qi(w0)≤nk(M(w0)x0)i+qi(w0)<0. Thus,
(94)r(nkx0)≤∑n=1n∥qi(w0)∥.
This contradicts the level boundedness of r(x) since  nkx0→∞.The above conclusion is equivalent to say that for eachw∈∩N~∈N∞∪n∈N~Ω(nx), the matrix M(w) is a R0-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)=0andG(x,w)≥0}, where H:ℝn×ℝm→ℝl1 and G:ℝn×ℝm→ℝl2. Then, the solution set can be further characterized.Theorem 22.
IfΩ(x):={w∣G(x,w)≥0,H(x,w)=0}, then
(95)SOL(F,Ω)=⋃w∈ℝm‍{x∣(x0α)∈SOL(Θw)=⋃w∈ℝm‍withα∈ℝ++l2and0∈ℝl1(x0α)},
where Θw:ℝn→ℝn+l1+l2 is defined as Θw(x):=(F(x,w)G(x,w)H(x,w)) and ℝ++l2:={α∈ℝl2∣αi>0foralli=1,…,l2}.Proof.
Noting that the problem (2) is to find w∈ℝm and x∈ℝn, such that
(96)x≥0,F(x,w)≥0,〈F(x,w),x〉=0,G(x,w)≥0,H(x,w)=0,
namely, to find w∈ℝm and x∈ℝn satisfying
(97)x≥0,F(x,w)≥0,〈F(x,w),x〉=0,0≥0,G(x,w)≥0,0·G(x,w)=0,α>0,H(x,w)≥0,〈α,H(x,w)〉=0.
In other words,
(98)(x0α)≥0,(F(x,w)G(x,w)H(x,w))≥0,(x0α)T(F(x,w)G(x,w)H(x,w))=0.
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, findingx∈ℝn and w∈ℝm to satisfy the following equation
(99)Γ(x,w)=(ξ(x,w)H(x,w)dist2(G(x,w)∣ℝ+l2))=0,
where ξ(x,w)=(1/2)∥ΦFB(x,F(x,w))∥2. Note that when A is a closed convex set, then θ(x):=dist2(x,A) is continuously differentiable, and ∇θ(x)=2(x-ΠA(x)). This fact together with ∥ϕFB∥2 being continuously differentiable implies the following immediately.Theorem 23.
Suppose thatG and H are continuously differentiable, and ϕ is the Fischer-Burmeister function, then  Γ is continuously differentiable and
(100)JT(x,w)=(Jxξ(x,w)JxH(x,w)2(G(x,w)-∏ℝ+l2‍(G(x,w)))TJxG(x,w)Jwξ(x,w)JwH(x,w)2(G(x,w)-∏ℝ+l2‍(G(x,w)))TJwG(x,w)),
where
(101)Jxξ(x,w)=ΦFB(x,F(x,w))T×[𝒟a(x,F(x,w))+𝒟b(x,F(x,w))JxF(x,F(x,w))],Jwξ(x,w)=ΦFB(x,F(x,w))T𝒟b(x,F(x,w))×JwF(x,w).
Here 𝒟a(x,F(x,w)) and 𝒟b(x,F(x,w)) mean the sets of  n × n diagonal matrices diag (a1(x,F(x,w)),…,an(x,F(x,w))) and diag (b1(x,F(x,w)),…,bn(x,F(x,w))), respectively, and
(102)(ai(x,F(x,w)),bi(x,F(x,w))){=(xi,Fi(x,w))xi2+Fi2(x,w)-(1,1),if(xi,Fi(x,w))≠0,∈⋃θ∈[0,2π]‍{cosθ,sinθ}-(1,1),if(xi,Fi(x,w))=0.


## 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. GivenF:ℝn×Ξ→ℝ, Xξ⊂ℝn and Ξ⊂ℝl, a set representing future states of knowledge, the stochastic variational inequalities is to find x∈Xξ, such that
(103)(y-x)TF(x,ξ)≥0,∀y∈Xξ,ξ∈Ξ.
If Xξ=ℝ+n, then the stochastic variational inequalities reduce to the stochastic complementarity problem as follows:
(104)x≥0,F(x,ξ)≥0,xTF(x,ξ)=0,ξ∈Ξ.
The optimization problem corresponding to stochastic complementarity problem is
(105)minx∈ℝ+n𝔼{∥Φ(x,F(x,ξ))∥}.
When Ξ is a discrete set, say Ξ:={ξ1,ξ2,…,ξv}, then
(106)𝔼{∥Φ(x,F(x,ξ))∥}=∑i=1vP(ξi)∥Φ(x,F(x,ξi))∥,
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
(107)x≥0,F(x,ξi)≥0,xTF(x,ξi)=0,∀ξi∈ΞsatisfyingP(ξi)>0.
When Ξ is a continuous set, then
(108)𝔼{∥Φ(x,F(x,ξ))∥}=∫Ω∥Φ(x,F(x,ξi))∥P(x)dx,
where P(x) is the density function. In this case, (104) takes the form of
(109)x≥0,F(x,ξ)≥0,xTF(x,ξ)=0,a.e.ξ∈Ξ,
or equivalently there exists a subset Ξ0⊂Ξ with P(Ξ0)=0, such that
(110)x≥0,F(x,ξ)≥0,xTF(x,ξ)=0,∀ξ∈Ξ∖Ξ0.
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 (likeP0, P*, Z, Q, Q0, S, 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 usefixed-point theory. In fact, the set-valued complementarity problem is to find x∈ℝn, such that
(111)x=max{0,x-F(x,w)}=Πℝ+n(x-F(x,w))forsomew∈Ω(x),that is,
(112)x∈Πℝ+n(x-F~(x)),
where F~(x):=⋃w∈Ω(x)‍F(x,w). Note that (112) is a fixed point of a set-valued mapping Πℝ+n(I-F~), where I denotes the identify mapping.



---

*Source: 105930-2013-02-12.xml*