# Robust Linear Programming with Norm Uncertainty

Authors: Lei Wang; Hong Luo
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We consider the linear programming problem with uncertainty set described byp
,
w-norm. We suggest that the robust counterpart of this problem is equivalent to a computationally convex optimization problem. We provide probabilistic guarantees on the feasibility of an optimal robust solution when the uncertain coefficients obey independent and identically distributed normal distributions.


---

## Body

## 1. Introduction

Robust optimization is a rapidly developing methodology to address the optimization problems under uncertainty. Compared with sensitivity analysis and stochastic programming, the robust optimization approach can handle cases where fluctuations of the data may be large and can guarantee satisfaction of hard constraints which are required in some practical settings. The advantage of the robust optimization is that it could prevent the optimal solution against any realization of the uncertainty in a given bounded uncertainty set. The robust linear optimization problem where the data are uncertain was first introduced by Soyster [1]. The basic idea is to assume that the vector of uncertain data can be any point (scenario) in the uncertainty set, to find a solution that satisfies all the constraints for any possible scenario from the uncertainty set, and to optimize the worst-case value of the objective function. Ben-Tal and Nemirovski [2, 3] and El Ghaoui et al. [4, 5] addressed the overconservatism of robust solutions by allowing the uncertainty sets for the data to be ellipsoids and proposed some efficient algorithms to solve convex optimization problems under data uncertainty. Bertsimas et al. [6, 7] proposed a different approach to control the level of conservatism on the solution that has the advantage that leads to a linear optimization model. For more about the robust optimization, we refer to [8–15].Consider the following linear programming problem:(1)
max
⁡
c
T
x
s
.
t
.
A
~
x
≤
b
,
k
k
k
k
k
x
∈
P
x
,
where x
∈
R
n
×
1, A
~
∈
R
m
×
n is a uncertain matrix which belongs to an uncertainty set U, c
∈
R
n
×
1, and P
x is a given set. The robust counterpart of problem (1) is
(2)
max
⁡
c
T
x
s
.
t
.
A
~
x
≤
b
,
k
k
k
k
k
x
∈
P
x
,
k
k
k
k
k
A
~
∈
U
.An optimal solutionx
* is said to be a robust solution if and only if it satisfies all the constraints for any A
~
∈
U.In this paper, we consider the linear optimization problem (1) with uncertainty set described by (
p
,
w
)-norm for the reason not only to make up the disadvantages of the uncertain parameters of all possible values that will give the same weight, but also to consider the robust cost of the robust optimization model which is mentioned in [6]. We suggest the robust counterpart of problem (1) that is a computationally convex optimization problem. We also provide probabilistic guarantees on the feasibility of an optimal robust solution when the uncertain coefficients obey independent and identically distributed normal distributions.Here is the structure of this paper. In Section2, we introduce the (
p
,
w
)-norm and its dual norm and give the comparison with the Euclidean norm. In Section 3, we show that the linear optimization problem (1) with uncertainty set described by (
p
,
w
)-norm is equivalent to a convex programming. In Section 4, we provide probabilistic guarantees on the feasibility of an optimal robust solution when the uncertainty set U is described by the (
p
,
w
)-norm.


## 2. The(
p
,
w
)-Norm

In this section, we introduce the(
p
,
w
)-norm and its dual norm. Furthermore, we show worst-case bounds on the proximity of the (
p
,
w
)-norm as opposed to the Euclidean norm considered in Ben-Tal and Nemirovski [2, 10] and El Ghaoui et al. [4, 5].


### 2.1. The(
p
,
w
)-Norm and Its Dual

We consider theith constraint of the problem (1), a
i
′
x
≤
b
i. We denote by J
i the set of coefficients a
i
j, and a
~
i
j, j
∈
J
i takes values in the interval [
a
i
j
-
a
^
i
j
,
a
i
j
+
a
^
i
j
] according to a symmetric distribution with mean equal to the nominal value a
i
j. For every i, we introduce a parameter p
i, which takes values in the interval [
0
,
|
J
i
|
]. It is unlike the case that all of the a
i
j, j
∈
J
i will change, which is proposed by [1]. Our goal is to protect the cases that are up to ⌈
p
i
⌉ of these coefficients which are allowed to change and take the worst-case values at the same time. Next, we introduce the following definition of (
p
,
w
)-norm.Definition 1.
For a given nonzero vector,w
∈
R
n with w
j
>
0, j
=
1
,
…
,
n, we define the (
p
,
w
)-norm as
(3)
∥
y
∥
p
,
w
=
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
⁡
{
∑
j
∈
S
‍
w
j
|
y
j
|
}
,
with y
∈
R
n.Remark 2.
Obviously,∥
y
∥
p
,
w is indeed a norm, since(1)
∥
y
∥
p
,
w
≥
0, and ∥
y
∥
p
,
w
=
0 if and only if y
=
0, since w is not a zero matric, with w
j
>
0, j
=
1
,
…
,
n;
(2)
(4)
∥
α
y
∥
p
,
w
=
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
α
y
j
|
}
=
|
α
|
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
y
j
|
}
=
|
α
|
∥
y
∥
p
,
w
;
(3)
5555
(5)
∥
x
+
y
∥
p
,
w
=
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
x
j
+
y
j
|
}
≤
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
y
j
|
}
+
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
x
j
|
}
≤
∥
x
∥
p
,
w
+
∥
y
∥
p
,
w
.Remark 3.
(1) Supposed that(i)
y
1
≥
y
2
≥
·
·
·
≥
y
n
≥
0;
(ii)
w
1
=
w
2
=
·
·
·
=
w
⌊
p
⌋
=
1, w
⌈
p
⌉
=
p
-
⌊
p
⌋, w
i
≤
w
⌈
p
⌉, ⌈
p
⌉
<
i
≤
n;then the (
p
,
w
)-norm degenerates into D-norm studied by Bertsimas and Sim [6]; that is,
(6)
∥
y
∥
p
=
max
⁡
{
S
∪
t
∣
S
⊆
J
,
|
S
|
≤
⌊
p
⌋
,
t
∈
J
∖
S
}
⁡
{
∑
j
∈
S
‍
|
y
j
|
+
(
p
-
⌊
p
⌋
)
|
y
t
|
}
.
(2) Ifw
=
(
1
,
…
,
1
)
T and p
=
n, then (
p
,
w
)-norm degenerates into L
1, and we can get ∥
y
∥
p
,
w
=
∥
y
∥
n
,
e
=
∑
i
=
1
n
‍
y
i, i
=
1
,
…
,
n.
(3) Ifw
=
(
1
,
…
,
1
)
T and p
=
1, then (
p
,
w
)-norm degenerates into L
∞, and we have ∥
y
∥
p
,
w
=
∥
y
∥
1
,
e
=
max
⁡
|
y
i
|, i
=
1
,
…
,
n.
Next we derive the dual norm.Proposition 4.
The dual norm of the(
p
,
w
)-norm is
(7)
∥
s
∥
p
,
w
*
=
max
⁡
{
∥
s
w
∥
∞
,
∥
s
/
w
∥
1
⌈
p
⌉
}
,
with w
=
(
w
1
,
w
2
,
…
,
w
n
)
T, w
j
>
0
,
j
=
1
,
…
,
n.Proof.
The norm∥
y
∥
p
,
w is equivalent to
(8)
∥
y
∥
p
,
w
=
max
⁡
∑
j
=
1
n
‍
μ
j
w
j
|
y
j
|
s
.
t
.
∑
j
=
1
n
‍
μ
j
≤
⌈
p
⌉
,
kkkkk
0
≤
μ
j
≤
1
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
.
According to linear programming strong duality, we have(9)
min
⁡
⌈
p
⌉
r
+
∑
j
=
1
n
‍
t
j
s
.
t
.
r
+
t
j
≥
w
j
|
y
j
|
,
k
k
k
k
k
r
≥
0
,
k
k
k
k
k
t
j
≥
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
.
Then,∥
y
∥
p
,
w
≤
1 if and only if
(10)
⌈
p
⌉
r
+
∑
j
=
1
n
‍
t
j
≤
1
,
r
+
t
j
≥
w
j
|
y
j
|
,
r
≥
0
,
t
j
≥
0
,
w
j
>
0
,
j
=
1
,
…
,
n
,
is feasible.
We give the following dual norm∥
s
∥
p
,
w
* by
(11)
∥
s
∥
p
,
w
*
=
max
⁡
∥
y
∥
p
,
w
≤
1
s
′
y
.
From (10) we obtain that
(12)
∥
s
∥
p
,
w
*
=
max
⁡
s
′
y
s
.
t
.
⌈
p
⌉
r
+
∑
j
=
1
n
‍
t
j
≤
1
,
k
k
k
k
k
w
j
y
j
-
r
-
t
j
≤
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
-
w
j
y
j
-
r
-
t
j
≤
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
r
≥
0
,
k
k
k
k
k
t
j
≥
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
.
Using the LP duality again we have(13)
∥
s
∥
p
,
w
*
=
min
⁡
θ
s
.
t
.
⌈
p
⌉
θ
-
∑
j
=
1
n
‍
μ
j
-
∑
j
=
1
n
‍
ν
j
≥
0
,
kkkkk
θ
-
μ
j
-
ν
j
≥
0
,
j
=
1
,
…
,
n
,
kkkkk
(
μ
j
-
ν
j
)
w
j
=
s
j
,
j
=
1
,
…
,
n
,
kkkkk
θ
≥
0
,
μ
j
≥
0
,
ν
j
≥
0
,
kkkkkkkkkkkkkk
j
=
1
,
…
,
n
,
kkkkk
w
j
>
0
,
j
=
1
,
…
,
n
.
Thus,
(14)
∥
s
∥
p
,
w
*
=
min
⁡
θ
s
.
t
.
θ
≥
|
s
j
|
w
j
,
j
=
1
,
…
,
n
kk
kk
θ
≥
∑
j
=
1
n
‍
|
s
j
|
/
w
j
⌈
p
⌉
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
,
and we obtain that
(15)
∥
s
∥
p
,
w
*
=
max
⁡
{
∥
s
w
∥
∞
,
∥
s
/
w
∥
1
⌈
p
⌉
}
.Remark 5.
(1) When the(
p
,
w
)-norm degenerates into D-norm, we can get its dual norm:(16)
∥
s
∥
p
*
=
max
⁡
(
∥
s
∥
∞
,
∥
s
∥
1
/
p
)
.(2) When the(
p
,
w
)-norm degenerates into L
1, we can get its dual norm:
(17)
∥
s
∥
n
,
e
*
=
∥
s
∥
∞
.(3) When the(
p
,
w
)-norm degenerates into L
∞, we can get its dual norm:
(18)
∥
s
∥
1
,
e
*
=
∥
s
∥
1
.


### 2.2. Comparison with the Euclidean Norm

The uncertainty sets in the related literatures have been described using the Euclidean norm and it is of interest to study the proximity between the(
p
,
w
)-norm and the Euclidean norm.Proposition 6.
For everyy
∈
R
n,
(19)
min
⁡
{
min
⁡
j
∈
S
{
w
j
}
,
∑
j
∈
S
‍
w
j
n
}
≤
∥
y
∥
p
,
w
∥
y
∥
2
≤
∑
j
∈
S
‍
w
j
2
,
min
⁡
{
1
∑
k
∈
N
‍
w
k
2
,
min
⁡
k
∈
N
{
1
/
w
k
}
⌈
p
⌉
}
≤
∥
y
∥
p
,
w
*
∥
y
∥
2
≤
max
⁡
{
n
∑
k
∈
N
‍
w
k
2
⌈
p
⌉
,
min
⁡
k
∈
N
{
1
w
k
}
}
.Proof.
First, we will give a lower bound on∥
y
∥
p
,
w
/
∥
y
∥
2 by solving the following problem:
(20)
max
⁡
∑
j
∈
N
‍
y
j
2
s
.
t
.
∥
y
∥
p
,
w
=
1
,
where N
=
{
1
,
…
,
n
}.
LetS
=
{
1
,
…
,
⌈
p
⌉
}; we can get that y
j
≥
y
t, ∀
j
∈
S, and y
j
≤
y
t, ∀
j
∈
N
∖
S. It is easy to see that the objective function can never decrease if we let y
j
=
y
t, ∀
j
∈
N
∖
S; then we have that (20) is equivalent to the following problem:
(21)
max
⁡
∑
j
∈
S
‍
y
j
2
+
(
n
-
⌈
p
⌉
)
y
t
2
s
.
t
.
∑
j
∈
S
‍
w
j
|
y
j
|
=
1
,
k
k
k
k
k
w
j
>
0
,
k
k
k
k
k
y
j
≥
y
t
,
j
∈
S
,
k
k
k
k
k
y
t
≥
0
.
Our goal is to maximize the convex function over a polytope; then there exists an extreme point optimal solution for the above problem. We can get the|
S
|
+
1 extreme points:
(22)
y
j
=
e
j
w
j
,
j
∈
S
,
y
|
S
|
+
1
=
e
∑
j
∈
S
‍
w
j
,
where e
j is the unit vector with the jth element equal to one and the rest is equal to zero. Obviously, the problem can get the optimum value of max
⁡
{
max
⁡
j
∈
S
{
1
/
w
j
2
}
,
n
/
(
∑
j
∈
S
‍
w
j
)
2
}. Then the inequality follows as
(23)
∥
y
∥
2
≤
max
⁡
{
max
⁡
j
∈
S
{
1
w
j
}
,
n
∑
j
∈
S
‍
w
j
}
∥
y
∥
p
,
w
,
by taking the square root.
By the same way, in order to obtain an upper bound of∥
y
∥
p
,
w
/
∥
y
∥
2, by solving the following nonlinear optimization problem:
(24)
min
⁡
∑
j
∈
N
‍
y
j
2
s
.
t
.
∥
y
∥
p
,
w
=
1
,
clearly, the objective function can never increase with y
j
=
0, ∀
j
∈
N
∖
S, and we can show that the above problem is equivalent to the following problem:
(25)
min
⁡
∑
j
∈
S
‍
y
j
2
s
.
t
.
∑
j
∈
S
‍
w
j
|
y
j
|
=
1
k
k
k
k
k
w
j
>
0
,
k
k
k
k
k
y
j
≥
0
,
j
∈
S
.
Firstly, we use Lagrange multiplier methods reformulating the problem as(26)
L
(
y
,
μ
)
=
∑
j
∈
S
‍
y
j
2
+
μ
(
∑
j
∈
S
‍
w
j
y
j
-
1
)
.
Applying the KKT conditions for this problem, an optimal solution can be found:(27)
y
j
=
w
j
∑
j
∈
S
‍
w
j
2
,
j
∈
S
;
otherwise, y
j
=
0. It is easy to see that the optimal objective value is 1
/
∑
j
∈
S
‍
w
j
2. By taking the square root, we have that
(28)
∥
y
∥
2
≥
1
∑
j
∈
S
‍
w
j
2
∥
y
∥
p
,
w
;
that is,
(29)
∥
y
∥
p
,
w
≤
∑
j
∈
S
‍
w
j
2
∥
y
∥
2
.
Since
(30)
1
≤
∥
y
∥
1
∥
y
∥
2
≤
n
,
1
n
≤
∥
y
∥
∞
∥
y
∥
2
≤
1
.
So we can deduce that(31)
min
⁡
k
∈
N
{
1
w
k
}
≤
∥
y
/
w
∥
1
∥
y
∥
2
≤
n
∑
k
∈
N
‍
w
k
2
,
1
∑
k
∈
N
‍
w
k
2
≤
∥
y
/
w
∥
∞
∥
y
∥
2
≤
min
⁡
k
∈
N
{
1
w
k
}
,
∥
s
∥
p
,
w
*
=
max
⁡
{
∥
s
w
∥
∞
,
∥
s
/
w
∥
1
⌈
p
⌉
}
,
with w
=
(
w
1
,
w
2
,
…
,
w
n
)
T, w
i
>
0
,
i
=
1
,
…
,
n.
Thus, we have(32)
min
⁡
{
1
∑
k
∈
N
‍
w
k
2
,
min
⁡
k
∈
N
{
1
/
w
k
}
⌈
p
⌉
}
≤
∥
y
∥
p
,
w
*
∥
y
∥
2
≤
max
⁡
{
n
∑
k
∈
N
‍
w
k
2
⌈
p
⌉
,
min
⁡
k
∈
N
{
1
w
k
}
}
.
Therefore, the results hold.Remark 7.
(1) When∥
y
∥
p
,
w
=
∥
y
∥
p, we obtain the comparison between D-norm and Euclidean norm easily; that is,
(33)
min
⁡
{
1
,
p
n
}
≤
∥
y
∥
p
∥
y
∥
2
≤
⌊
p
⌋
+
(
p
-
⌊
p
⌋
)
2
.
The comparison between the duality of D-norm and Euclidean norm is
(34)
min
⁡
{
1
p
,
1
n
}
≤
∥
y
∥
p
*
∥
y
∥
2
≤
max
⁡
{
n
p
,
1
}
.
(2) When(
p
,
w
)-norm degenerates into L
1 and L
∞, the comparison results are
(35)
1
≤
∥
y
∥
1
∥
y
∥
2
≤
n
,
1
n
≤
∥
y
∥
∞
∥
y
∥
2
≤
1
.


## 2.1. The(
p
,
w
)-Norm and Its Dual

We consider theith constraint of the problem (1), a
i
′
x
≤
b
i. We denote by J
i the set of coefficients a
i
j, and a
~
i
j, j
∈
J
i takes values in the interval [
a
i
j
-
a
^
i
j
,
a
i
j
+
a
^
i
j
] according to a symmetric distribution with mean equal to the nominal value a
i
j. For every i, we introduce a parameter p
i, which takes values in the interval [
0
,
|
J
i
|
]. It is unlike the case that all of the a
i
j, j
∈
J
i will change, which is proposed by [1]. Our goal is to protect the cases that are up to ⌈
p
i
⌉ of these coefficients which are allowed to change and take the worst-case values at the same time. Next, we introduce the following definition of (
p
,
w
)-norm.Definition 1.
For a given nonzero vector,w
∈
R
n with w
j
>
0, j
=
1
,
…
,
n, we define the (
p
,
w
)-norm as
(3)
∥
y
∥
p
,
w
=
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
⁡
{
∑
j
∈
S
‍
w
j
|
y
j
|
}
,
with y
∈
R
n.Remark 2.
Obviously,∥
y
∥
p
,
w is indeed a norm, since(1)
∥
y
∥
p
,
w
≥
0, and ∥
y
∥
p
,
w
=
0 if and only if y
=
0, since w is not a zero matric, with w
j
>
0, j
=
1
,
…
,
n;
(2)
(4)
∥
α
y
∥
p
,
w
=
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
α
y
j
|
}
=
|
α
|
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
y
j
|
}
=
|
α
|
∥
y
∥
p
,
w
;
(3)
5555
(5)
∥
x
+
y
∥
p
,
w
=
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
x
j
+
y
j
|
}
≤
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
y
j
|
}
+
max
⁡
{
S
∣
S
⊆
J
,
|
S
|
≤
⌈
p
⌉
}
{
∑
j
∈
S
‍
w
j
|
x
j
|
}
≤
∥
x
∥
p
,
w
+
∥
y
∥
p
,
w
.Remark 3.
(1) Supposed that(i)
y
1
≥
y
2
≥
·
·
·
≥
y
n
≥
0;
(ii)
w
1
=
w
2
=
·
·
·
=
w
⌊
p
⌋
=
1, w
⌈
p
⌉
=
p
-
⌊
p
⌋, w
i
≤
w
⌈
p
⌉, ⌈
p
⌉
<
i
≤
n;then the (
p
,
w
)-norm degenerates into D-norm studied by Bertsimas and Sim [6]; that is,
(6)
∥
y
∥
p
=
max
⁡
{
S
∪
t
∣
S
⊆
J
,
|
S
|
≤
⌊
p
⌋
,
t
∈
J
∖
S
}
⁡
{
∑
j
∈
S
‍
|
y
j
|
+
(
p
-
⌊
p
⌋
)
|
y
t
|
}
.
(2) Ifw
=
(
1
,
…
,
1
)
T and p
=
n, then (
p
,
w
)-norm degenerates into L
1, and we can get ∥
y
∥
p
,
w
=
∥
y
∥
n
,
e
=
∑
i
=
1
n
‍
y
i, i
=
1
,
…
,
n.
(3) Ifw
=
(
1
,
…
,
1
)
T and p
=
1, then (
p
,
w
)-norm degenerates into L
∞, and we have ∥
y
∥
p
,
w
=
∥
y
∥
1
,
e
=
max
⁡
|
y
i
|, i
=
1
,
…
,
n.
Next we derive the dual norm.Proposition 4.
The dual norm of the(
p
,
w
)-norm is
(7)
∥
s
∥
p
,
w
*
=
max
⁡
{
∥
s
w
∥
∞
,
∥
s
/
w
∥
1
⌈
p
⌉
}
,
with w
=
(
w
1
,
w
2
,
…
,
w
n
)
T, w
j
>
0
,
j
=
1
,
…
,
n.Proof.
The norm∥
y
∥
p
,
w is equivalent to
(8)
∥
y
∥
p
,
w
=
max
⁡
∑
j
=
1
n
‍
μ
j
w
j
|
y
j
|
s
.
t
.
∑
j
=
1
n
‍
μ
j
≤
⌈
p
⌉
,
kkkkk
0
≤
μ
j
≤
1
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
.
According to linear programming strong duality, we have(9)
min
⁡
⌈
p
⌉
r
+
∑
j
=
1
n
‍
t
j
s
.
t
.
r
+
t
j
≥
w
j
|
y
j
|
,
k
k
k
k
k
r
≥
0
,
k
k
k
k
k
t
j
≥
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
.
Then,∥
y
∥
p
,
w
≤
1 if and only if
(10)
⌈
p
⌉
r
+
∑
j
=
1
n
‍
t
j
≤
1
,
r
+
t
j
≥
w
j
|
y
j
|
,
r
≥
0
,
t
j
≥
0
,
w
j
>
0
,
j
=
1
,
…
,
n
,
is feasible.
We give the following dual norm∥
s
∥
p
,
w
* by
(11)
∥
s
∥
p
,
w
*
=
max
⁡
∥
y
∥
p
,
w
≤
1
s
′
y
.
From (10) we obtain that
(12)
∥
s
∥
p
,
w
*
=
max
⁡
s
′
y
s
.
t
.
⌈
p
⌉
r
+
∑
j
=
1
n
‍
t
j
≤
1
,
k
k
k
k
k
w
j
y
j
-
r
-
t
j
≤
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
-
w
j
y
j
-
r
-
t
j
≤
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
r
≥
0
,
k
k
k
k
k
t
j
≥
0
,
j
=
1
,
…
,
n
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
.
Using the LP duality again we have(13)
∥
s
∥
p
,
w
*
=
min
⁡
θ
s
.
t
.
⌈
p
⌉
θ
-
∑
j
=
1
n
‍
μ
j
-
∑
j
=
1
n
‍
ν
j
≥
0
,
kkkkk
θ
-
μ
j
-
ν
j
≥
0
,
j
=
1
,
…
,
n
,
kkkkk
(
μ
j
-
ν
j
)
w
j
=
s
j
,
j
=
1
,
…
,
n
,
kkkkk
θ
≥
0
,
μ
j
≥
0
,
ν
j
≥
0
,
kkkkkkkkkkkkkk
j
=
1
,
…
,
n
,
kkkkk
w
j
>
0
,
j
=
1
,
…
,
n
.
Thus,
(14)
∥
s
∥
p
,
w
*
=
min
⁡
θ
s
.
t
.
θ
≥
|
s
j
|
w
j
,
j
=
1
,
…
,
n
kk
kk
θ
≥
∑
j
=
1
n
‍
|
s
j
|
/
w
j
⌈
p
⌉
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
,
and we obtain that
(15)
∥
s
∥
p
,
w
*
=
max
⁡
{
∥
s
w
∥
∞
,
∥
s
/
w
∥
1
⌈
p
⌉
}
.Remark 5.
(1) When the(
p
,
w
)-norm degenerates into D-norm, we can get its dual norm:(16)
∥
s
∥
p
*
=
max
⁡
(
∥
s
∥
∞
,
∥
s
∥
1
/
p
)
.(2) When the(
p
,
w
)-norm degenerates into L
1, we can get its dual norm:
(17)
∥
s
∥
n
,
e
*
=
∥
s
∥
∞
.(3) When the(
p
,
w
)-norm degenerates into L
∞, we can get its dual norm:
(18)
∥
s
∥
1
,
e
*
=
∥
s
∥
1
.


## 2.2. Comparison with the Euclidean Norm

The uncertainty sets in the related literatures have been described using the Euclidean norm and it is of interest to study the proximity between the(
p
,
w
)-norm and the Euclidean norm.Proposition 6.
For everyy
∈
R
n,
(19)
min
⁡
{
min
⁡
j
∈
S
{
w
j
}
,
∑
j
∈
S
‍
w
j
n
}
≤
∥
y
∥
p
,
w
∥
y
∥
2
≤
∑
j
∈
S
‍
w
j
2
,
min
⁡
{
1
∑
k
∈
N
‍
w
k
2
,
min
⁡
k
∈
N
{
1
/
w
k
}
⌈
p
⌉
}
≤
∥
y
∥
p
,
w
*
∥
y
∥
2
≤
max
⁡
{
n
∑
k
∈
N
‍
w
k
2
⌈
p
⌉
,
min
⁡
k
∈
N
{
1
w
k
}
}
.Proof.
First, we will give a lower bound on∥
y
∥
p
,
w
/
∥
y
∥
2 by solving the following problem:
(20)
max
⁡
∑
j
∈
N
‍
y
j
2
s
.
t
.
∥
y
∥
p
,
w
=
1
,
where N
=
{
1
,
…
,
n
}.
LetS
=
{
1
,
…
,
⌈
p
⌉
}; we can get that y
j
≥
y
t, ∀
j
∈
S, and y
j
≤
y
t, ∀
j
∈
N
∖
S. It is easy to see that the objective function can never decrease if we let y
j
=
y
t, ∀
j
∈
N
∖
S; then we have that (20) is equivalent to the following problem:
(21)
max
⁡
∑
j
∈
S
‍
y
j
2
+
(
n
-
⌈
p
⌉
)
y
t
2
s
.
t
.
∑
j
∈
S
‍
w
j
|
y
j
|
=
1
,
k
k
k
k
k
w
j
>
0
,
k
k
k
k
k
y
j
≥
y
t
,
j
∈
S
,
k
k
k
k
k
y
t
≥
0
.
Our goal is to maximize the convex function over a polytope; then there exists an extreme point optimal solution for the above problem. We can get the|
S
|
+
1 extreme points:
(22)
y
j
=
e
j
w
j
,
j
∈
S
,
y
|
S
|
+
1
=
e
∑
j
∈
S
‍
w
j
,
where e
j is the unit vector with the jth element equal to one and the rest is equal to zero. Obviously, the problem can get the optimum value of max
⁡
{
max
⁡
j
∈
S
{
1
/
w
j
2
}
,
n
/
(
∑
j
∈
S
‍
w
j
)
2
}. Then the inequality follows as
(23)
∥
y
∥
2
≤
max
⁡
{
max
⁡
j
∈
S
{
1
w
j
}
,
n
∑
j
∈
S
‍
w
j
}
∥
y
∥
p
,
w
,
by taking the square root.
By the same way, in order to obtain an upper bound of∥
y
∥
p
,
w
/
∥
y
∥
2, by solving the following nonlinear optimization problem:
(24)
min
⁡
∑
j
∈
N
‍
y
j
2
s
.
t
.
∥
y
∥
p
,
w
=
1
,
clearly, the objective function can never increase with y
j
=
0, ∀
j
∈
N
∖
S, and we can show that the above problem is equivalent to the following problem:
(25)
min
⁡
∑
j
∈
S
‍
y
j
2
s
.
t
.
∑
j
∈
S
‍
w
j
|
y
j
|
=
1
k
k
k
k
k
w
j
>
0
,
k
k
k
k
k
y
j
≥
0
,
j
∈
S
.
Firstly, we use Lagrange multiplier methods reformulating the problem as(26)
L
(
y
,
μ
)
=
∑
j
∈
S
‍
y
j
2
+
μ
(
∑
j
∈
S
‍
w
j
y
j
-
1
)
.
Applying the KKT conditions for this problem, an optimal solution can be found:(27)
y
j
=
w
j
∑
j
∈
S
‍
w
j
2
,
j
∈
S
;
otherwise, y
j
=
0. It is easy to see that the optimal objective value is 1
/
∑
j
∈
S
‍
w
j
2. By taking the square root, we have that
(28)
∥
y
∥
2
≥
1
∑
j
∈
S
‍
w
j
2
∥
y
∥
p
,
w
;
that is,
(29)
∥
y
∥
p
,
w
≤
∑
j
∈
S
‍
w
j
2
∥
y
∥
2
.
Since
(30)
1
≤
∥
y
∥
1
∥
y
∥
2
≤
n
,
1
n
≤
∥
y
∥
∞
∥
y
∥
2
≤
1
.
So we can deduce that(31)
min
⁡
k
∈
N
{
1
w
k
}
≤
∥
y
/
w
∥
1
∥
y
∥
2
≤
n
∑
k
∈
N
‍
w
k
2
,
1
∑
k
∈
N
‍
w
k
2
≤
∥
y
/
w
∥
∞
∥
y
∥
2
≤
min
⁡
k
∈
N
{
1
w
k
}
,
∥
s
∥
p
,
w
*
=
max
⁡
{
∥
s
w
∥
∞
,
∥
s
/
w
∥
1
⌈
p
⌉
}
,
with w
=
(
w
1
,
w
2
,
…
,
w
n
)
T, w
i
>
0
,
i
=
1
,
…
,
n.
Thus, we have(32)
min
⁡
{
1
∑
k
∈
N
‍
w
k
2
,
min
⁡
k
∈
N
{
1
/
w
k
}
⌈
p
⌉
}
≤
∥
y
∥
p
,
w
*
∥
y
∥
2
≤
max
⁡
{
n
∑
k
∈
N
‍
w
k
2
⌈
p
⌉
,
min
⁡
k
∈
N
{
1
w
k
}
}
.
Therefore, the results hold.Remark 7.
(1) When∥
y
∥
p
,
w
=
∥
y
∥
p, we obtain the comparison between D-norm and Euclidean norm easily; that is,
(33)
min
⁡
{
1
,
p
n
}
≤
∥
y
∥
p
∥
y
∥
2
≤
⌊
p
⌋
+
(
p
-
⌊
p
⌋
)
2
.
The comparison between the duality of D-norm and Euclidean norm is
(34)
min
⁡
{
1
p
,
1
n
}
≤
∥
y
∥
p
*
∥
y
∥
2
≤
max
⁡
{
n
p
,
1
}
.
(2) When(
p
,
w
)-norm degenerates into L
1 and L
∞, the comparison results are
(35)
1
≤
∥
y
∥
1
∥
y
∥
2
≤
n
,
1
n
≤
∥
y
∥
∞
∥
y
∥
2
≤
1
.


## 3. Robust Counterpart

In this section, we will show that the robust formulation of (1) with the (
p
,
w
)-norm is equivalent to a linear programming problem.We consider the following robust formulation of (1) with the (
p
,
w
)-norm:
(36)
max
⁡
c
T
x
s
.
t
.
∑
j
=
1
n
‍
a
i
j
x
j
+
max
⁡
{
S
i
∣
S
i
⊆
J
i
,
|
S
i
|
=
⌈
p
i
⌉
}
{
∑
j
∈
S
i
‍
a
^
i
j
w
j
y
j
}
kkkkk
≤
b
i
,
i
=
1
,
…
,
n
,
kkkkk
-
y
j
≤
x
j
≤
y
j
,
j
=
1
,
…
,
n
,
kkkkk
l
≤
x
≤
u
,
kkkkk
y
j
≥
0
,
j
=
1
,
…
,
n
,
kkkkk
w
j
>
0
,
j
=
1
,
…
,
n
.Ifp
i is selected as an integer, the protection function of the ith constraint is
(37)
β
i
(
x
,
p
i
)
=
max
⁡
{
S
i
|
S
i
⊆
J
i
,
|
S
i
|
=
p
i
}
{
∑
j
∈
S
i
‍
a
^
i
j
w
j
|
x
j
|
}
.
Note that when p
i
=
0, β
i
(
x
,
p
i
)
=
0, the constraints are equivalent to the nominal problem. And if p
i
=
|
J
i
|, w
j
=
1, ∀
j, we have the method of Soyster [1]. Likewise, if we assume that y
1
≥
y
2
≥
·
·
·
≥
y
n
≥
0 and w
1
=
w
2
=
·
·
·
=
w
⌊
p
⌋
=
1, w
⌈
p
⌉
=
p
-
⌊
p
⌋, we have the method of Bertsimas and Sim [6]. Therefore, by varying p
i
∈
[
0
,
|
J
i
|
], we have the flexibility of adjusting the robustness of the method against the level of conservatism of the solution.We need the following proposition to reformulate (36) as a linear programming problem.Proposition 8.
Given a vectorx
*, the protection function of the ith constraint,
(38)
β
i
(
x
*
,
p
i
)
=
max
⁡
{
S
i
∣
S
i
⊆
J
i
,
|
S
i
|
=
⌈
p
i
⌉
}
{
∑
j
∈
S
i
‍
a
^
i
j
w
j
|
x
j
*
|
}
,
is equivalent to the following linear programming problem:
(39)
β
i
(
x
*
,
p
i
)
=
max
⁡
∑
j
∈
J
i
‍
a
^
i
j
w
j
|
x
j
*
|
z
i
j
s
.
t
.
∑
j
∈
J
i
‍
z
i
j
≤
⌈
p
i
⌉
,
kkkkk
0
≤
z
i
j
≤
1
,
∀
j
∈
J
i
,
kkkkk
w
j
>
0
,
j
=
1
,
…
,
n
.Proof.
An optimal solution of problem (39) obviously consists of ⌈
p
i
⌉ variables at 1, which is equivalent to a subset
(40)
{
S
i
∣
S
i
⊆
J
i
,
|
S
i
|
=
⌈
p
i
⌉
}
.
The objection function of problem (39) converts to
(41)
{
∑
j
∈
S
i
‍
a
^
i
j
w
j
|
x
j
*
|
}
,
which is equivalent to problem (38).Next we will reformulate problem (36) as a linear programming problem.Theorem 9.
Problem (36) is equivalent to the following linear programming problem:
(42)
max
⁡
c
T
x
s
.
t
.
∑
j
=
1
n
‍
a
i
j
x
j
+
z
i
⌈
p
i
⌉
kkkkk
+
∑
j
∈
J
i
‍
t
i
j
≤
b
i
i
=
1
,
…
,
n
,
kkkkk
z
i
+
t
i
j
≥
a
^
i
j
w
j
y
j
∀
i
,
j
∈
J
i
kkkkk
-
y
j
≤
x
j
≤
y
j
j
=
1
,
…
,
n
,
kkkkk
l
j
≤
x
j
≤
u
j
j
=
1
,
…
,
n
,
kkkkk
t
i
j
≥
0
∀
i
,
j
∈
J
i
,
kkkkk
y
j
≥
0
j
=
1
,
…
,
n
,
kkkkk
z
i
≥
0
i
=
1
,
…
,
n
,
kkkkk
w
j
>
0
j
=
1
,
…
,
n
.Proof.
First, we consider the dual problem of (39):
(43)
min
⁡
∑
j
∈
J
i
‍
t
i
j
+
⌈
p
i
⌉
z
i
s
.
t
.
z
i
+
t
i
j
≥
a
^
i
j
w
j
|
x
j
*
|
,
∀
i
,
j
∈
J
i
,
k
k
k
k
k
t
i
j
≥
0
,
∀
j
∈
J
i
,
k
k
k
k
k
z
i
≥
0
,
i
=
1
,
…
,
n
,
k
k
k
k
k
w
j
>
0
,
j
=
1
,
…
,
n
.
Since problem (39) is feasible and bounded for all p
i
∈
[
0
,
|
J
i
|
], by strong duality, we know that the dual problem (43) is also feasible and bounded and their objective values coincide. By Proposition 8, we obtain that β
i
(
x
*
,
p
i
) is equivalent to the objective function value of (43). Substituting in problem (36), we have that problem (36) equals the linear programming problem (42).Remark 10.
When(
p
,
w
)-norm degenerates into D-norm, we have the following robust counterpart of problem (36) [6]:
(44)
max
⁡
c
T
x
s
.
t
.
∑
j
=
1
n
‍
a
i
j
x
j
+
z
i
Γ
i
kkkkkk
+
∑
j
∈
J
i
‍
p
i
j
≤
b
i
,
i
=
1
,
…
,
n
,
kkkkkk
z
i
+
p
i
j
≥
a
^
i
j
y
j
,
∀
i
,
j
∈
J
i
,
kkkkkk
-
y
j
≤
x
j
≤
y
j
,
j
=
1
,
…
,
n
,
kkkkkk
l
j
≤
x
j
≤
u
j
,
j
=
1
,
…
,
n
,
kkkkkk
p
i
j
≥
0
,
∀
i
,
j
∈
J
i
,
kkkkkk
y
j
≥
0
,
j
=
1
,
…
,
n
,
kkkkkk
z
i
≥
0
,
i
=
1
,
…
,
n
.


## 4. Probabilistic Guarantees

In this section, we will provide probabilistic guarantees on the feasibility of an optimal robust solution when the uncertainty setU is described by the (
p
,
w
)-norm.Proposition 11.
We denote byS
i
* and t
i
* the set and the index, respectively, which achieve the maximum for β
i
(
x
*
,
p
i
) in (38). Assume that x
* is an optimal solution of problem (42). The violated probability of the ith constraint satisfies
(45)
Pr
(
∑
j
‍
a
~
i
j
x
j
*
>
b
i
)
≤
Pr
(
∑
j
∈
J
i
‍
γ
i
j
η
i
j
≥
Ξ
)
,
where(46)
γ
i
j
=
{
1
,
if
j
∈
S
i
*
,
a
^
i
j
|
x
j
*
|
a
^
i
r
*
|
x
r
*
*
|
,
if
j
∈
J
i
∖
S
i
*
,
r
*
=
arg
⁡
min
⁡
r
∈
S
i
*
⁡
a
^
i
r
|
x
r
*
|
.Proof.
Letx
*, S
i
* be the solution of problem (36). Then the violated probability of the ith constraint is
(47)
Pr
(
∑
j
‍
a
~
i
j
x
j
*
>
b
i
)
=
Pr
(
∑
j
‍
a
i
j
x
j
*
+
∑
j
∈
J
i
‍
η
i
j
a
^
i
j
x
j
*
>
b
i
)
≤
Pr
(
∑
j
∈
J
i
‍
η
i
j
a
^
i
j
|
x
j
*
|
>
∑
j
∈
S
i
*
‍
a
^
i
j
w
j
|
x
j
*
|
)
=
Pr
(
∑
j
∈
J
i
∖
S
i
*
‍
η
i
j
a
^
i
j
|
x
j
*
|
>
∑
j
∈
S
i
*
‍
a
^
i
j
|
x
j
*
|
(
w
j
-
η
i
j
)
)
≤
Pr
(
∑
j
∈
J
i
∖
S
i
*
‍
η
i
j
a
^
i
j
|
x
j
*
|
>
a
^
i
r
*
|
x
r
*
*
|
∑
j
∈
S
i
*
‍
(
w
j
-
η
i
j
)
)
≤
Pr
(
∑
j
∈
J
i
∖
S
i
*
‍
η
i
j
a
^
i
j
|
x
j
*
|
a
^
i
r
*
|
x
r
*
*
|
+
∑
j
∈
S
i
*
‍
η
i
j
>
∑
j
=
1
⌈
p
i
⌉
‍
w
j
)
=
Pr
(
∑
j
∈
J
i
‍
γ
i
j
η
i
j
>
∑
j
=
1
⌈
p
i
⌉
‍
w
j
)
≤
Pr
(
∑
j
∈
J
i
‍
γ
i
j
η
i
j
≥
∑
j
=
1
⌈
p
i
⌉
‍
w
j
)
.
Let Ξ
=
∑
j
=
1
⌈
p
i
⌉
‍
w
j; we get the result.Remark 12.
Clearly,Ξ is related to p
i and w
=
(
w
1
,
w
2
,
…
,
w
n
)
T; the role of the parameter X
i or p
i (for w is a given vector) is to adjust the robustness of the proposed method against the level of conservatism of the solution. We define Ξ and p
i as robust cost and protection level, which control the tradeoff between the probability of violation and the effect to the objective function of the nominal problem.
Naturally we want to bound the probabilityPr
(
∑
j
∈
J
i
‍
γ
i
j
η
i
j
≥
Ξ
). The following result provides a bound that is independent of the solution x
*.Theorem 13.
Letη
i
j, j
∈
J
i be independent and symmetrically distributed random variables in [
-
1,1
]; then we have
(48)
Pr
(
∑
j
∈
J
i
‍
γ
i
j
η
i
j
≥
Ξ
)
≤
exp
⁡
(
-
(
Ξ
)
2
2
|
J
i
|
)
.Proof.
Letθ
>
0. Then we obtain that
(49)
Pr
(
∑
j
∈
J
i
‍
γ
i
j
η
i
j
≥
ξ
)
≤
E
[
exp
⁡
(
θ
∑
j
∈
J
i
‍
γ
i
j
η
i
j
)
]
exp
⁡
(
θ
Ξ
)
=
∏
j
∈
J
i
‍
E
[
exp
⁡
(
θ
γ
i
j
η
i
j
)
]
exp
⁡
(
θ
Ξ
)
=
∏
j
∈
J
i
‍
2
∫
0
1
∑
k
=
0
∞
‍
(
(
θ
γ
i
j
η
)
2
k
/
(
2
k
)
!
)
d
F
η
i
j
(
η
)
exp
⁡
(
θ
Ξ
)
≤
∏
j
∈
J
i
‍
∑
k
=
0
∞
‍
(
(
θ
γ
i
j
)
2
k
/
(
2
k
)
!
)
exp
⁡
(
θ
Ξ
)
≤
∏
j
∈
J
i
‍
exp
⁡
(
θ
2
γ
i
j
2
/
2
)
exp
⁡
(
θ
Ξ
)
≤
exp
⁡
(
|
J
i
|
θ
2
2
-
θ
Ξ
)
,
where we use the knowledge of Markov’s inequality, the independence and symmetric distribution, and γ
i
j
≤
1. Selecting θ
=
Ξ
/
|
J
i
|, we obtain the result of Theorem 13.


## 5. Conclusions

In this paper, we introduce the definition of(
p
,
w
)-norm, its dual, and some propositions to show a new uncertainty set. We suggest that the robust counterpart of linear programming problem described by (
p
,
w
)-norm is a computationally convex optimization problem. We provide probabilistic guarantees on the feasibility of an optimal robust solution when the uncertain coefficients obey independent and identically distributed normal distributions.



---

*Source: 209239-2014-05-11.xml*