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∈ 是独立的，对称的，有界的随机变量（但分 布未知） ， 在 中取值。 ~ ij a Ji j∈ aij ^ aij ij ^ aij · （价格向量C的不确定性）： ， j C 0 J j∈ 在 ] , , , 0 上是对称分布的 · 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 +3个网络流问题，其中=max{ ： （i，j）∈A}。 _ θ _ θ d u ij ij 11 经验结论 11.1 最短路 幻灯片35 12 结论 幻灯片36 · MIP相应的鲁棒问题仍是一个MIP，具有可比的规模。 · 方法允许保护水平的调整的灵活性，以违反约束的概率界的形式。 幻灯片37 · 对价格不确定的多项式可解的0-1优化问题，相应的鲁棒 问题也是多项式可解的。 幻灯片38 · 将鲁棒网络流看成一系列不现实的网络流问题后式可解的。 · 没有维数烦恼的随机优化问题的鲁棒优化是很容易处理的。 11
标签: 鲁棒优化
