# The Distributionally Robust Optimization Reformulation for Stochastic Complementarity Problems

Authors: Liyan Xu; Bo Yu; Wei Liu
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We investigate the stochastic linear complementarity problem affinely
affected by the uncertain parameters. Assuming that we have only limited
information about the uncertain parameters, such as the first two moments or the first two moments as well as the support of the distribution, we formulate the stochastic linear complementarity
problem as a distributionally robust optimization reformation which minimizes
the worst case of an expected complementarity measure with nonnegativity
constraints and a distributionally robust joint chance constraint representing
that the probability of the linear mapping being nonnegative is not less than
a given probability level. Applying the cone dual theory and S-procedure, we
show that the distributionally robust counterpart of the uncertain complementarity
problem can be conservatively approximated by the optimization with
bilinear matrix inequalities. Preliminary numerical results show that a solution
of our method is desirable.


---

## Body

## 1. Introduction

The stochastic complementarity problem (SCP) is to find a vectorx
∈
R
n such that
(1)
x
≥
0
,
F
x
,
ξ
≥
0
,
x
T
F
x
,
ξ
=
0
,
∀
ξ
∈
Ξ
,
where F
:
R
n
×
Ξ
→
R
n is a vector valued function affected by the uncertain data ξ
∈
Ξ and the uncertainty set (or support set when viewing ξ as a random vector) Ξ
⊂
R
k. If Ξ is a singleton, then the problem (1) becomes the deterministic complementarity problem, which has been well studied during the past two decades, due to its wide range of practical applications in engineering and economic science, control theory, operations research, and game theory [1–4].In the stochastic programming approach, the uncertain data are assumed to be random, and the random dataξ are assumed to obey a known in advance probability distribution for the simplest case or more generally the expected value of F
(
x
,
ξ
) can be evaluated by the corresponding function of the sample of the random data ξ. In this way, people seek some deterministic and approximate reformulations of the SCP (1). Among the literature of the SCP, there are some typical deterministic reformulations, such as, the expected value method, the expected residual minimization method, stochastic mathematical program with equilibrium constraints reformulation, and the CVaR minimization reformulation (see [5–8] for details). Because the sample average approximation method is utilized to solve the deterministic reformulations of the SCP, the reformulations of the SCP are depended on the sample of the random data ξ which itself has the property of the randomness or uncertainty. In the robust optimization approach, uncertain data ξ is assumed to be in some convex tractable sets which are called the uncertainty. In order to establish reformulation immunizing against the data uncertainty, [9] reformulates the SCP as a system of robust inequalities, namely, ρ-approximation, as a relaxation of the robust counterpart of the SCP.Contrary to the approaches of the stochastic programming and the classical robust optimization, the distributionally robust optimization (see [10–13] for reference), which aims to find the best solution of the worst-case of a problem with uncertain data whose distribution is assumed to be in a family of probability distributions, captures the decision makers a moderate risk attitude (through the consideration of the partial information about the distribution of the uncertain data but not the exact ranges of the uncertain data) and an aversion towards uncertainty (through the consideration of the worst probability distribution within a known family of distributions with partial information). It has been argued that most decision makers have low tolerance towards uncertainty in the distribution [14, 15]. It is rational to take decisions in view of the worst probability distribution that is deemed possible under the existing information and to obtain an out-of-sample model. In this paper, viewing the uncertain data ξ as a random vector and assuming that only partial information about the distribution of ξ is known, we use the distributionally robust optimization approach to reformulate the SCP (1) as the distributionally robust optimization reformulation (DROR):
(2)
min
⁡
sup
⁡
P
∈
P
E
P
[
x
∘
F
(
x
,
ξ
)
2
]
s
.
t
.
inf
⁡
P
∈
P
P
F
x
,
ξ
≥
0
≥
1
-
ϵ
,
v
v
v
v
v
v
x
≥
0
,
where x
∘
F
(
x
,
ξ
)
2 is a measure of the complementarity in terms of the 2-norm and the risk factor ϵ
∈
(
0,1
). The distribution P is assumed to belong to a family P of possible distributions. We consider two cases of information about P, the necessary information given first two moments, that is, P
=
{
P
∈
M
+
:
P
(
ξ
∈
Ξ
)
=
1, E
P
[
ξ
]
=
μ
0, and E
P
[
ξ
ξ
T
]
=
Σ
0
+
μ
0
μ
0
T
,
Σ
0
≻
0
} with M
+ being the cone of nonnegative Borel measures on R
k and Ξ
=
R
k and the additional information about support set Ξ, which is assumed as one of the following convex sets: the box set, the polyhedral set, ∩-ellipsoidal set, or the intersection of these sets mentioned above:
(3)
Ξ
1
=
{
ξ
:
l
b
≤
ξ
≤
u
b
,
l
b
,
u
b
∈
R
k
,
l
b
≤
u
b
}
Ξ
2
=
{
ξ
:
C
p
ξ
≤
d
p
,
C
p
∈
R
(
k
+
1
)
×
k
,
d
p
∈
R
k
+
1
}
Ξ
3
=
{
ξ
:
S
j
1
/
2
(
ξ
-
μ
j
)
2
≤
1
,
S
j
⪰
0
,
μ
j
∈
R
k
,
j
=
1
,
…
,
l
}
Ξ
4
=
Ξ
1
⋂
‍
Ξ
2
⋂
‍
Ξ
3
.
In rest of the paper, we assume that F
i
(
x
,
ξ
) relies affinely on x; that is,
(4)
F
i
(
x
,
ξ
)
=
∑
j
=
1
n
‍
m
~
i
j
ξ
T
x
j
+
q
~
i
(
ξ
)
,
and that the coefficients m
~
i
j
(
ξ
) and q
~
i
(
ξ
) are affinely affected by the random parameters ξ; that is,(5)
m
~
i
j
(
ξ
)
=
m
i
j
0
+
∑
l
=
1
k
‍
m
i
j
l
ξ
l
,
q
~
i
(
ξ
)
=
q
i
0
+
∑
l
=
1
k
‍
q
i
l
ξ
l
,
where m
i
j
0
,
m
i
j
l
,
q
i
0
,
q
i
l
,
∈
R are scalars.The motivation of this reformulation comes from the idea that all reformulations for the SCP endeavor to make a trade-off between the feasibility and complementarity when both sides cannot be satisfied simultaneously. We minimize the worst case of the complementarity measure with imposing the worst case joint chance constraint, which describes that the complementarity is satisfied with a given probability not less than1
-
ϵ. It is worth mentioning that the DROR (2) contains two semi-infinite programs in the variable of the probability measure P. So, the major difficulty to solve (2) lies in how to transform it into a tractable problem. By investigating the dual of the inner problem in the objective and the structure of the feasible set of the worst case joint chance constraint, we will illustrate that the DROR can be conservatively approximated as the optimization with bilinear matrix inequalities (BMIs).The rest of the paper is organized as follows. In Sections2 and 3, we study the conservative approximations of the DROR without and with the information of the support, respectively. Numerical results on a simple stochastic complementarity problem using the DROR are reported in Section 4.Notation. Denote the covariance matrix C
=
Σ
0
+
μ
0
μ
0
T
μ
0
μ
0
T
1, and rewrite F
i
(
x
,
ξ
)
=
(
ξ
T
1
)
A
i
(
x
)
ξ
1, where A
i
(
x
)
:
=
0
k
×
k
(
1
/
2
)
a
~
i
(
x
)
(
1
/
2
)
a
~
i
T
(
x
)
a
~
i
0
(
x
) is affine in x with
(6)
a
~
i
0
x
=
∑
j
=
1
n
‍
m
i
j
0
x
j
+
q
i
0
∈
R
,
a
~
i
(
x
)
=
∑
j
=
1
n
‍
x
j
m
i
j
1
⋯
m
i
j
k
T
+
q
i
1
⋯
q
i
k
T
∈
R
k
.
Let Π
m
(
u
) denote the linear mapping of u determined by the support Ξ
m
(
m
=
1,2
,
3,4
):
(7)
Π
1
(
u
)
:
=
0
1
2
(
u
¯
-
u
_
)
1
2
u
¯
-
u
_
T
u
_
T
l
b
-
u
¯
T
u
b
,
Π
2
(
u
)
:
=
0
1
2
C
p
T
u
1
2
u
T
C
p
-
u
T
d
p
,
Π
3
(
u
)
:
=
∑
j
=
1
l
‍
u
j
S
j
-
1
S
j
-
1
μ
j
S
j
-
1
μ
j
T
μ
j
T
S
j
-
1
μ
j
-
1
,
Π
4
(
u
)
:
=
∑
m
=
1
3
‍
Π
m
(
u
m
)
,
with u
=
(
u
_
,
u
¯
)
∈
R
2
k, u
∈
R
k
+
1, u
∈
R
l, and u
=
(
u
1
,
u
2
,
u
3
)
∈
R
3
k
+
1
+
l, respectively.


## 2. The Conservative Approximation for the DROR without the Support Information

In this section, we assume that we have no information about the support. Noticing that the objective function and the constraints contain two semi-infinite programs with variableP, we first reformulate the inner moment problem in its dual form and then use the fact that min-min operations can be performed jointly to approximate the DROR (2) as the optimization with BMIs.First of all, we investigate these semi-infinite programs for every fixed decision variablex by the cone dual theory and the S-procedure. We show that DROR can be approximated conservatively by optimization with BMIs. First, we recall the S-procedure, which is the generalization of the well-known S-lemma [16], which plays a crucial role in the proof of the following the paper.Lemma 1 (S-procedure).
LetF
i
(
x
)
=
x
T
A
i
x
+
2
b
i
T
x
+
c
i, i
=
0,1
,
…
,
p be quadratic functions of x
∈
R
n. Then
(8)
F
i
(
x
)
≥
0
,
i
=
1
,
…
,
p
⟹
F
0
(
x
)
≥
0
if there exist λ
i
≥
0 such that
(9)
A
0
b
0
b
0
T
c
0
-
∑
i
=
1
p
‍
λ
i
A
i
b
i
b
i
T
c
i
⪰
0
.
If p
=
1, converse also holds as long as ∃
x
0
s
.
t
.
F
1
(
x
0
)
>
0.Another useful lemma is a result derived by the cone duality theory (see [17]).Lemma 2.
Letϕ
(
x
,
ξ
) be the nonlinear mapping in x and ξ. Then for each fixed x
∈
R
n, sup
⁡
P
∈
P
E
P
[
ϕ
(
x
,
ξ
)
] is equivalent to the following semi-infinite programming:
(10)
min
⁡
C
·
Y
s
.
t
.
ξ
T
1
Y
ξ
T
1
T
≥
ϕ
x
,
ξ
,
∀
ξ
∈
Ξ
,
Y
∈
S
k
+
1
,
where C
·
Y represents the trace of the matrix C
Y.Remark 3.
We mention that the problemsup
⁡
P
∈
P
E
P
[
ϕ
(
x
,
ξ
)
] is a moment problem and the strong duality condition holds due to Σ
0
≻
0 in Lemma 2. See Lemma  1 in [12] and also Lemma A.1 in [13] for similar results.


### 2.1. The Equivalent Expression of the Worst Case of the Objective

Now we study the inner problem(11)
sup
⁡
P
∈
P
E
P
[
x
∘
F
(
x
,
ξ
)
2
]
in the objective of the DROR without the support information.Lemma 4.
Suppose thatF
i
(
x
,
ξ
) is affine in x and is affinely affected by ξ which is supported on Ξ
=
R
k. Then, for each fixed x
∈
R
n, the problem (11) is equivalent to an optimization with a linear matrix inequality:
(12)
inf
⁡
C
·
Y
v
s
.
t
.
Y
v
a
1
(
x
)
⋯
a
n
(
x
)
a
1
T
(
x
)
1
⋮
⋱
a
n
T
(
x
)
1
⪰
0
,
Y
v
∈
S
k
+
1
,
where a
i
(
x
)
:
=
(
x
i
a
~
i
T
(
x
)
x
i
a
~
i
0
(
x
)
)
T
(
i
=
1
,
…
,
n
) is quadratic in x.Proof.
Due toΣ
0
≻
0 and Lemma 2, the problem (11) is equivalent to its dual problem:
(13)
inf
⁡
Y
v
C
·
Y
v
s
.
t
.
ξ
T
1
Y
v
ξ
T
1
T
≥
x
∘
F
(
x
,
ξ
)
2
,
∀
ξ
∈
Ξ
,
Y
v
∈
S
k
+
1
.
Notice that F
i
(
x
,
ξ
)
=
a
~
i
T
(
x
)
ξ
+
a
~
i
0
(
x
); then, the semi-infinite inequality constraint above can be equivalently written as
(14)
ξ
T
1
Y
v
ξ
T
1
T
≥
∑
i
=
1
n
‍
x
i
(
a
~
i
T
(
x
)
ξ
+
a
~
i
0
(
x
)
)
2
,
∀
ξ
∈
Ξ
,
which can be also written as
(15)
Y
v
-
∑
i
=
1
n
‍
a
i
(
x
)
a
i
T
(
x
)
⪰
0
.
Then using the Schur Complement lemma, we can show that it is equivalent to the constraint in the problem (12), which completes the proof.


### 2.2.  The Conservative Approximation of the Distributionally Robust Joint Chance Constraint

DenoteX
c
=
x
∈
R
n
:
inf
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
≥
0
]
≥
1
-
ϵ as the feasible set of the chance constraint in (2). Now we describe the structure of X
c by a conservative approximation when we have no information about the support Ξ. Since the chance constraint in (2) is a distributionally robust joint chance constraint, it is difficult to describe the structure of its feasible set X
c exactly. We establish a conservative approximation in terms of a system of BMIs for the distributionally robust joint chance constraint when F
i
(
x
,
ξ
) is affinely depended on ξ. To this end, we introduce a set X
0
c:
(16)
X
0
c
=
x
∈
R
n
:
inf
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
>
0
]
≥
1
-
ϵ
.
Employing Lemmas 1 and 2, we show that the structure of X
0
c can be equivalently described by a system of BMIs, as stated as Lemma 5.Lemma 5.
Suppose thatF
i
(
x
,
ξ
) is affine in x and is affinely affected by ξ which is supported on Ξ
=
R
k, and suppose that there exists some ξ with F
i
(
x
,
ξ
)
<
0
(
i
=
1
,
…
,
n
) for each fixed x. Then X
0
c
⊆
X
c and X
0
c can be equivalently expressed as a system of BMIs:
(17)
X
0
c
=
x
∈
R
n
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
s
u
c
h
t
h
a
t
x
C
·
Y
c
≤
ϵ
,
z
>
0
,
Y
c
⪰
0
,
Y
c
∈
S
k
+
1
,
z
∈
R
n
Y
c
+
z
i
A
i
x
-
C
0
⪰
0
,
i
=
1
,
…
,
n
x
∈
R
n
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
s
u
c
h
t
h
a
t
x
,
with the constant matrix C
0
=
0
k
×
k
0
k
×
1
0
1
×
k
1.Proof.
Since(18)
inf
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
≥
0
]
≥
1
-
ϵ
⟺
sup
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
<
0
]
≤
ϵ
,
it is clear that X
0
c
⊆
X
c. So it suffices to show that X
0
c can be expressed as (17) equivalently. x
∈
X
0
c implies that sup
⁡
P
∈
P
P
[
min
⁡
1
≤
i
≤
n
F
i
(
x
,
ξ
)
≤
0
]
≤
ϵ, which can be reexpressed as
(19)
sup
⁡
P
P
∈
P
E
[
1
{
min
⁡
1
≤
i
≤
n
F
i
(
x
,
ξ
)
≤
0
}
]
≤
ϵ
.
Then using Lemma 2, we can show that x
∈
X
0
c means that x satisfies
(20)
ϵ
≥
inf
⁡
C
·
Y
c
s.t.
ξ
T
1
Y
c
ξ
1
≥
1
{
min
⁡
i
F
i
(
x
,
ξ
)
≤
0
}
,
∀
ξ
∈
Ξ
,
Y
c
∈
S
k
+
1
.
Note that the semi-infinite constraint above is equivalent to
(21)
ξ
T
1
Y
c
ξ
1
≥
0
,
∀
ξ
∈
Ξ
,
(22)
ξ
T
1
Y
c
ξ
1
≥
1
,
∀
ξ
∈
{
ξ
:
min
⁡
i
F
i
(
x
,
ξ
)
≤
0
}
⋂
‍
Ξ
.
The constraint (22) can be expressed as
(23)
ξ
T
1
Y
c
ξ
1
≥
1
,
∀
ξ
∈
{
ξ
:
F
i
(
x
,
ξ
)
≤
0
}
⋂
‍
Ξ
,
∀
i
=
1
,
…
,
n
.
Since Ξ
=
R
k, the above implications can be reexpressed as the following implications:
(24)
ξ
T
1
A
i
(
x
)
ξ
1
≤
0
⟹
ξ
T
1
Y
c
ξ
1
≥
1
,
∀
i
=
1
,
…
,
n
.
Notice that A
i
(
x
) is affine in x and Y
c
⪰
0 by (21); then, by Lemma 1 and the assumptions of this lemma, we have that the implications above are equivalent to
(25)
∃
z
∈
R
n
,
such
that
z
i
≥
0
,
Y
c
+
z
i
A
i
x
-
C
0
⪰
0
,
i
=
1
,
…
,
n
.
So, we have
(26)
X
0
c
=
x
∈
R
k
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
such
that
C
·
Y
c
≤
ϵ
,
z
≥
0
,
Y
c
⪰
0
,
R
k
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
Y
c
+
z
i
A
i
x
-
C
0
⪰
0
,
i
=
1
,
…
,
n
x
∈
R
k
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
such
that
.
To complete the proof, it is sufficient to show that z
=
0 is impossible in (26). Otherwise, if there exists some z
i
=
0 in (25), by taking trace operator to the both sides of the BMIs above multiplied by C, we obtain C
·
Y
c
≥
1, which contradicts C
·
Y
c
≤
ϵ.


### 2.3.  The Conservative Approximation for the DROR

According to Lemma4, the DROR (2) can be expressed equivalently as
(27)
min
⁡
C
·
Y
v
s
.
t
.
Y
v
a
1
(
x
)
⋯
a
n
(
x
)
a
1
T
(
x
)
1
⋮
⋱
a
n
T
(
x
)
1
⪰
0
,
x
≥
0
,
x
∈
X
c
,
Y
v
∈
S
k
+
1
.
Notice that the set X
0
c is inside the feasible set X
c as stated in Lemma 5. So by replacing X
c by X
0
c in the problem above, we can obtain a problem with an optimal value not less than that of (2). Thus, putting Lemmas 4 and 5 together, we obtain conservative approximation of the DROR (2) in terms of the optimization with BMIs, as stated in Theorem 6.Theorem 6.
Suppose thatF
i
(
x
,
ξ
) is affine in x and is also affine with respect to ξ which is supported on Ξ
=
R
k, and suppose that there exists some ξ with F
i
(
x
,
ξ
)
<
0
(
i
=
1
,
…
,
n
) for each fixed x. Then the DROR (2) can be conservatively expressed as
(28)
min
⁡
C
·
Y
v
s
.
t
.
x
≥
0
,
z
>
0
,
C
·
Y
c
≤
ϵ
,
Y
c
⪰
0
,
Y
c
+
z
i
A
i
(
x
)
-
C
0
⪰
0
,
i
=
1
,
…
,
n
,
Y
v
a
1
(
x
)
⋯
a
n
(
x
)
a
1
T
(
x
)
1
⋮
⋱
a
n
T
(
x
)
1
⪰
0
,
x
∈
R
n
,
z
∈
R
n
,
Y
c
∈
S
k
+
1
,
Y
v
∈
S
k
+
1
.


## 2.1. The Equivalent Expression of the Worst Case of the Objective

Now we study the inner problem(11)
sup
⁡
P
∈
P
E
P
[
x
∘
F
(
x
,
ξ
)
2
]
in the objective of the DROR without the support information.Lemma 4.
Suppose thatF
i
(
x
,
ξ
) is affine in x and is affinely affected by ξ which is supported on Ξ
=
R
k. Then, for each fixed x
∈
R
n, the problem (11) is equivalent to an optimization with a linear matrix inequality:
(12)
inf
⁡
C
·
Y
v
s
.
t
.
Y
v
a
1
(
x
)
⋯
a
n
(
x
)
a
1
T
(
x
)
1
⋮
⋱
a
n
T
(
x
)
1
⪰
0
,
Y
v
∈
S
k
+
1
,
where a
i
(
x
)
:
=
(
x
i
a
~
i
T
(
x
)
x
i
a
~
i
0
(
x
)
)
T
(
i
=
1
,
…
,
n
) is quadratic in x.Proof.
Due toΣ
0
≻
0 and Lemma 2, the problem (11) is equivalent to its dual problem:
(13)
inf
⁡
Y
v
C
·
Y
v
s
.
t
.
ξ
T
1
Y
v
ξ
T
1
T
≥
x
∘
F
(
x
,
ξ
)
2
,
∀
ξ
∈
Ξ
,
Y
v
∈
S
k
+
1
.
Notice that F
i
(
x
,
ξ
)
=
a
~
i
T
(
x
)
ξ
+
a
~
i
0
(
x
); then, the semi-infinite inequality constraint above can be equivalently written as
(14)
ξ
T
1
Y
v
ξ
T
1
T
≥
∑
i
=
1
n
‍
x
i
(
a
~
i
T
(
x
)
ξ
+
a
~
i
0
(
x
)
)
2
,
∀
ξ
∈
Ξ
,
which can be also written as
(15)
Y
v
-
∑
i
=
1
n
‍
a
i
(
x
)
a
i
T
(
x
)
⪰
0
.
Then using the Schur Complement lemma, we can show that it is equivalent to the constraint in the problem (12), which completes the proof.


## 2.2.  The Conservative Approximation of the Distributionally Robust Joint Chance Constraint

DenoteX
c
=
x
∈
R
n
:
inf
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
≥
0
]
≥
1
-
ϵ as the feasible set of the chance constraint in (2). Now we describe the structure of X
c by a conservative approximation when we have no information about the support Ξ. Since the chance constraint in (2) is a distributionally robust joint chance constraint, it is difficult to describe the structure of its feasible set X
c exactly. We establish a conservative approximation in terms of a system of BMIs for the distributionally robust joint chance constraint when F
i
(
x
,
ξ
) is affinely depended on ξ. To this end, we introduce a set X
0
c:
(16)
X
0
c
=
x
∈
R
n
:
inf
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
>
0
]
≥
1
-
ϵ
.
Employing Lemmas 1 and 2, we show that the structure of X
0
c can be equivalently described by a system of BMIs, as stated as Lemma 5.Lemma 5.
Suppose thatF
i
(
x
,
ξ
) is affine in x and is affinely affected by ξ which is supported on Ξ
=
R
k, and suppose that there exists some ξ with F
i
(
x
,
ξ
)
<
0
(
i
=
1
,
…
,
n
) for each fixed x. Then X
0
c
⊆
X
c and X
0
c can be equivalently expressed as a system of BMIs:
(17)
X
0
c
=
x
∈
R
n
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
s
u
c
h
t
h
a
t
x
C
·
Y
c
≤
ϵ
,
z
>
0
,
Y
c
⪰
0
,
Y
c
∈
S
k
+
1
,
z
∈
R
n
Y
c
+
z
i
A
i
x
-
C
0
⪰
0
,
i
=
1
,
…
,
n
x
∈
R
n
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
s
u
c
h
t
h
a
t
x
,
with the constant matrix C
0
=
0
k
×
k
0
k
×
1
0
1
×
k
1.Proof.
Since(18)
inf
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
≥
0
]
≥
1
-
ϵ
⟺
sup
⁡
P
∈
P
P
[
F
(
x
,
ξ
)
<
0
]
≤
ϵ
,
it is clear that X
0
c
⊆
X
c. So it suffices to show that X
0
c can be expressed as (17) equivalently. x
∈
X
0
c implies that sup
⁡
P
∈
P
P
[
min
⁡
1
≤
i
≤
n
F
i
(
x
,
ξ
)
≤
0
]
≤
ϵ, which can be reexpressed as
(19)
sup
⁡
P
P
∈
P
E
[
1
{
min
⁡
1
≤
i
≤
n
F
i
(
x
,
ξ
)
≤
0
}
]
≤
ϵ
.
Then using Lemma 2, we can show that x
∈
X
0
c means that x satisfies
(20)
ϵ
≥
inf
⁡
C
·
Y
c
s.t.
ξ
T
1
Y
c
ξ
1
≥
1
{
min
⁡
i
F
i
(
x
,
ξ
)
≤
0
}
,
∀
ξ
∈
Ξ
,
Y
c
∈
S
k
+
1
.
Note that the semi-infinite constraint above is equivalent to
(21)
ξ
T
1
Y
c
ξ
1
≥
0
,
∀
ξ
∈
Ξ
,
(22)
ξ
T
1
Y
c
ξ
1
≥
1
,
∀
ξ
∈
{
ξ
:
min
⁡
i
F
i
(
x
,
ξ
)
≤
0
}
⋂
‍
Ξ
.
The constraint (22) can be expressed as
(23)
ξ
T
1
Y
c
ξ
1
≥
1
,
∀
ξ
∈
{
ξ
:
F
i
(
x
,
ξ
)
≤
0
}
⋂
‍
Ξ
,
∀
i
=
1
,
…
,
n
.
Since Ξ
=
R
k, the above implications can be reexpressed as the following implications:
(24)
ξ
T
1
A
i
(
x
)
ξ
1
≤
0
⟹
ξ
T
1
Y
c
ξ
1
≥
1
,
∀
i
=
1
,
…
,
n
.
Notice that A
i
(
x
) is affine in x and Y
c
⪰
0 by (21); then, by Lemma 1 and the assumptions of this lemma, we have that the implications above are equivalent to
(25)
∃
z
∈
R
n
,
such
that
z
i
≥
0
,
Y
c
+
z
i
A
i
x
-
C
0
⪰
0
,
i
=
1
,
…
,
n
.
So, we have
(26)
X
0
c
=
x
∈
R
k
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
such
that
C
·
Y
c
≤
ϵ
,
z
≥
0
,
Y
c
⪰
0
,
R
k
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
Y
c
+
z
i
A
i
x
-
C
0
⪰
0
,
i
=
1
,
…
,
n
x
∈
R
k
:
∃
Y
c
∈
S
k
+
1
,
z
∈
R
n
such
that
.
To complete the proof, it is sufficient to show that z
=
0 is impossible in (26). Otherwise, if there exists some z
i
=
0 in (25), by taking trace operator to the both sides of the BMIs above multiplied by C, we obtain C
·
Y
c
≥
1, which contradicts C
·
Y
c
≤
ϵ.


## 2.3.  The Conservative Approximation for the DROR

According to Lemma4, the DROR (2) can be expressed equivalently as
(27)
min
⁡
C
·
Y
v
s
.
t
.
Y
v
a
1
(
x
)
⋯
a
n
(
x
)
a
1
T
(
x
)
1
⋮
⋱
a
n
T
(
x
)
1
⪰
0
,
x
≥
0
,
x
∈
X
c
,
Y
v
∈
S
k
+
1
.
Notice that the set X
0
c is inside the feasible set X
c as stated in Lemma 5. So by replacing X
c by X
0
c in the problem above, we can obtain a problem with an optimal value not less than that of (2). Thus, putting Lemmas 4 and 5 together, we obtain conservative approximation of the DROR (2) in terms of the optimization with BMIs, as stated in Theorem 6.Theorem 6.
Suppose thatF
i
(
x
,
ξ
) is affine in x and is also affine with respect to ξ which is supported on Ξ
=
R
k, and suppose that there exists some ξ with F
i
(
x
,
ξ
)
<
0
(
i
=
1
,
…
,
n
) for each fixed x. Then the DROR (2) can be conservatively expressed as
(28)
min
⁡
C
·
Y
v
s
.
t
.
x
≥
0
,
z
>
0
,
C
·
Y
c
≤
ϵ
,
Y
c
⪰
0
,
Y
c
+
z
i
A
i
(
x
)
-
C
0
⪰
0
,
i
=
1
,
…
,
n
,
Y
v
a
1
(
x
)
⋯
a
n
(
x
)
a
1
T
(
x
)
1
⋮
⋱
a
n
T
(
x
)
1
⪰
0
,
x
∈
R
n
,
z
∈
R
n
,
Y
c
∈
S
k
+
1
,
Y
v
∈
S
k
+
1
.


## 3. The Conservative Approximation for the DROR with the Support Information

When the information about the supportΞ is also known, we use the similar argument of the proof in Theorem 6 to establish a more conservative approximation. It is worth mentioning that there is a slight difference between the proof in Theorem 6 and that in Theorem 7. The proof of Theorem 6 uses the equivalent form of the S-procedure, but the proof of Theorem 7 uses the implication form of the S-procedure, due to their different assumptions on the support.Theorem 7.
Suppose thatF
i
(
x
,
ξ
) is affine in x and is also affine with respect to uncertain data ξ which is supported on Ξ
=
Ξ
m
(
m
=
1,2
,
3,4
), respectively. Then the DROR (2) can be conservatively expressed as
(29)
min
⁡
C
·
Y
v
s
.
t
.
x
≥
0
,
z
>
0
,
u
c
0
≥
0
,
u
v
≥
0
,
u
c
i
≥
0
,
i
=
1
,
…
,
n
,
C
·
Y
c
≤
ϵ
,
Y
c
+
Π
m
(
u
c
0
)
⪰
0
,
Y
c
+
z
i
H
i
(
x
)
+
Π
m
(
u
c
i
)
-
C
0
⪰
0
,
i
=
1
,
…
,
n
,
Y
v
-
Π
m
(
u
v
)
h
1
(
x
)
⋯
h
n
(
x
)
h
1
T
(
x
)
1
⋮
⋱
h
n
T
(
x
)
1
⪰
0
,
x
,
z
∈
R
n
,
u
c
0
,
u
v
,
u
c
i
∈
R
J
m
,
Y
c
,
Y
v
∈
S
k
+
1
,
i
=
1
,
…
,
n
,
where J
1
=
2
k, J
2
=
k
+
1, J
3
=
l, and J
4
=
3
k
+
1
+
l, respectively.The proof for eachΞ
m, m
=
1,2
,
3,4 is similar to that of Lemmas 4 and 5, and we omit it here.


## 4. Numerical Experiments

In this section, we give preliminary numerical results with an example of a linear complementarity problem with a random parameter from [8] for the proposed method.Example 1.
Suppose that we have no information about the supportΞ and
(30)
F
x
,
ξ
:
=
x
1
-
ξ
x
2
+
3
-
2
ξ
-
ξ
x
1
+
2
x
2
+
ξ
x
3
-
2
-
ξ
ξ
x
2
+
3
x
3
-
3
-
ξ
,
where ξ is the random parameter with mean μ and covariance σ
2. This is a stochastic linear complementarity problem which has a unique solution x
*
=
(
0,1
,
1
)
T when ξ
∈
[
0,1
].We solve the problem by DROR employing the PENLAB solver (see [18]) for nonlinear semidefinite programs with different settings of μ and σ
2: case 1 for μ
=
0.5 and σ
2
=
1
/
12 and case 2 for μ
=
0 and σ
2
=
1. We run the codes for each case with ϵ
=
0.1,0.2,0.3 (denoted by DROR
0.1, DROR
0.2, and DROR
0.3), respectively. To compare the property of the DROR with the classical reformulation for the stochastic complementarity problem, we also run the ERM method employing the MatLab solver Fmincon with different samples which follow these specific distributions, respectively: (
a
)
ξ
~
U
(
0,1
), (
b
)
ξ
~
N
(
0.5
,
1
/
12
), (
c
)
ξ
~
U
(
-
3
,
3
), (
d
)
ξ
~
N
(
0,1
) (denoted by ERM
a, ERM
b, ERM
c, and ERM
d), respectively. The initial value for each run (ERM
a, ERM
b, ERM
c, ERM
d, and DROR
0.1, DROR
0.2, and DROR
0.3 for both cases) is set to be rand of appropriate dimensions and we evaluate these solutions for uniform samples and normal samples with given moments according to each case, respectively, using the indices compl, feas, and pr. The index compl measures the complementarity and the indices feas and pr measure the nonnegativity, which are defined as compl
(
x
)
=
(
1
/
N
)
∑
l
=
1
N
‍
x
T
(
F
(
x
,
ξ
l
)
)
+
,
feas
(
x
)
=
(
1
/
N
)
∑
l
=
1
N
‍
(
-
F
(
x
,
ξ
l
)
)
+, and pr
(
x
)
=
∏
i
=
1
n
‍
P
{
ξ
:
F
i
(
x
,
ξ
)
≥
0
}. We list the comparison results in Table 1.Table 1
Numerical comparison between the DROR and the ERM methods.
Case
Method
xsol
compl
feas
pr (%)
compl
feas
pr (%)
Uniform samples
Normal samples
1
DROR0.1
(0.000003, 1.000001, 1.000000)
5.44e −06
1.73e −07
100.0
5.76e −06
1.24e −02
96.4
DROR0.2
(0.000021, 1.000006, 0.999999)
3.39e −05
3.06e −06
100.0
3.60e −05
1.24e −02
92.9
DROR0.3
(0.000001, 1.000000, 1.000000)
1.44e −06
5.21e −07
100.0
1.54e −06
1.24e −02
96.4
ERMa
(0.000000, 0.999997, 1.000001)
1.44e −06
5.48e −06
100.0
1.53e −06
1.24e −02
96.4
ERMb
(0.044313, 0.998574, 1.002037)
7.11e −02
2.49e −02
0.0
7.54e −02
3.34e −02
1.8
2
DROR0.1
(6.001528, 1.000509, 7.001366)
1.81e +02
0.00e +00
100.0
1.80e +02
2.10e −03
99.8
DROR0.2
(3.001060, 1.000530, 4.000647)
5.43e +01
0.00e +00
100.0
5.40e +01
2.65e −02
97.4
DROR0.3
(1.583408, 1.000545, 2.582745)
1.97e +01
2.05e −02
91.2
1.96e +01
8.26e −02
89.3
ERMc
(0.367029, 0.911208, 1.082520)
1.65e +00
3.09e −01
27.5
1.60e +00
3.48e −01
22.4
ERMd
(0.403395, 0.841871, 1.130820)
1.92e +00
3.84e −01
15.3
1.88e +00
4.38e −01
9.6From Table1, we see that both the DROR and the ERM methods can obtain an approximate solution when the SCP has a common solution for all ξ, as shown in case 1. When the SCP has no common solution for all ξ, the DROR can obtain a solution to guarantee F
(
x
,
ξ
)
≥
0 with a higher probability and also with a lower feas, but the ERM method prefers a solution with a lower compl, as shown in case 2. Moreover, the quality of the solution by the DROR is independent of the specific distribution but relies on the first two moments only. However, the quality of the solution by the ERM method relies on the specific distribution seriously, as shown by the data with ERM
a and ERM
b.



---

*Source: 469587-2014-11-06.xml*