Lecture # 4

Stochastic Programming
Chance constraints
LNMB ’14, Lecture # 4
Reformulation of LP with random parameters min {cx : T (!)x
where X0 = {x 2
Rn+
x2X0
: Ax = b}
Chance constrained model: for reliability level ↵ 2 [0, 1]
Chance constraints
Introduction
Properties: convexity
Integrated CC
relation to Recourse Models
min {cx : Pr{T (!)x
x2X0
h(!)}
(Joint CC)
↵}
or, for ↵i 2 [0, 1], i = 1, . . . , m
min {cx : Pr{Ti(!)x
x2X0
hi(!)}
↵i 8i}
(Individual/Separate CC)
x 2 X0 is feasible in
JCC if p(x) := Pr{T (!)x h(!)} ↵
SCC if pi(x) := Pr{Ti(!)x hi(!)} ↵i 8i
Slides on http://tinyurl.com/SPLNMB
1
CC model only useful for inequalities: for equalities T (!)x = h(!)
if ! continuous: pi(x) = 0 for all x
if ! discrete: pi(x) ⇡ 0 for all x
Could use instead, with ai < 0 < bi
Pr{ai  Ti(!)x
hi(!)  bi}
JCC: for ↵ 2 [0, 1],
↵i
! C(↵) :=
↵ik ,
m
\
i=1
Ci(↵i),
↵}
↵i }
↵ 2 [0, 1]m
Upper level sets of reliability function p/pi
Would like C(↵) to be
non-empty
closed ! existence of optimal solutions
convex ! solvability, algorithms
Quantitative risk in CC: use several CCs to model risk ⇠ shortage level
dik }
C(↵) := {x 2 Rn : p(x)
SCC: for ↵i 2 [0, 1], Ci(↵i) := {x 2 Rn : pi(x)
In CC risk:= Pr{T x 6 h} is qualitative: ‘Size of shortage irrelevant’
Good or bad? Depends on application
hi(!)
2
Consider induced feasibility sets:
but won’t . . .
Pr{Ti(!)x
h(!)}
k = 1, . . . , K
where 0 = di1 < di2 < . . . < diK
↵i1 < ↵i2 < . . . < ↵iK
‘Larger shortages are less acceptable’ ! Integrated CC: later
(Recall examples Lecture 1)
3
4
Theorem 5.3.6 in LN:
Convexity of C(↵)
p is upper semi-continuous
! C(↵) closed for all ↵ 2 [0, 1] and all distributions of !
x 2 C(↵) if T (!)x
C : [0, 1] 7! Rn non-increasing: ↵1 > ↵2 ) C(↵1) ✓ C(↵2)
h(!) for ‘enough’ realizations of ! :
if 9K ⇢ ⌦ with Pr{! 2 K}
↵ such that
n
x 2 S(!) := {x 2 R : T (!)x
Extreme cases:
C(0) = {x 2 Rn : p(x) 0} = Rn
includes ‘extremely risky set’{x 2 Rn : p(x) = 0}
h(!)}
8!2K
K not unique in general:
e.g. with ⌦ discrete and K↵ := K ⇢ ⌦ : Pr{! 2 K}
[ \
C(↵) =
S(!)
C(1) is ‘extremely safe set’ {x 2 Rn : p(x) = 1}
C(↵) is non-empty for all ↵ i↵ C(1) 6= ;
↵
K2K↵ !2K
|
{z }
convex
= ‘union of convex sets’
=) C(↵) in general non-convex.
Conditions such that C(↵) is convex?
5
C(↵) = {x 2 Rn : p(x)
() p is quasi-concave: for any x := (1
p(x )
(i) If ! 2 R, T is 1 ⇥ n vector:
then cdf F is non-decreasing on R ) quasi-concave
SCC with T (!) = T fixed ! C(↵) convex
Reduced form:
↵} convex 8↵ 2 [0, 1]
() all upper level sets of p are convex
)x0 + x1,
2 [0, 1]
min p(x0), p(x1)
C(↵) = x 2 Rn : T x
(with F
In general, p is not quasi-concave (examples) ! study special cases
1
F
1
(↵) ,
↵ 2 [0, 1]
(↵) the ↵-th quantile of ! )
! linear constraint
(ii) If log F is concave (F is log-concave)
Assume
T (!) = T fixed
h(!) = ! 2 Rr with cdf F
! p(x) = Pr{T x !} = F (T x)
When is cdf F quasi-concave?
6
log F (x )
log F (x0) + (1
) log F (x1)
log min{F (x0), F (x1)}
(g quasi-concave ) g(T x) quasi-concave in x)
7
) F (x )
min{F (x0), F (x1)}
since log strictly increasing (on R+, with log 0 =
Example: multivariate normal
1)
8
Consider case with T (!) random: only positive results for SCC
! T (!) is 1 ⇥ n vector, h(!) 2 R
(iii) If ! 2 Rm has a pdf f such that
log f is concave OR
f 1/m is convex
(a) Only 1 element of T (!) random: h(!) = h fixed, T (!) = (!, t2)
! 2 R with cdf F , left-continuous cdf Fˆ (s) := Pr{! < s}
p(x) = Pr{!x1 + t2x2 h}
(Notation: z := t2x2)
8
>
Pr{!  hx1z } = F ( hx1z ),
x1 < 0
>
<
Pr{z h} 2 {0, 1},
x1 = 0
=
>
>
: Pr{! h z } = 1 Fˆ ( h z ), x > 0
1
x1
x1
Examples:
uniform on ⌦ ⇢ Rm, ⌦ convex
multivariate normal
, 2, t, . . .
See e.g. [Pr´ekopa 1995]
Hence, for ↵ 2 (0, 1]
Conclusion for T (!) = T fixed, h(!) = ! 2 Rr :
C(↵), ↵ 2 [0, 1], convex in many practical situations
SCC: always
JCC: depends on distribution
x 2 Rn : x1 < 0, F
C(↵) =
{x : x1 = 0, z
1
(↵)x1 + z h [
n
h} [ x : x1 > 0, Fˆ 1(1
↵)x1 + z
is a union of convex sets . . . Convex?
9
h
o
10
(b) Normal distribution
C(↵) =
x 2 Rn : x1 < 0, F
{x : x1 = 0, z
is convex i↵
F
1
(↵) 
Fˆ
1
(↵)x1 + z h [
n
h} [ x : x1 > 0, Fˆ 1(1
1
(1
↵) () ↵
↵)x1 + z
h
o
1/2
T (!) = (!1, . . . , !n) ⇠ N (µ, V ), h(!) = h fixed
Chance constraint: Pr{!x
h}
↵ with x 2 Rn
Normalize: !x ⇠ N (µx, 2(x)) with
!x µx
!
⇠ N (0, 1), cdf
(x)
2
(x) = x0V x (assume > 0)
Reduced form
C(↵) := {x 2 Rn : Pr{!x
=
x 2 Rn : µx
C(↵) convex if ↵
11
1/2 ()
h}
↵}
h+
1
1
0) since (x) is convex (!)
(↵)
(↵) (x)
12
(c) Discrete distributions
Also h random: T (!), h(!) = (!1, . . . , !n+1) ⇠ Nn+1(⌫, U )
Use
n
X
!i xi
i=1
!n+1 ()
n+1
X
!i xi
0, xn+1 =
1
⌦ = {! , . . . , ! } with probabilities pk , ! k 7! (T k , hk )
Define
1
Sk := S(! k ) = x 2 Rn : T k x
i=1
and apply previous result !
x 2 Rn+1 : ⌫x
C(↵) =
=
(
x 2 Rn :
n
X
1
0+
⌫ i xi
(↵) (x) \ x 2 Rn+1 : xn+1 =
⌫n+1 +
1
(↵) (x)
i=1
)
hk
Then
1
C(↵) =
[ \
where
Sk
N↵ :=
I2N↵ k2I
(
I ⇢ {1, . . . , K} :
X
pk
k2I
↵
)
C(↵) is union of convex polyhedra: non-convex in general . . .
p
with (x) = (x, 1)0U (x, 1)
C(↵) is convex if ↵
(JCC)
K
Fix ↵. If there exists a dominating index set I↵ 2 N↵
I↵ ⇢ I for all I 2 N↵
\
T
T
then C(↵) =
Sk is convex (since k2I Sk ⇢ k2I↵ Sk for all I 2 N↵)
1/2
Note: Sufficient, not necessary. See Exercise C3.
k2I↵
13
14
Equivalent MIP formulation for JCC, ! discrete
Consider relaxation of T k x
Example: T (!) = ( !1, !2),
8 1
< ! = (3, 0)
! 2 = (0, 3)
! = (!1, !2) =
: 3
! = (1, 1)
h(!) =
1
T kx + M
w.p. 1/7
w.p. 2/7
w.p. 4/7
pk
MIP equivalent of JCC
min cx : T k x + M
x2X0
; {1} {2} {1, 2} {3} {1, 3} {2, 3} {1, 2, 3}
0
1
7
2
7
k
2 {0, 1}
⇢
0, x 2 Sk
Interpretation: indicator k =
1, x 2
6 Sk
P
k
!
pk = 1 p(x)
Dominating index sets:
↵=0 !;
↵ 2 (3/7, 4/7] ! {3}
X
hk
with ‘big’ M 2 Rm and
Constraint !1x1 + !2x2  1
I
k
hk
3
7
4
7
5
7
6
7
K
X
k=1
k
pk
k
k
1
hk , k = 1, . . . , K
↵
(?)
2 {0, 1}, k = 1, . . . , K
1
Observe: Not large-scale equivalent of any recourse model due to (?)
k2I
15
16
Variant of CC equivalent to recourse model
min cx+q0 Pr{T (!)x 6
Integrated Chance Constraints
h(!)}
x2X0
Motivation: CC modeling quantitative risk
! second-stage problem
min q0 : M + T k x
hk ,
Convenient: Model risk instead of reliability:
↵ 2 [0, 1] is maximum risk level (was 1 ↵ before)
C(↵) := {x 2 Rn : 1 p(x)  ↵}
2 {0, 1} =: v(x, ! k )
corresponding to large-scale MIP
min
s.t.
cx + p1 · q0 1 + . . . + pK · q0
Ax
T 1x +
M 1
..
...
T Kx
...
+
M
k
x 0,
2 {0, 1}, k = 1, . . . , K
Mixed-integer recourse model
K
Notation: ⌘i(x, !) := Ti(!)x
=
K
[Klein Haneveld ’86]
b
h1
..
hK
! i-th constraint is ⌘i(x, !)
hi(!)
0.
First apply to SCC: drop index i
Quantitative risk & CC: define CC for several shortage levels, e.g.
Pr{⌘(x, !) <
dk }  ↵ k ,
k = 1, . . . , K
where 0 = d1 < d2 < . . . < dK and ↵1 > ↵2 > . . . > ↵K
(later)
! ‘Larger shortages are less acceptable’
17
18
Idea: CC for every shortage level t 2 ( 1, 0], aggregate !
Z 0
Z 0
Pr{⌘(x, !) < t} dt 
↵(t) dt =:
1
1
called Integrated CC
Looks familiar...
See http://stoprog.org
19
20
Idea: CC for every shortage level t 2 ( 1, 0], aggregate !
Z 0
Z 0
Pr{⌘(x, !) < t} dt 
↵(t) dt =:
1
Properties regular CC and ICC follow from loss-functions
⇢
⇥
⇤
1, z < 0
Pr{⌘(x, !) < 0} = E! l1(⌘(x, !)) with l1(z) =
= sgn(z)
0, z 0
1
called Integrated CC
whereas
Looks familiar... Indeed, recall from SR
Z z
⇥
⇤
H(z) := E⇠ (⇠ z) =
Pr{⇠ < t} dt
⇥
⇤
⇥
⇤
E! ⌘(x, !) = E! l2(⌘(x, !)) with l2(z) =
1
one-dimensional expected shortage function
For fixed x, ⌘(x, !) is a random variable
Z 0
⇥
Pr{⌘(x, !) < t} dt = E⌘(x,!) (⌘(x, !)
1
0)
⇤
Compare to traditional CC !
0,
z, z < 0
= (z)
z 0
l2 is
continuous
convex
strictly decreasing on ( 1, 0)
⇥
⇤
= E! ⌘(x, !)
is convex ! ICC set {x : E! [⌘(x, !) ]  } convex, 8 F! and
⇢
l1 is not
2R
20
Feasibility sets: for ↵ 2 [0, 1] and
n
2 [0, 1)
C0(↵) :=
x 2 R : Pr{⌘(x, !) < 0}  ↵
C1( ) :=
⇥
⇤
x 2 Rn : E! ⌘(x, !) 
Consider extreme values ↵ and
Extremely risky sets: ↵ = 1 and
C0(1) = C1(1) = R
Both ↵ and are RISK parameters
↵ is maximal probability of shortage, scale-free
is maximal mean shortage, not scale-free
! hard to specify (cf. recourse)
=1
n
Extremely safe sets: ↵ = 0 and = 0
n
o
C0(0) = C1(0) = x 2 Rn : Pr{⌘(x, !) < 0} = 0
Alternative: use bound for E! [⌘(x, !) ] ⇠ distribution ⌘(x, !), e.g.
⇥
⇤
⇥
⇤
⇥
⇤
E! ⌘(x, !) + E! ⌘(x, !)+ = E! |⌘(x, !)|
Both
convex
often empty
x 2 Ci(0) ! x very expensive
! for ↵ 2 [0, 1]
n
⇥
⇤
⇥
⇤o
C2(↵) := x 2 Rn : E! ⌘(x, !)  ↵ · E! |⌘(x, !)|
C2 is closed, convex for ↵  1/2, . . .
21
(⌘(x, !)
0 for all ! 2 ⌦)
For non-extreme ↵ and , C0 and C1 often quite di↵erent . . .
(details: see LN)
22
23
Example 1: !x
Pr{!x < 1} =
1, i.e. ⌘(x, !) = !x
⇢
1,
|x| < 1
1/2, |x| 1
C0(↵) is empty for relevant ↵
C0(↵) non-convex otherwise (↵ 6= 1)
⇥
E! (!x
1)
⇤
1
= ( x
2
1, with ! ⇠ U { 1, 1}
8
>
↵ 2 [0, 1/2)
< ;,
{x : |x| 1}, ↵ 2 [1/2, 1)
C0(↵) =
>
: R,
↵=1
1
1) + (x
2
C0(↵) =
For all
1
1) = (|x|
2
1) + 1
Reduced form (. . . ): C1( ) = x 2 R : |x|  2 + 1 ,
8
< {x : 2x1
: {x : 2x
1
x2  0, 2x2
0
0
8
>
<
C1( ) is
closed, convex
smoothly increasing with
For all 2 [0, 1), C1( ) is
closed, convex
smoothly increasing with : applications!
x1  0} ,
x2  0} [ {x : 2x2
2x1 x2  2
C1( ) = x : 2x2 x1  2
>
:
x1 + x2  2
+
0, ! ⇠ U {( 2, 1), (1, 2)}
Example 2: ⌘(x, !) = !1x1 + !2x2
↵ 2 [0, 1/2) ⇠ ↵ = 0
x1  0} , ↵ 2 [1/2, 1)
9
>
=
>
;
24
Consider the extremely risky set
ICC for Joint CC
(see Figure)
R := {x 2 Rn : Pr{⌘(x, !) < 0} = 1}
Obviously, C0(↵) \ R = ; for all ↵ < 1
C1( ) \ R may be non-empty, even for small
25
(x: mean shortage is small)
Extreme case: X0 = {x 0 : Ax = b} ⇢ R
CC is infeasible ! infinite costs
ICC is feasible ! finite (small!) costs
(JICC)
Feasibility set for JCC
8
8
9
9
<
< ⌘1(x, !)
=
=
.
6 0
C0(↵) =
x 2 Rn : Pr
↵
:
:
;
;
⌘m(x, !)
n
h
i
o
=
x 2 Rn : E! sgn max ⌘i(x, !)  ↵
i
SCC ! ICC: drop sgn(·)
Analogous: feasible set JICC
n
h
i
o
n
C1( ) := x 2 R : E! max ⌘i(x, !) 
,
2 [0, 1)
Examples suggest ICC have nice properties
i
Theorem 5.5.6: C1( ) is
closed, convex
non-empty for
0 := minx2Rn E! [⌘(x, !) ]
smoothly increasing with (. . . )
C1( ) is convex
for all distributions of !
for all
0
Computations / reduced form: C0(↵) easy ! C1( ) easy
Again, much nicer than C0(↵)
26
27
ICC: reduced forms
Hence
Consider feasible set of ICC for SCC
⇥
⇤
C( ) := x 2 Rn : E! ⌘(x, !) 
C( ) :=
=
Nice interpretation & properties
Computations: need reduced form
(see LN for e.g. ! ⇠ N (µ,
s
2
))
=
s
Restrict to finite discrete distribution: Pr{! = ! } = p , s 2 S
X
⇥
⇤
+
E! ⌘(x, !) =
ps⌘(x, ! s)
X
ps⌘(x, ! s),
K ?(x) = {k 2 S :
s2K ? (x)
= max
K⇢S
X
k
k
=
pk ⌘(x, ! k ) > 0}
\
\
K⇢S
(
(
x 2 Rn :
n
x2R :
k2K
X
pk ⌘(x, ! k ) 
k2K
X
p
k
h
k2K
k
)
)
k
T x 
with (hs, T s) := h(! s), T (! s) , s 2 S
(Why?)
p ⌘(x, ! )
K⇢S
K⇢S
s2S
=
⇥
⇤
x 2 Rn : E! ⌘(x, !) 
(
)
X
x 2 Rn : max
pk ⌘(x, ! k ) 
Description of polyhedral set C( ) using 2|S|
k2K
1 linear constraints
28
Alternative ICC: for ↵  1/2
n
⇥
x 2 R : E! ⌘(x, !)
(
C2(↵) :=
\
=
K⇢S
with (⌧, µ) = E!
⇥
x 2 Rn : (1
T (!), h(!)
⇤
2↵)
⇤
⇥
 ↵ E! ⌘(x, !)
X
pk hk
k2K
Conclusion: ICC model equivalent to LP
⇤
T k x  ↵(⌧ x
Reduced form for JICC:
n
h
i
o
D( ) :=
x 2 Rn : E! max ⌘i(x, !) 
µ)
)
\ \
K⇢S j2I K
(
x 2 Rn :
X
k2K
pk hkjk
Tjkk x 
Alternative LP representation of ICC (individual):
s2S
ys
)
0,
s2S
only |S| + 1 constraints and |S| additional variables
Observe: LP-relaxation of MIP formulation SCC
with I K := j = (jk , k 2 K) : jk 2 {1, . . . , m}, k 2 K
uses (m + 1)|S|
However, for realistic |S|, LP is huge !!!
T sx + y s
hs , s 2 S
X
ps y s 
i
=
29
(Verify!)
First LP representation ! special purpose algorithm
1 linear inequalities
30
(next time)
31
ICC for JCC: for 2 [0, 1)
n
h
min cx : E! max Ti(!)x
ICC and Recourse Models
ICC is missing link between CC and RM
feasible if
ICC and Simple Recourse: risk ⇠ mean shortage (surplus)
min cx + Q (x) ,
x2X0
i=1
hi(!)
Q (x) =
In canonical form:

Q (x) = E! min qy : W y = h(!)
)
y 0
with
✓
is SR model
KKT ! mathematical equivalence, NOT practical
q
W
◆
=
✓
0
e
I
i

o
0
x2X0
x2X0
i
sufficiently large
Lagrangian problem: for
ICC model for SCC: for sufficiently large
n
h
i
o
min cx : E! Ti(!)x hi(!)
 i, i = 1, . . . , m
Lagrangian problem: for
0
(
m
h
X
min c(x) +
Ti(!)x
i · E!
i
x2X0
hi(!)
◆
,
h
· E! max Ti(!)x
i
hi(!)
i
T (!)x
e = (1, . . . , 1)0 2 Rm
is Complete & Sufficiently Expensive
32
Next time: algorithms for
SCC and JCC
ICC
Spin-o↵: SR with random T (!)
Exercise C4 in Appendix F: relation SCC and JCC
34
33

Download Report