# Properties of Expected Residual Minimization Model for a Class of Stochastic Complementarity Problems

Authors: Mei-Ju Luo; Yuan Lu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Expected residual minimization (ERM) model which minimizes an expected residual function defined by an NCP function has been studied in the literature for solving stochastic complementarity problems. In this paper, we first give the definitions of stochasticP-function, stochastic P0-function, and stochastic uniformly P-function. Furthermore, the conditions such that the function is a stochastic PP0-function are considered. We then study the boundedness of solution set and global error bounds of the expected residual functions defined by the “Fischer-Burmeister” (FB) function and “min” function. The conclusion indicates that solutions of the ERM model are robust in the sense that they may have a minimum sensitivity with respect to random parameter variations in stochastic complementarity problems. On the other hand, we employ quasi-Monte Carlo methods and derivative-free methods to solve ERM model.


---

## Body

## 1. Introduction

Given a vector-valued functionF:Rn×Ω→Rn, the stochastic complementarity problems, denoted by SCP(F(x,ω)), are to find a vector x* such that
(1)x*≥0,F(x*,ω)≥0,(x*)TF(x*,ω)=0,ω∈Ωa.s.,
where ω∈Ω⊆Rm is a random vector with given probability distribution 𝒫 and “a.s." means “almost surely" under the given probability measure. Particularly, when F is an affine function of x for any ω, that is,
(2)F(x,ω)=M(ω)x+q(ω),ω∈Ω,
where M(ω)∈Rn×n and q(ω)∈Rn, the SCP(F(x,ω)) is called stochastic linear complementarity problems, denoted by SLCP(M(ω),q(ω)). Correspondingly, problem (1) is called stochastic nonlinear complementarity problem, denoted by SNCP(F(x,ω)) if F can not be denoted by an affine function of x for any ω. The deterministic problems, which are called complementarity problems (denoted by CP(F(x))), have been intensively studied. More information about theoretical analysis, numerical algorithms and applications especially in economics and engineering can be found in comprehensive books [1, 2].In practical applications, some elements may involve stochastic factors. In fact, due to stochastic factors, the function value ofF depends not only on x, but also on random vectors. Hence, problem (1) does not have solution in general for almost all ω∈Ω. To solve these problems, researchers focus on giving reasonable deterministic reformulations for SCP(F(x,ω)). Certainly, different deterministic formulations may yield different solutions that are optimal in different senses. In the study of SCP(F(x,ω)), three types of formulations have been proposed; the expected value (EV) formulation, the expected residual minimization (ERM) formulation, and the SMPEC formulation [3].The EV formulation is studied by Gürkan et al. [4]. The problem considered in [4] is actually a stochastic variational inequality problem. When applied to the SCP(F(x,ω)), the EV model can be stated as follows:
(3)x*≥0,E[F(x*,ω)]≥0,(x*)TE[F(x*,ω)]=0,
where E means expectation with respect to ω.The ERM model is first proposed by Chen and Fukushima [5] for solving the SLCP(M(ω),q(ω)). By employing an NCP function ϕ, the SCP(F(x,ω)) (1) is transformed equivalently to the stochastic equations
(4)Φ(x,ω)=0,ω∈Ωa.s.,
where Φ:Rn×Ω→Rn is defined by
(5)Φ(x,ω)∶=(ϕ(x1,F1(x,ω))⋮ϕ(xn,Fn(x,ω))),
and xi denotes the ith component of the vector x. Here ϕ:Rn→R is an NCP function which has the property
(6)ϕ(a,b)=0⟺a≥0,b≥0,ab=0.
Then the ERM formulation for (1) is given by
(7)minx∈R+nθ(x)∶=E[∥Φ(x,ω)∥2].
The NCP functions employed in [5] include the Fischer-Burmeister function, which is defined by
(8)ϕFB(a,b):=a2+b2-(a+b)
and the min function
(9)ϕmin(a,b)∶=min{a,b}.
In particular, it is known [6, 7] that there exist the following relations between these two functions:
(10)22+2|ϕmin|≤|ϕFB|≤(2+2)|ϕmin|.
As observed in [5], the ERM formulations with different NCP functions may have different properties. Subsequently, the ERM formulation for SCP(F(x,ω)) has been studied in [6, 8–13]. Note that Fang et al. [8] propose a new concept of stochastic matrice: M(·) is called a stochastic R0 matrix if
(11)𝒫{ω:x≥0,M(ω)x≥0,xTM(ω)x=0}=1⟹x=0.
Moreover, Zhang and Chen [11] introduce a new concept of stochastic R0 function, which can be regarded as a generalization of the stochastic R0 matrix given in [8].Throughout this paper, we suppose that the sample spaceΩ is nonempty and compact set and that the function F(x,ω) is continuous with respect to x and ω. On the other hand, we will use the following notations: I(x)={i:xi=0} and J(x)={i:xi≠0} for a given vector x∈Rn. 〈l,n〉 represents the set {l,l+1,…,l+n} for natural numbers l and u with l<u. x+=max{x,0} for any given vector x. ∥·∥ refers to the Euclidean norm.The remainder of the paper is organized as follows: in Section2, we introduce the concepts of a stochastic P-function, a stochastic P0-function, and a stochastic uniformly P-function, which can be regarded as a generalization of the deterministic P, P0-function, and uniformly P-function or an extension of stochastic P matrix and stochastic P0 matrix [14]. In addition, some properties of a stochastic P(P0)-function are given. In Section 3, we show the sufficient conditions for the solution set of ERM problem to be nonempty and bounded. In Section 4, we discuss error bounds of SCP(F(x,ω)). In Section 5, an algorithm will be given to solve ERM model. We then give conclusions in Section 6.


## 2. StochasticP(P0)-Function

It is well known that theP-function, P0-function, and uniformly P-function play an important role in the nonlinear complementarity problems theory [1]. We will introduce a new concept of stochastic P-function, P0-function, and uniformly P-function, which can be regarded as a generalization of their deterministic form or stochastic P matrix and stochastic P0 matrix.Definition 1 (see [14]).
M
(
·
) is called a stochastic P(P0)-matrix if there exists i∈J(x) such that, for every x≠0 in Rn,
(12)𝒫{ω:xi(M(ω)x)i>0(≥0)}>0.Definition 2.
A functionF:Rn×Ω→Rn is a stochastic P(P0)-function if there exist i∈J(x,y), i∈〈1,n〉 such that, for every x≠y in Rn,
(13)xi≠yi,𝒫{ω:(xi-yi)(Fi(x,ω)-Fi(y,ω))>0(≥0)}>0.Definition 3.
A functionF:Rn×Ω→Rn is a stochastic uniformly P-function if there exists a positive constant α and i∈J(x,y), i∈〈1,n〉 such that, for every x≠y in Rn,
(14)𝒫{ω:(xi-yi)(Fi(x,ω)-Fi(y,ω))≥α∥x-y∥2}>0.Clearly, every stochastic uniformlyP-function must be a stochastic P-function, which in turn must be a stochastic P0-function. We further cite the definition of “equicoercive" in [11]. More information about this definition can be found in [11].Definition 4 (see [11]).
We say thatF:Rn×Ω→Rn is equicoercive on 𝒟⊆Rn, if, for any {xk}⊆𝒟 satisfying ∥xk∥→∞, the existence of {ωk}⊆suppΩ with limk→∞Fi(xk,ωk)=∞(limk→∞(-Fi(xk,ωk))+=∞) for some i∈〈1,n〉 implies that
(15)𝒫{ω:limk→∞Fi(xk,ω)=∞}>0(𝒫{ω:limk→∞(-Fi(xk,ω))+=∞}>0),
where
(16)suppΩ∶={ω-∈Ω:∫Bω(ω-,ν)∩Ω‍dF(ω)>0foranyν>0}
and Bω(ω-,ν):={ω:∥ω-ω-∥<ν} and F(ω) is the distribution function of ω.More details aboutsuppΩ were included in [8].Proposition 5.
IfF is a stochastic P0-function, then F+εx is a stochastic P-function for every ε>0.Proof.
From the definition of stochasticP0-function, there exist i∈J(x,y), i∈〈1,n〉 such that, for every x≠y,
(17)xi≠yi,𝒫{ω:(xi-yi)(Fi(x,ω)-Fi(y,ω))≥0}>0.
Hence, we have
(18)𝒫{ω:(xi-yi)(Fi(x,ω)+εxi-(Fi(y,ω)+εyi))>0}=𝒫{ω:(xi-yi)(Fi(x,ω)-Fi(y,ω))+ε(xi-yi)2>0}≥𝒫{ω:(xi-yi)(Fi(x,ω)-Fi(y,ω))≥0}>0.This proposition gives the relationship between stochasticP0-function and stochastic P-function.Proposition 6.
LetF be an affine function of x for any ω∈Ω defined by (2). Then F is a stochastic P(P0)-function if and only if M(·) is a stochastic P(P0) matrix.Proof.
By the definition of stochasticP(P0)-function, we have that there exist i∈J(x,y), i∈〈1,n〉 such that, for every x≠y,
(19)xi≠yi,𝒫{ω:(xi-yi)(Fi(x,ω)-Fi(y,ω))>0(≥0)}>0,
which is equivalent to
(20)xi≠yi,𝒫{ω:(xi-yi)(M(ω)(x-y))i>0(≥0)}>0,
when F is defined by (2). Set z=x-y; then z≠0, and we have that formulation (20) holds if and only if there exists i∈J(z) such that, for every z≠0,
(21)𝒫{ω:zi(M(ω)z)i>0(≥0)}>0.
Hence, M(·) is a stochastic P(P0) matrix.Proposition 7.
F is a stochastic P(P0)-function if and only if there exists a ω-∈suppΩ such that F(·,ω-) is a P(P0)-function.Proof.
For the “if” part, suppose on the contrary thatF is not a stochastic P(P0)-function, and then there exist x~,y~,x~≠y~ in Rn for any i∈〈1,n〉 satisfying
(22)x~i≠y~i,𝒫{ω:(x~i-y~i)(Fi(x~,ω)-Fi(y~,ω))>0(≥0)}=0.
On the other hand, sinceF(·,ω-) is a P(P0)-function, then for x~,y~ there exist i∈J(x~,y~), i∈〈1,n〉 such that
(23)(x~i-y~i)(Fi(x~,ω-)-Fi(y~,ω-))>0(≥0).
Notice that ω-∈suppΩ, by the definition of suppΩ in (16), we have
(24)𝒫{ω-:(x~i-y~i)(Fi(x~,ω-)-Fi(y~,ω-))>0(≥0)}>0.
This contradicts formulation (22). Therefore, F is a stochastic P(P0)-function.
Now for the “only if” part, suppose on the contrary that there does not exist aω-∈suppΩ such that F(·,ω-) is a P(P0)-function. Then for any i∈〈1,n〉, ω∈suppΩ, there exists x-,y-,x-≠y- in Rn, such that
(25)x-i≠y-i,(x-i-y-i)(Fi(x-,ω)-Fi(y-,ω))≤0(<0),
which means that
(26)x-i≠y-i,𝒫{ω∈suppΩ:(x-i-y-i)(Fi(x-,ω)-Fi(y-,ω))>0(≥0)(y-,ω)}=0.
By the definition of suppΩ in (16), we have 𝒫{ω∈Ω∖suppΩ}=0. Hence, formulation (26) is equivalent to
(27)x-i≠y-i,𝒫{ω∈Ω:(x-i-y-i)(Fi(x-,ω)-Fi(y-,ω))>0(≥0)}=0,
which contradicts definition (20). Therefore, there exists a ω-∈suppΩ such that F(·,ω-) is a P(P0)-function.Theorem 8.
Suppose thatf(x):=E[F(x,ω)] is a P(P0)-function. Then F is a stochastic P(P0)-function.Proof.
Suppose on the contrary thatF is not a stochastic P(P0)-function, then there exist x~,y~,x~≠y~ in Rn for any i∈〈1,n〉 satisfying
(28)x~i≠y~i,𝒫{ω:(x~i-y~i)(Fi(x~,ω)-Fi(y~,ω))>0(≥0)}=0.
This means that
(29)(x~i-y~i)(Fi(x~,ω)-Fi(y~,ω))≤0(<0)
always holds for any i∈〈1,n〉 and ω∈Ω. Furthermore, following from (29), we have
(30)E[(x~i-y~i)(Fi(x~,ω)-Fi(y~,ω))]≤0(<0),
that is
(31)(x~i-y~i)(fi(x~)-fi(y~))≤0(<0),
which contradicts the definition of P(P0)-function. Therefore, F is a stochastic P(P0)-function.Note that there is at most one solution (may not be a solution) for the EV model stochastic complementarity problems iff(x):=E[F(x,ω)] is a P(P0)-function.


## 3. Boundedness of Solution Set

Theorem 9.
Suppose thatF is a stochastic uniformly P-function and F is equicoercive on Rn. Then the solution set of ERM model (7) defined by ϕmin and ϕFB is nonempty and bounded.Proof.
Suppose on the contrary that the ERM model defined byϕmin is not bounded. Thus there exist a sequence {xk}⊂R+n with ∥xk∥→∞(k→∞) and a constant c∈R+, such that
(32)θ(xk)≤c,for∀k.
Define the index set I⊆{1,…,n} by
(33)I:={i∣{xik}isunbounded}.
By assumption, we have I≠∅. We now define a sequence {yk}⊆Rn as follows:
(34)yik:={0ifi∈I,xikifi∉I.
From the definition of yk and the fact that F is a stochastic uniformly P-function, we obtain that for any xk,yk, there exists i such that
(35)𝒫{∥xk-yk∥2ω:(xik-yik)(Fi(xk,ω)-Fi(yk,ω))≥α∥xk-yk∥2}>0,
and hence there are ω-k∈suppΩ satisfying
(36)(xik-yik)(Fi(xk,ω-k)-Fi(yk,ω-k))≥α∥xk-yk∥2.
Take subsequence xki,yki such that the corresponding subscript of (36) is j. Noting that j∈I and taking (36) into account, we have
(37)α∑j∈I‍(xjki)2≤xjki(Fj(xki,ω-ki)-Fj(yki,ω-ki))≤∑j∈I‍(xjki)2·∑j∈I‍|Fj(xki,ω-ki)-Fj(yki,ω-ki)|,
from which we get
(38)α∑j∈I‍(xjki)2≤∑j∈I‍|Fj(xki,ω-ki)-Fj(yki,ω-ki)|.
By definition, the sequence {yki} remains bounded. From the continuity of F, it follows that the sequence {Fj(yki,ωki)} is also bounded for every j∈I. Hence, taking a limit in (38), we obtain that there is at least one index j-∈I such that
(39)xj-ki⟶∞,Fj-(xki,ω-ki)⟶∞.
Since F is equicoercive on Rn, we have
(40)𝒫{ω:limki→∞Fj-(xki,ω)=∞}>0.
Let
(41)Ω1={ω:limki→∞min(xj-ki,Fj-(xki,ω))=∞}.
Then 𝒫{Ω1}>0. By Fatou’s Lemma [15], we have
(42)EΩ1[liminfki→∞(min(xj-ki,Fj-(xki,ω)))2]≤liminfki→∞EΩ1[(min(xj-ki,Fj-(xki,ω)))2].
Since
(43)liminfki→∞(min(xj-ki,Fj-(xki,ω)))2=∞
on Ω1 and 𝒫{Ω1}>0, then the left-hand side of formulation (42) is infinite. Therefore,
(44)liminfki→∞EΩ1[(min(xj-ki,Fj-(xki,ω)))2]=∞.
Moreover, it is easy to find
(45)θ(xki)=E[∥Φ(xki,F(xki,ω))∥2]≥EΩ1[(min(xj-ki,Fj-(xki,ω)))2]⟶∞
as ki→∞. This contradicts formulation (32). Hence, the solution set of ERM model (7) defined by ϕmin is nonempty and bounded. Similar results about ϕFB can be obtained by relation formulation (10).


## 4. Robust Solution

As we show, both EV model and ERM model give decisions by a deterministic formulation. However, the decisions may not be the best or may be even infeasible for each individual event. In fact, we should take risk into account to make a priori decision in many cases. Naturally, it is necessary to know how good or how bad the decision which we have given can be. In this section, we study the robustness of solutions of the ERM model. LetSOL(F(x,ω)) denote the solution set of SCP(F(x,ω)), and define the distance from a point x to the set SOL(F(x,ω)) by
(46)dist(x,SOL(F(x,ω))):=infx′∈SOL(F(x,ω))∥x-x′∥.Theorem 10.
Assume thatΩ={ω1,ω2,…,ωN}⊂Rm, and ω takes values ω1,…,ωN with respective probabilities p1,…,pN. Furthermore, suppose that for every ω∈Ω, F(x,ω) is uniformly P-function and Lipschitz continuous with respect to x. Then there is a constant C>0 such that
(47)E[dist(x,SOL(F(x,ω)))]≤C·θ(x),
where θ(x) is defined by ϕmin or ϕFB.Proof.
For any fixedωi, since F(x,ωi) is uniformly P-function and Lipschitz continuous, from Corollary 3.19 of [16], we have unique solution x^(ωi) of CP(F(x,ωi)), and there exists a constant Ci such that
(48)∥x-x^(ωi)∥≤Ci∥min{x,F(x,ωi)}∥.
Letting C:=((2+2)/2)max{C1,…,CN}, we have
(49)E2[dist(x,SOL(F(x,ω)))]=E2[∥x-x^(ωi)∥]≤E[∥x-x^(ωi)∥2]≤∑i=1N‍pi·Ci2∥min{x,F(x,ωi)}∥2≤∑i=1N‍pi·Ci2·(2+22)2×∑j=1n‍(Fj2(x,ωi)+xj2-(Fj(x,ωi)+xj))2≤C2∑i=1N‍pi∑j=1n‍(Fj2(x,ωi)+xj2-(Fj(x,ωi)+xj))2=C2θ(x),
where the first inequality follows from Cauchy-Schwarz inequality, the second inequality follows from formulation (48), and the third inequality follows from formulation (10). This completes the proof of the theorem.Theorem10 particularly shows that for the solution x* of (7),
(50)E[dist(x*,SOL(F(x,ω)))]≤C·θ(x*).
This inequality indicates that the expected distance to the solution set SOL(F(x,ω)) for ω∈Ω is also likely to be small at the solution x* of (7). In other words, we may expect that a solution of the ERM formulation (7) has a minimum sensitivity with respect to random parameter variations in SCP(F(x,ω)). In this sense, solutions of (7) can be regarded as robust solutions for SCP(F(x,ω)).


## 5. Quasi-Monte Carlo and Derivative-Free Methods for Solving ERM Model

Note that the ERM model (7) included an expectation function, which is generally difficult to be evaluated exactly. Hence in this section, we first employ a quasi-Monte Carlo method to obtain approximation problems of (7) for numerical integration. Then, we consider derivative-free methods to solve these approximation problems.By the quasi-Monte Carlo method, we obtain the following approximation problem of (7):
(51)minx∈R+nθN(x):=1N∑ωi∈ΩN∥Φ(x,ωi)∥2ρ(ωi),
where ΩN={ωi∣i=1,2,…,N} is a set of observations generated by a quasi-Monte Carlo method such that ΩN⊆Ω and ρ(ω) stands for the probability density function. In the rest of this paper, we assume that the probability density function ρ is continuous on Ω. For each N, θN(x) is continuously differentiable function. We denote by xN the optimal solutions of approximation problems (51). We are interested in the situation where the first-order derivatives of θN(x) cannot be explicitly calculated or approximated.Condition 1.
Given a pointx0≥0, the level set
(52)L:={x≥0∣f(x)≤f(x0)}
is compact.Condition 2.
If{xkN} and {ykN} are sequences of points such that xkN≥0,  ykN≥0 converging to some x-N and IkN⊆I(x-N):={i∣x-iN=0} for all k, then
(53){dist(TIkN(xkN),TIkN(ykN))}⟶0,
where dist(T1,T2)=maxd1∈T1:∥d1∥=1{mind2∈T2∥d1-d2∥} and TIkN(x):={dkN∈Rn∣dk,iN≥0,∀i∈IkN}.Condition 3.
For everyx-N≥0 there exist scalars δ>0, and η>0 such that
(54)minz≥0∥z-x∥≤η∑i=1n‍max(-xi,0),∀x∈{x∈Rn∣∥x-x-∥≤δ}.Condition 4.
GivenxkN and ϵkN>0, the set of search directions
(55)DkN={dkN,j,j=1,…,rkN},with∥dkN,j∥=1,
satisfing rkN is uniformly bounded and cone{DkN}=T(xkN;ϵkN). Here,
(56)cone{DkN}={dkN,1β1+⋯+dkN,rkNβrkN:β1≥0,…,βrkN≥0},T(xkN;ϵkN)={dkN∈Rn∣dk,iN≥0,xk,iN≤ϵkN}.Under Conditions1, 2, and 3 and by choosing DkN satisfying Condition 4 with ϵkN→0, then the following generated iterates have at least one cluster point that is a stationary point of (51) for each N.Algorithm 11.
Parameters:x0N≥0, α~0N>0, γN>0, θ1N∈(0,1), θ2N∈(0,1), ϵ0N>0.
Step
1. Set kN=0.
Step
2. Choose a set of directions DkN={dkN,j,j=1,…,rkN} satisfying Condition 4.
Step
3.
(a)
Setj=1, ykN,j=xkN, α~kN,j=α~kN.
(b)
Compute the maximum stepsizeα-kN,j such that yi,kN,j+α-kN,jd^i,kN,j≥0 for all i. Set α^kN,j=min{α-kN,j,α~kN,j}.
(c)
Ifα^kN,j>0 and θN(y^kN,j)≤θN(ykN,j)-γ(α^kN,j)2, set α~kN,j+1=αkN,j; otherwise set αkN,j=0,ykN,j+1=ykN,j,α~kN,j+1=θ1Nα~kN,j.
(d)
IfαkN,j=α-kN,j, set ϵk+1N=ϵkN, and go to Step 4.
(e)
Ifj<rkN, set j=j+1, and go to Step 3(b). Otherwise set ϵk+1N=θ2NϵkN and go to Step 4.
Step
4. Find xk+1N≥0 such that θN(xk+1N)≤θN(ykN,j+1). Set α~k+1N=α~kN,j+1,r~k=j,k=k+1, and go to Step 2.For this algorithm, it is easy to proof that ifxkN is the sequence produced by algorithm under Conditions 1–4, then xkN is bounded and there exists at least one cluster point which is a stationary point of problem (51) for each N.


## 6.  Conclusions

The SCP(F(x,ω)) has a wide range of applications in engineering and economics. Therefore, it is meaningful and interesting to study this problem. In this paper, we give the definitions of stochastic P-function, stochastic P0-function and stochastic uniformly P-function, which can be regarded as a generalization of the deterministic formulation or an extension of a stochastic R0 function given in [11]. Moreover, we consider the conditions when the function is a stochastic P(P0)-function. Furthermore, we show that the involved function being a stochastic uniformly P-function and equi-coercive  [11] are sufficient conditions for the solution set of the expected residual minimization problem to be nonempty and bounded. Finally, we illustrate that the ERM formulation produces robust solutions with minimum sensitivity in violation of feasibility with respect to random parameter variations in SCP(F(x,ω)). On the other hand, we employ a quasi-Monte Carlo method to obtain approximation problems of (7) for dealing numerical integration and further consider derivative-free methods to solve these approximation problems.



---

*Source: 497586-2013-05-28.xml*