日志
鲁棒优化
|
15.093 最优化方法
讲义8：鲁棒优化
1
1 论文 幻灯片1
· B 和 Sim，The Priceof Robustness. Operations Research(运筹学),2003
· B 和 Sim，Robust Discrete optimization, Mathematical Programming(数学规
划)
2003
2 结构 幻灯片2
· 起因
· 数据不确定性
· 鲁棒混合整数规则
· 鲁棒0-1规则
· 鲁棒近似算法
· 鲁棒网络流
· 经验结论
· 概括与总结论
3 起因 幻灯片3
· 传统的优化模型都假设输入的数据是精确的切等于某些不真实的值。这种方法没
有考虑到模型的质量及可行性受到的数据不确定性的影响。
· 我们能否设计一种对数据不确定免疫的解法，使得它们是健壮的？
幻灯片4
· Ben-Tal 和 Nemirovski(2000)
线性规划在现实世界的应用（网络试验，图书馆）中，没有人能够忽视一种可能性，
那就是：数据的一个小的不确定性可能使得最优解在实际应用中完全毫无意义。
2
3.1 文献
· 椭圆不确定性;Robust convex optimization Ben-Tal 和Nemirovski 幻灯片5
（1997），El-Ghaoui.al(1996)
· Flexible adjudtment ofconservativision
· Nonlinearconvex models (非线性凸模型)
· 不能推广到离散优化。
4 目标
发展一种致力于数据不确定性的优化问题的解法： 幻灯片6
· 允许控制解的保护程度。
· 在实际和理论上的计算都是易处理的。
5 数据不确定性
幻灯片7
,...,k Z, i x
u x l
b o Ax subject t
c'x
i
1
minimize
= ∈
≤ ≤
≤
WLOG数据不确定性只影响A和C，不影响向量b 幻灯片8
· （矩阵A的不确定性）：
ij a ， Ji j∈ 是独立的，对称的，有界的随机变量（但分
布未知） ， 在[ - ,a+ ]中取值。
~
ij
a Ji j∈ aij
^
aij
ij
^
aij
· （价格向量C的不确定性）： ， j C 0
J j∈ 在 ] , [
j j j d C C + 中取值。
6 鲁棒混合整数优化（MIP）
· 考虑一个整数 m i J Ti i
,......, 1 , 0 ], , 0 [ = ∈ 幻灯片
9
· 调整适当方法的健壮性使得解的保护水平会受到影响。 i T
·直观地讲，所有的ij a , 不可能都改变，我们需要使得 J j∈ ij a 都允许变化时所
有的情都在 之上。 i T
·自然将约束自己的行为，因此只有系数的一个子集发生改变反过来影响解。
3
·我们将保证：若自然发生这种改变，那么鲁棒解也将绝对可行。即使比Ti改变的更
多，鲁棒解也将在一个高概率下保持可行。
6.1 问题 幻灯片11
{}
{}
k 1,..., i ,
ˆ max o subject t
max minimize
0
0 0 0 0
= ∀ ∈
≤ ≤
∀ ≤
⎭
⎬
⎫
⎩
⎨
⎧
+
⎭
⎬
⎫
⎩
⎨
⎧
+
∑∑
∑
∈
≤ ⊆
∈
≤ ⊆
Z x
u x l
i , b x a x a
x d c'x
i
i
jSj
j ij
Γ S , J |S S
j ij
S j
j j
Γ S , J |S S
i
t i i i i
t
6.2 定理 幻灯片12
k i Z x
j u x l
y x y
J j i z y P
J ,j i y a p z
J j y d p z
i b p Γ z x a to subject
p Γ z c'x
i
j j j
j j j
i i j ij
i j ij ij i
j j j
J j
i ij i i
j
j ij
j J j
,..., 1
j
, 0 , ,
0 ˆ
minimize
0 0 0
0 0 0
0
0
= ∈
∀ ≤ ≤ −
∀ ≤ ≤ −
∈ ∀ ≥
∈ ≠ ∀ ≥ +
∈ ∀ ≥ +
∀ ≤ + +
∑ + +
∑ ∑
∈
∈
6.3 证明 幻灯片13
给定向量X
*
，我们定义：
{}⎭
⎬
⎫
⎩
⎨
⎧
= ∑
∈
Γ = ⊆
i
i i i i i
S j
ij ij
S J S S
i
x a x
*
, |
*
ˆ max ) ( β
这就等价于：
i ij
i
J j
ij
ij
j j
ij ij i
J i,j z
Γ z s.t.
z x a x
i
i
∈ ∀ ≤ ≤
≤
=
∑
∑
∈
∈
1 0
ˆ max ) (
* *
β
对偶： 幻灯片14
4
i z
J j p
J j x a p s.t. z
z p x
i
i ij
i
*
j ij ij i
J j
i i ij i
i
∀ ≥
∈ ∀ ≥
∈ ∀ ≥ +
Γ + = ∑
∈
0
0
min ) (
*
β
i
J Γ
5 5
10 83565
100 24263
200 33899
表1： 选取 Ti作为 i T i
J 的一个系数使得违反约束的概率小于1%。
6.4 规模 幻灯片15
· 原问题有n个变量，m个约束。
· 鲁棒问题有 个变量，其中l= 1 2 + +n m ∑=
m
i
Ji
0
| | 是不确定的系数的个数字且
个约束。 L n m + + 2
6.5 概率保证
6.5.1 定理2 幻灯片16
设X
*
是鲁棒 MIP的一个最优解
(a) 若A受约束与数据不确定性U：
⎣⎦ ⎣⎦ ⎭
⎬
⎫
⎩
⎨
⎧
⎟
⎠
⎞
⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛
− ≤
⎟
⎠
⎞
⎜
⎝
⎛
> ∑∑ ∑
=+=
n
i
n
i
n
j
i j ij
l
n
u
l
n
u b x a
νν1
*
) 1 (
2
1 ~
Pr
n=|Ji |，v=
2
n Ti+
，且u=v-|v|；，界是紧的
（b）当n→∞
⎣⎦ ⎣⎦
⎟
⎠
⎞
⎜
⎝
⎛ − Γ
Φ −
⎭
⎬
⎫
⎩
⎨
⎧
⎟
⎠
⎞
⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛
− ∑∑ =+= n l
n
u
l
n
u
i
n
i
n
i
n
1
1 ~ ) 1 (
2
1
1 νν
幻灯片17
幻灯片18
7 经验结论
7.1Knapsack 问题
幻灯片19
5
{}n
N i
i i
N i
i i
, x
b x w
x c
1 0
o subject t
maximize
∈
≤ ∑
∑
∈
∈
· 是独立分布且在[Wi-δi, Wi+δi]上是对称分布的
· C不受数据不确定性的限制
7.1.1 数据
· |N|=200，不=4000， 幻灯片20
· Wi从{20，21，……，29}中随机选取
· 从{16，17，……，77}中随机选取 i C
6
· i δ=0.1 Wi
i W
7.1.2 结论 幻灯片21
8 鲁棒 0-1优化 幻灯片22
· 不现实的组合优化：
{}n
, X x
c'x
1 0 o subject t
minimize
⊂ ∈
· 对应的鲁棒：
{}
X x
x d c'x Z
S j
j j
Γ S J, S|S
∈
+ = ∑
∈
= ⊆
o subject t
max minimize
*
·
n d d WLOGd Λ Λ 2 1 >
8.1 评论 幻灯片23
· 例子：最短路.最小生成树、最小指派、旅行商、交通工具路径选择及拟阵交集问题。
· 鲁棒性问题的其它解法很难，其不确定性的形式
( )
X x
x x,c c
' '
∈ o subject t
max minimize
2 1
对于最短路问题时NP-难的。
8.2 方法
幻灯片24
原：
{}
∑
∑
≤
∀ ≤ ≤
+ =
∈
= ⊆ ∈
j
j
j
S j
j j
Γ S J, S|S X x
Γ uj
j u s.t.
u x d c'x Z
1 0
max min
*
对偶：
0 ,
min min
j
*
≥
∀ ≥ +
+ Γ + = ∑ ∈
θ
θ
θ
j
j j j
i
X x
y
j x d s.t. y
y c'x Z
7
8.3 算法A
· 解： 幻灯片25
( ) ( ) ∑ − + + Γ =
≥ ∈
j
j j j j
X x
x d x c Z 0 , max min
0 ,
*
θ θ
θ
· 因为X∈{0,1}
n
( ) ( )
() ()j
j
j j
X x
j j j j
x d c Z
x d x d
∑ − + + Γ =
− = −
≥ ∈
0 , max min
0 , max 0 , max
0 ,
*
θ θ
θ θ
θ
· 幻灯片26
·d1≥d2≥…≥dn≥dn+1=0
·对 ≥θ≥ d1 dn 1 +
()
()
() ∑∑
∑ ∑
∑ ∑
== ∈ + =
= =
= =
≥ ∈
− + + Γ =
= − + + Γ
= − + + Γ
+
n
j
l
j
j l j j j
X x
l
n l
l
n
j
j l j
n
j
j j l
l
j
j j
n
j
j j
d d X x
x d d x c d Z
Z x d d x c d
x d x c
l l
11 1 ,..., 1
*
1 1
1 1
,
min min
min
1
θ θ
θ
8.4 定理3 幻灯片27
· 算法A正确地了解了鲁棒 0-1 优化问题。
· 它至多需要求|J|+1个不现实问题的解。因此，若不实现问题时多项式时间内可
解的，则鲁棒 0-1优化也是多项式可解的。
· 鲁棒最小生成树，最小指派，最小匹配，最短路和拟阵交集问题都是多项式可解
的。
9 经验结果
9.1 鲁棒分类： 幻灯片28
8
{}n
N i
i
N i
i i
, x
k x
x c
1 0
o subject t
minimize
∈
= ∑
∑
∈
∈
Γ `
) (Γ Z ) ( % Γ changeinZ ) (Γ σ ) ( % Γ σ changein
0 8822 0% 501.0 0.0%
10 8827 0.056% 493.1 -1.6%
20 8923 1.145% 471.9 -5.8%
30 9059 2.686% 454.3 -9.3
40 9627 9.125% 396.3 -20.9%
50 10049 13.91% 371.6 -25.8%
60 10146 15.00% 365.7 -27.0%
70 10355 17.38% 352.9 -29.6%-80 10619 20.37% 342.5 -31.6%
100 10619 20.37% 340.1 -32.1%
{}
{}n
N i
i
S j
j j
Γ S J, S|S
x
k x
x d c'x Z
1 , 0
o subject t
max minimize ) (
*
∈
=
+ = Γ
∑
∑
∈
∈
= ∈
9.1.1 数据 幻灯片29
· 200 = N
· 100 = k
· ] 200 , 50 [ ~ ]; 200 , 50 [ ~ U d U C j j
· 对于检测坚固性，生成的例子使得每个价格分量在概率P=0.2下独立的偏差与不
现实值 到
j C j j d C +
9.1.2 结论 幻灯片30
10 鲁棒 网络流
· 不真实的情况 幻灯片31
9
()
() {}( ) {}
()A u x
Ν i b x x
x c
ij ij
i
A j,i j:
ij
A i,j j:
ij
A i,j
ij ij
∈ ∀ ≤ ≤
∈ ∀ = − ∑ ∑
∑
∈ ∈
∈
j i, 0
s.t.
min
· X为可行解流的集合
· 鲁棒
{}()
X x
x d c'x Z
S i,j
ij ij
Γ S A, S|S
∈
+ = ∑
∈
≤ ⊆
o subject t
max min
*
10.1 转化 幻灯片32
· ( ) θ
θ
Z Z
0
*
min
≥
=
( )
()
X x
A p
A x d p
ij
ij ij ij
∈
∈ ∀ ≥
∈ ∀ − ≥
j i, 0
j i, o subject t θ
· 等价于
()
()
X x
d
x d x c Z
A j i ij
ij ij
∈
⎟
⎠
⎞
⎜
⎝
⎛
− + + Γ = ∑
∈
o subject t
0 , max ' min
,
θ
θ θ
10.2 网络公式转化 幻灯片33
定理： 对于固定的θ，我们可以把鲁棒问题看成网络流问题来求解。
10.3 复杂性 幻灯片34
10
2 1 2 1
) ( ) ( θ θ θ θ − ≤ − A Z Z
· ) (θ z 是凸函数且对所有 0 ,
2 1 > θ θ 有：
()
∑
∈
+ =
S j i
ij ij
x d x c Z
,
ˆ max ˆ '
ˆ
· 对任意固定的T≤|A|和任意ε＞0，我们能找到一个解 ，其鲁棒目标值 X x∈
^
使得
( )
* *
1
ˆ Z Z Z ε + ≤ ≤
通过求解2[log2（|A| /ε）]+3个网络流问题，其中=max{ ：
（i，j）∈A}。
_
θ
_
θ d u ij ij
11 经验结论
11.1 最短路 幻灯片35
12 结论 幻灯片36
· MIP相应的鲁棒问题仍是一个MIP，具有可比的规模。
· 方法允许保护水平的调整的灵活性，以违反约束的概率界的形式。 幻灯片37
· 对价格不确定的多项式可解的0-1优化问题，相应的鲁棒
问题也是多项式可解的。 幻灯片38
· 将鲁棒网络流看成一系列不现实的网络流问题后式可解的。
· 没有维数烦恼的随机优化问题的鲁棒优化是很容易处理的。
11
