Presentation

Recent Advances in
Robust Optimization
Aharon Ben-Tal
MINERVA Optimization Center
Technion – Israel Institute of Technology
♣ Robust Optimization is a methodology for processing uncertain
optimization problems
min {f (x, ζ) : F (x, ζ) ∈ K}
x
• x ∈ Rn is the decision vector
• ζ ∈ Rd is the data (or data perturbation)
• f (x, ζ) : Rn × Rd → R and F (x, ζ) : Rn × Rd → Rm are given functions,
and K ⊂ Rm is a given set.
f (·, ·), F (·, ·), K form the structure of the uncertain problem.
♣ In contrast to Stochastic Programming, RO does not assume
stochastic nature of data ζ and uses instead uncertain-but-bounded
uncertainty model: ζ runs through a given (typically, compact) uncertainty set Z ⊂ Rd.
♣ RO, people:
• 1973: A.L. Soyster (LP)
• 1997: P. Kouvelis & G. Yu (IP)
L. El Ghaoui & H. Lebret & F. Oustry
• 1997 –:
(CP)
A. Ben-Tal & A. Nemirovski
• 2000 –: E. Adida, A. Atamturk, A. Beck, D. Bertsimas,
C. Bhattacharyya, H.-G. Bock, S. Boyd, G. Calafiore, M. Diehl,
Y. Eldar, E. Erdogan, L. Grate, E. Guslitzer, B. Golany,
D. Goldfarb, C. Hol, G. Iyengar, M. Jordan, E. Kostina,
O. Kostyukova, G. Lanckriet, A. Nilim, M. Sim, D. Pachamanova,
C. Roos, C. Schrerer, A. Sood, A. Thiele, J.-Ph. Vial, M. Zhang,...
♠ RO, applications:
• Structural/Circuit/Network Design • Control • Signal Processing • Machine Learning • Portfolio Optimization • Inventory...
Example of uncertain LP: Multi-product inventory with backlogged
demand and shared warehouse capacity
C
min
C,xt ,yt ,wt ,vt
s.t.
•
•
•
•
PT
0
t=1 [ch yt
[inventory management cost]
+ c0bwt + c0pvt] ≤ C [cost description]
xt+1 = xt + vt − ζt
[balance equations]
−xt ≤ wt, 0 ≤ wt
[bounds on backlogged demand]
q 0 yt ≤ Q
[warehouse capacity bound]
xt ≤ y t , 0 ≤ y t
[bounds on [xt]+]
v t ≤ vt ≤ v t
[bounds on orders]
xt ∈ Rd: inventory state at time t
•
vt ∈ Rd: replenishment orders at time t •
yt ∈ Rd: stored items at time t
•
wt ∈ Rd: backlogged demand at time t •
• Uncertain data: demands
q ∈ Rd+: storage coefficients
co ∈ Rd+: ordering costs
ch ∈ Rd+: holding costs
cb ∈ Rd+: backlog penalty
ζ = [ζ1; ...; ζT ]
n
o
min {f (x, ζ) : F (x, ζ) ∈ K} : ζ ∈ Z
x
(Unc)
Assume that our “decision environment” is such that
• All decisions xj should be made before ζ “reveals itself ” and
thus should be independent of ζ
• The constraints are “hard”: their violations cannot be tolerated
• We intend to take full care of all data ζ ∈ Z and do not care
what happens when ζ 6∈ Z.
Under these assumptions, seemingly the only meaningful way to
process (Unc) is to solve the Robust Counterpart
min {t : ∀ζ ∈ Z : f (x, ζ) ≤ t, F (x, ζ) ∈ K}
t,x
of the uncertain problem.
(RC)
Example: To build the RC of the Inventory problem, we use balance
equations to eliminate the states and pass to the RC of the resulting
inequality constrained problem, thus arriving at
min
C,yt ,wt ,vt
s.t.
C
PT
0
0
0
t=1 [ch yt + cb wt + cp vt ] ≤ C
P
x1 + τt−1
=1 [vτ − ζτ ] ≤ yt , 0 ≤ yt
Pt−1
−x1 − τ =1[xτ − ζτ ] ≤ wt, 0 ≤
v t ≤ vt ≤ v t , q 0 yt ≤ Q







wt 





∀ζ ∈ Z
(RC)
Note: When Z is a computationally tractable convex set, the semiinfinite problem (RC) is computationally tractable. E.g., when Z is
polyhedral: Z = {ζ : ∃u : P ζ + Qu + r ≥ 0}, RC can be converted into
an explicit LP program of sizes polynomial in T, d and the sizes of
the representation of Z.
• In dynamical decision-making, some of the decisions xj should
be made when the actual data becomes partially known and thus
can depend on the corresponding portions of the data
Example: In the Inventory problem with uncertain demand,
replenishment orders vt of day t usually can depend on the
actual demands at days 1, ..., t − 1.
♣ To account for adjustability, we allow for every xj to depend on a
prescribed portion Pj ζ of ζ: xj = Xj (Pj ζ), thus arriving at Adjustable
Robust Counterpart
min n {t : ∀ζ ∈ Z : f (X(ζ), ζ) ≤ t, F (X(ζ), ζ) ∈ K}
t,{Xj (·)}j=1
[X(ζ) = {Xj (Pj ζ)}]
(ARC)
Note: ARC is infinite-dimensional and thus is typically heavily computationally intractable. Seemingly the only applicable technique
is Dynamic Programming ⇒“curse of dimensionality”
♣ To overcome, to some extent, intractability of ARC, we restrict
the decision rules to be affine: Xj (Pj ζ) = ξj0 + ξjT Pj ζ, thus arriving at
the Affinely Adjustable Robust Counterpart
min
t,{ξj0 ,ξj }nj=1
{t : ∀ζ ∈ Z : f (X(ζ), ζ) ≤ t, F (X(ζ), ζ) ∈ K}
[X(ζ) = {ξj0 + ξjT Pj ζ}nj=1]
(AARC)
Example: The only “actual decisions” in the Inventory problem are
orders vt. Assume that vt can depend on the preceding demands
ζ t−1 = [ζ1; ...; ζt−1]. To build the AARC, we
• introduce linear decision rules for the orders vt = vt0 + Vtζ t−1
• make xt, yt, wt affine functions of ζ: xt = x0t + Xtζ, yt = yt0 + Ytζ, wt =
wt0 + Wtζ, thus ending up with
min
P
C,vt0 ,Vt ,...,wt0 ,Wt
C

0 0
0
0 0
t−1
[c
[y
+
Y
ζ]
+
c
[w
+
W
ζ]
+
c
[v
+
V
ζ
]]
≤
C
t
t
t

p t
b t
t≤T h t



0
0
0
t−1

xt+1 + Xt+1ζ = xt + Xtζ + vt + Vtζ − ζt


0
0
0
s.t. xt + Xtζ ≤ yt + Ytζ, 0 ≤ yt + Ytζ
∀ζ ∈ Z



−[x0t + Xtζ] ≤ wt0 + Wtζ, 0 ≤ wt0 + Wtζ




0
t−1
0 0
v t ≤ v t + Vt ζ
≤ v t, q [yt + Ytζ] ≤ Q
(AARC)
Note: The AARC of the Inventory problem is computationally
tractable provided that Z is so. E.g., when Z is a polyhedral set,
(AARC) is equivalent to an explicit LP program.
Example (continued): Consider single-product Inventory with N = 10
and a box uncertainty set: (1 − ρ)ζ n ≤ ζ ≤ (1 + ρ)ζ n. Here the ARC is
well within the grasp of Dynamic Programming.
♣ How large are the gaps in the chain Opt(ARC) ≤ Opt(AARC) ≤
Opt(RC) ?
• We built a sample of 768 Inventory problems with uncertainty of
10% – 50% by picking at random cost coefficients, storage capacity and nominal demand trajectory ζ n and subsequent filtering out
problems with infeasible ARC’s.
♠ It turns out that Opt(ARC) = Opt(AARC) in every one of these 768
problems!
Note: This phenomenon disappears when passing from minimizing the worst-case inventory management cost to minimizing the
average of this cost.
.
♠ Opt(RC) was typically essentially worse than Opt(ARC) = Opt(AARC):
Opt(RC)
Range of Opt(ARC)
1 (1, 2] (2, 10] (10, 1000] ∞
Frequency in the sample 38% 23% 14%
11%
15%
♣ In the RO context, affine decision rules not necessarily are bad!
.
♣ Robust Counterparts of uncertain problem are semi-infinite programs and thus can be intractable even when all instances of the
uncertain problem are easy to solve.
⇒ When Robust Counterparts are computationally tractable?
What to do if it is not the case?
♣ “Solvable case”: Uncertain LP
Theorem. The RC/AARC of uncertain affinely perturbed LP problem
n
o
T
min cζ x + dζ : [aiζ ]T x + biζ ≥ 0, i = 1, ..., m : ζ ∈ Z
x
with fixed recourse is computationally tractable. With Z given by
a strictly feasible LP/CQP/SDP representation, the RC/AARC is
an explicit LP/CQP/SDP program of sizes polynomial in the size of
instances and the size of the representation of the uncertainty set.
Semi-Infinite Convex Quadratic Programming
♣ Tractability of a semi-infinite convex quadratically constrained program
T
T T
T
m
min
{c
x
:
x
A
A
x
+
2b
x
+
c
≤
0
,
∀
(i
=
1,
...,
m,
{A
,
b
,
c
}
i
i
i
i
i
i
i
i=1 ∈ U) }
x
|
{z
}
m

2Aix





T 

 1 + ci + 2bi x  ∈ L



T 
1 − ci − 2bi x

reduces to tractability of a single semi-infinite convex quadratic constraint
xT AT Ax + 2bT x + c ≤ 0
∀(A, b, c) ∈ V
♣ Fact: (∗) can be NP-hard already for a simple polyhedral set V.
⇒ We need to look for tight tractable approximations of (∗).
• What is “an approximation” ?
• How to measure the quality of an approximation?
13
(∗)
Definition. Consider a semi-infinite conic inequality
∀ζ ∈ Z : Aζ x + bζ ∈ K
(C)
with Aζ , bζ affine in ζ, and let Z, 0 ∈ Z, be convex. We embed
(C) into the parametric family of semi-infinite conic inequalities
∀(ζ ∈ ρZ) : Aζ x + bζ ∈ K
(Cρ)
(ρ ≥ 0: uncertainty level), and let Xρ be the feasible set of (Cρ).
A computationally tractable system of conic inequalities (e.g., a
system of explicit LMIs)
Pρx + Qρu + rρ ∈ M
(Sρ)
is a tight within factor ϑ ≥ 1 safe approximation of (Cρ), if
the projection Xρ∗ of the feasible set of (Sρ) onto the space of
x-variables satisfies Xϑρ ⊂ Xρ∗ ⊂ Xρ ∀ρ ≥ 0.
Approximating Semi-Infinite Convex Quadratic Constraint with
Ellipsoidal Uncertainty
Theorem. [Ben-Tal, Nem., Roos ’02] Consider semi-infinite convex
quadratic inequality
xT AT Ax + 2bT x + c ≤ 0

∀ (A, b, c) = (A∗, b∗, c∗) + ρ
L
X
`=1

ζ`(A`, b`, c`) : ζ ∈ Z 
(SC[ρ])
where the perturbation set Z is an intersection of ellipsoids centered
at the origin:
½
¾
T
Z = ζ : ζ Qj ζ ≤ 1, j = 1,
..., N

Qj º 0,


X
j
Qj  0
(SC[ρ]) admits an explicit ϑ-approximation, where ϑ is as follows:
♠ In the case N = 1 of simple ellipsoidal uncertainty, ϑ = 1;
♠ In the case of box uncertainty (N = dim ζ, ζ T Qj ζ = ζj2), ϑ = π2 ;
√
♠ In the general case, ϑ ≤ O(1) ln N . For example,
LN ≤ 100, 000, 000 ⇒ ϑ ≤ 6.36.
21
AARC without fix-recourse
a(ξ)Tx(ξ) ≤ b(ξ) ∀ ξ ∈ Uρ ⇒ sol. set Xρ
Uρ = { ξ0 + W ξ | ||ξ ||2 ≤ ρ }
•
If Uρ = single ellipsoid ⇒ RC is SDP
•
If U =∩ L ellipsoid ⇒ we can build an explicit SDP which
generates an approximation X̂ ρ of the robust feasible set Xρ
(i.e. Xˆ ρ ⊂ X ρ) which is tight up to a factor
θ = O(1) log L
i.e.
•
(∗)
X θρ ⊂ Xˆ ρ ⊂ X ρ
If Uρ is a box then (*) holds with
ρ=π/2
♣ Extending the notion of RC: Globalized Robust Counterpart.
min {t : f (x, ζ) ≤ t, F (x, ζ) ∈ Q} : ζ ∈ Z
t,x
(Unc)
♠ In some applications, it makes sense to modify our attitude to
uncertainty, specifically, to replace the requirement
Full responsibility for the constraints f (x, ζ) ≤ t and F (x, ζ) ∈
Q when ζ ∈ Z and no responsibility whatsoever when
ζ 6∈ Z
with
Full responsibility for the constraints when ζ ∈ Z and
controlled deterioration of the constraints when ζ 6∈ Z.
Globalized Robust Counterpart
Uncertain linear inequality
(1)
a(ξ)Tx ≤ b(ξ)
ξ ∈ U ⊂ ℜk
GRC
(2)
a(ξ)Tx – b(ξ) ≤ α dist(ξ, U) ∀ ξ ∈ ℜk
α > 0.
NOTE α → ∞ then GRC = RC
i.e.
(3)
a(ξ)Tx – b(ξ) ≤ 0
∀ξ∈U
1
♣ Generic application: Affine control of uncertainty-affected Linear Dynamical Systems.
♠ Consider Linear Time-Varying Dynamical system
xt+1 = Atxt + Btut + Rtdt
yt = Ctxt
x0 = z
(S)
• xt: state; • ut: control • yt: output;
• dt: uncertain input; • z: initial state
to be controlled over finite time horizon t = 0, 1, ..., T .
♠ Assume that a “desired behaviour” of the system is given by a system
of convex inclusions
Diw − bi ∈ Qi, i = 1, ..., m
on the state-control trajectory
w = (x0, x1, ..., xT +1, u0, u1, ..., uT ),
and the goal of the control is to minimize a given linear objective f (w).
24
xt+1 = Atxt + Btut + Rtdt
yt = Ctxt
x0 = z
♠ Restricting ourselves with affine output-based control laws
ut = ξt0 +
t
X
τ =0
(S)
Ξtτ yτ ,
(∗)
the problem of interest is
(!) Find an affine control law (∗) which ensures that the resulting statecontrol trajectory w satisfies the system of convex inclusions
Diw − bi ∈ Qi, i = 1, ..., m
and minimizes, under this restriction, a given linear objective f (w).
Dynamics (S) makes w a known function of inputs d = (d0, d1, ..., dT ), the
initial state z and the parameters ξ of the control law (∗):
w = W (ξ; d, z).
Consequently, (!) is the optimization problem
min {f (W (ξ; d, z)) : DiW (ξ; d, z) − bi ∈ Qi, i = 1, ..., m}
ξ
25
(U)








xt+1 = Atxt + Btut + Rtdt
open loop dynamics:  yt = Ctxt




x0 = z
t
control law:
ut = ξt0 + P Ξtτ yτ
τ =0
⇓
w := (u0, ..., uT , x0, ..., xT +1) = W (ξ; d, z)
⇓
min {f (W (ξ; d, z)) : DiW (ξ; d, z) − bi ∈ Qi, i = 1, ..., m}
ξ
(U)
Note: Due to presence of uncertain input trajectory d and possible
uncertainty in the initial state, (U) is an uncertain problem.
Difficulty: While linearity of the dynamics and the control law make
W (ξ; d, z) linear in (d, z), the dependence of W (·, ·) on the parameters
ξ = {ξt0, Ξtτ }0≤τ ≤t≤T of the control law is highly nonlinear
⇒ (U) is not a bi-affine problem, which makes inapplicable the theory
we have developed. In fact, (U) seems to be intractable already when
there is no uncertainty in d, z!
26
Remedy: suitable re-parameterization of affine control laws.
♣ Consider a closed loop system along with its model:
closed loop system:
model:
xt+1 = Atxt + Btut+Rtdt xct+1 = Atxct + Btut
yt = Ctxt
yct = Ctxct
x0 = z
xc0 = 0
ut = Ut(y0, ..., yt)
♠ Observation: We can run the model in an on-line fashion, so that
at time t, before the decision on ut should be made, we have in our
disposal purified outputs
vt = yt − yct.
♠ Fact I [Equivalence]: Every transformation (d, z) 7→ w which can be
obtained from an affine control law based on outputs:
ut = ξt0 +
t
X
τ =0
Ξtτ yτ
(∗)
can be obtained from an affine control law based on purified outputs:
ut = ηt0 +
and vice versa.
28
t
X
τ =0
Htτ vτ
(∗∗)
system:
model:
xt+1 = Atxt + Btut+Rtdt xct+1 = Atxct + Btut
yt = Ctxt
yct = Ctxct
x0 = z
xc0 = 0
control law:
vt = yt − yct
t
ut = ηt0 + P Htτ vτ
(∗∗)
(S)
τ =0
♠ Fact II [bi-affinity]: The state-control trajectory w = W (η; d, z) of (S)
is affine in (d, z) when the parameters η = {ηt0, Htτ }0≤τ ≤t≤T of the control
law (∗∗) are fixed, and is affine in η when (d, z) is fixed.
29
♠ Corollary: With parameterization (∗∗) of affine control laws, the problem
Find an affine control law (∗) which ensures that the resulting state-control
trajectory w satisfies the system of convex inclusions
Diw − bi ∈ Qi, i = 1, ..., m
and minimizes, under this restriction, a given linear objective f (w).
becomes an uncertain bi-affine optimization problem and as such can be processed
via the CRC approach.
In particular, in the case when Qi are one-dimensional, the CRC of the problem
is computationally tractable, provided that the normal range U of (d, z) and the
associated cone L are so. If U, L and the norms used to measure distances are
polyhedral, CRC is just an explicit LP program.
30
Supply chain control – GRC
implementation for control problems
xtj=amount echelon j orders from j-1 at the beginning of
period t
Ytj =inventory level in echelon j at the end of period t
zj =initial inventory level at echelon j
dt =external demand at period t
TL(j) =I(j) +M(j-1) +L(j) the delay between the time an order
is placed and received in echelon j.
TM(j) =I(j+1) +M(j)
the delay between the time an order is placed and shipped 22
from echelon
Supply chain control – GRC
implementation for control problems
Main objective : minimizing cost
Sub objective:
stabilizing the system
Problem Characteristics:
Finite horizon
Multi echelon
Delays
Backlogging
Demand must be satisfied and is uncertain
23
Supply chain control
Eliminating the equalities recursively will give us a LP
problem of the form we discussed.
How do we control this system? What are the
consequences of different types of control?
24
LV control
Lets assume we take the control suggested by Love
[Love,1979] using
target inventory:
Resulting in the LP problem:
25
ILV control
We can further improve this method by making the
reference inventory a decision variable rather than a
constant.
26
GRC control
Applying the GRC to the AARC problem assuming
29
Robust Counterpart (AARC)
ytj = ytj(d, z) affine function
xtj = xtj(d, z)
constraints must hold ∀ d ∈ D, z ∈ Z
CRC A typical constraint is of the form
Fi(d, z) ∈ Ki
(Ki = interval)
Its CRC version being
(∗)
n
m
t =1
j =1
(
dist ( Fi (d , z ), K i ) ≤ ∑ α it dist (dt , Dt ) + ∑ α ij dist z j , Z j
When Dt, Zj are polyhedral (*) can be converted to linear
inequalities.
)
The purified outputs corresponding to the dynamic system
(1) – (3) are here
⎧
t −T M (m )
⎪ z0m −
d z if j = m
∑
⎪
t =1
j ⎪
vt = ⎨
⎪z j
j<m
⎪ 0
⎪⎩
The affine control law is here
x,t , j m T x,t , j l
xt = η0
+ ∑ ∑ ητl
vτ
l =1τ =1
j
where ητxl,t , j = 0
∀τ ≥ t
(non anticipativity)
Example
[Love, 1979], Oscillating demand:
Horizon: n=20
Echelons: m=3
Cost: c=2, p=3,h=1
Initial inventory: z=12
Lead time: L=2
No other delays
30
Inventory Behavior – “amplification of
oscillation”
LV
OFV: 4795
RC
OFV: 1207
ILV
OFV: 3140
AARC
OFV: 1165
GRC
OFV: 1065
31
Example - extended
Assuming demand is uncertain:
Dt=[4,10], Zj=[10,14];
All other data is the same.
50 simulations, uniform distribution:
Same as assumed.
Dt=[2,12], Zj=[8,16];
33
Results
COST\ deviation ratio
Input
Assumed
LV
ILV
RC
AARC
GRC
5128
3310
1263
1131
1081
(597%)
(348%)
(73%)
(62%)
(48%)
Wider than
assumed
5430
3561
1405
1202
1114
(634%)
(380%)
(94%)
(65%)
(53%)
Theoretical
(worst case)
No
bound
No
bound
2137
1410
1628
35
Results – GRC characteristics
1
1
0.9
0.9
0.8
0.8
0.7
0.7
0.6
RC
.
GRC α0
GRC α1
GRC α2
GRC α3
GRC α
0.5
0.4
0.3
0.2
0
0.6
RC
.
GRC α0
GRC α1
GRC α2
GRC α3
GRC α4
0.5
0.4
0.3
0.2
4
0.1
0
probability
probability
Although restricting α worsens the theoretical
objective the common behavior is improved.
0.1
0.2
0.4
0.6
0.8
R
1
1.2
1.4
1.6
0
0
0.2
0.4
0.6
0.8
R
1
1.2
1.4
1.6
38
Probabilistic guaranties via RO
d
(1) f 0 ( y ) + ∑ ξl fl ( y ) ≤ 0
l =1
Assumption
ξ1, ξ2, . . . , ξd independent rv’s
ξ l ∼ Pl ∈ P l
*compact all prob. dist. in Pl has
common support = [−1,1].
Def. A vector y satisfying, for a given 0 < ξ < 1:
(2)
Pr{ f0(y) + Σ ξl fl(y) ≤ 0 } ≥ 1 − ε
provides a safe approximation of (1).
Challenge Find uncertainty set for ξ, U s.t. the RC of (1):
(3)
f0(y) + Σ ξl fl(y) ≤ 0 ∀ ξ ∈ U
is a safe approximation of (1), i.e. satisfies (2).
Theorem
U = B ∩ (M + E )
B = ξ ∈ ℜd ξ ∞ ≤ 1
{
}
(4) where M = {ξ μ − ≤ ξ ≤ μ + , l = 1,K d }
l
l
l
E = {ξ ∑ ξl2 σ l2 ≤ 2 log(1 ε )}
μl− , μl+ and σ l are such that
2
σ
Al ( z ) ≤ max μl− z , μl+ z + l zl2 , ∀l = 1,K d
2
(
)
where Al ( z ) = max log(∫ exp( zs )dPl (s )).
Pl ∈Pl
Also E can be replaced by a scaled
E = {ξ ∑ ξl σ l ≤ 2d log(1 ε ).}
Values of μl+ , σ l are explicitly known for various families Pl,
e.g.
supp(P ) ⊂ [− 1,1]
⎫ μl± = 0
⎬
P unimodal and symmetric⎭σ l = 1 6
supp(P ) ⊂ [− 1,1]⎫ μ − = −1 2 , μ + = 1 2
l
⎬ l
P unimodal ⎭
σ l = 1 24
Moreover, for the LP case (fl(y) affine) the RC of (3), with U as in
the Theorem, is conic quadratic or LP.
CASE I Information on ζ ∼ P
ζ` ’s are independent rv’s, |ζ` | ≤ 1,
E(ζ` ) = 0
Here the uncertainty set is
U Ball = {ζ | kζk2 ≤ Ω} .
The RC of the uncertain linear const. (1) is
v
u L
uX
Ωt [(a` )T x − b` ]2 ≤ b0 − (a0 )T x .
`=1
This conic-quadratic constraint is a safe approximation of the CC for
p
all Ω ≥ 2 log(1/2) i.e. for such Ω
n
o
X
X
ζ` (a` )T x > b0 +
ζ` b` ≤ exp(−Ω2 /2)
P r (a0 )T x +
Discussion What if we ignore the stochastic information and just use
|ζ` | ≤ 1? In this case, the CC coincide with the RC of the linear eq.
with uncertainty
U Box = {ζ | |ζi | ≤ 1,
which is here
Hence
` = 1, . . . , L}
X
(a` )T x − b` ≤ b0 − (ao )T x
x feasible for (3) ⇒ CC is feasible with prob. 1.
When using the stochastic information, the RC is
qX
2
Ω
[(a` )T x − b` ]
≤ b0 − (a0 )T x
(3)
(4)
(5)
which corresponds to U Ball , and we have
x feasible for (4) ⇒ CC is feasible with prob. 1 − exp(−Ω2 /2)
(For Ω = 7.44 1 − exp(−Ω2 /2) = 1 − 10−12 so (4) and (6) are
indistinguishable!)
(6)
But, for large L
Vol(U Box )
−→ ∞
Vol(U Ball )
superexponentially
(ratio is > 1 starting with L = 237).
For small L, we could use
L
U = U Box ∩ U Ball = ζ ∈ IR | kζk∞ ≤ 1, kζk2 ≤ Ω
Here the RC is
and we have

 P |z | + ΩpP w2 ≤ b0 − (a0 )T x
`
`
 z` + w` = b` = (a` )T x
If x is a component of a feasible
solution (x, z, w) of (7)
=⇒
(7)
CC is feasible with
2
prob. 1 − exp(−Ω /2)
(8)
Discussion With U = U Box ∩ U Ball , we get always (for all L) less
conservative RC (incomparable so for Ω > 7 compared to U Box ) and
yet guarantee the CC with prob. essen. 1.
Striking phenomenon Consider the special case of P in Case I:
P r(ζi = ±1) = 1/2 .
Note that here
kζk22 = L ;
hence, if L > Ω2 , the set U does not contain even a single
realization of ζ, and yet the CC holds with high probability.
Conclusion The “immunization power” of the RC (7) cannot be
explained by the fact that the underlying perturbation set U contains
“nearly all” realizations of the random perturbation vector.