Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls
Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls
复制标题
DOI：
10.1287/opre.2017.1698
复制
发表时间：
2018-05-01
影响因子：
2.7
通讯作者：
Kuhn, Daniel
中科院分区：
文献类型：
--
作者：
Hanasusanto, Grani A.;Kuhn, Daniel
自适应鲁棒优化问题通常通过将自适应决策限制在简单的参数决策规则内来近似求解。然而，相应的近似误差可能很大。在本文中，我们表明两阶段鲁棒和分布式鲁棒线性规划通常可精确地重新表述为与问题维度呈多项式规模的锥规划。具体而言，当模糊集构成以离散分布为中心的2 - 瓦瑟斯坦球时，分布式鲁棒线性规划等价于一个余正规划（如果问题具有完全追索权），或者可以通过一系列余正规划任意紧密地逼近（如果问题具有足够昂贵的追索权）。这些结果直接扩展到经典的鲁棒设置，并基于余正锥的半定逼近激发了两阶段问题的强可处理逼近。我们还证明，当模糊集构成以离散分布为中心的1 - 瓦瑟斯坦球且没有支撑约束时，两阶段分布式鲁棒优化问题等价于一个可处理的线性规划。
Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, when the ambiguity set constitutes a 2-Wasserstein ball centered at a discrete distribution, the distributionally robust linear program is equivalent to a copositive program (if the problem has complete recourse) or can be approximated arbitrarily closely by a sequence of copositive programs (if the problem has sufficiently expensive recourse). These results directly extend to the classical robust setting and motivate strong tractable approximations of two-stage problems based on semidefinite approximations of the copositive cone. We also demonstrate that the two-stage distributionally robust optimization problem is equivalent to a tractable linear program when the ambiguity set constitutes a 1-Wasserstein ball centered at a discrete distribution and there are no support constraints.