论文标题
WASSERSTEIN的二阶圆锥编程方法分布在强大的两阶段线性程序上
Second-order Conic Programming Approach for Wasserstein Distributionally Robust Two-stage Linear Programs
论文作者
论文摘要
本文提出了一种二阶圆锥编程（SOCP）方法，以在1-Wasserstein球上解决分布强劲的两阶段随机线性程序。我们从案例开始，仅在目标函数中具有分配不确定性，并将其准确地重新将其重新定义为SOCP问题。然后，我们仅在约束中研究了分布不确定性的情况，并表明这种健壮的程序通常是NP-HARD，因为它涉及多面体上的规范最大化问题。但是，如果多面体的极端点作为先验，则将其简化为SOCP问题。这促使设计一种具有可证明的收敛性的约束生成算法，以大致解决NP硬性问题。与退出的文献形成鲜明对比的是，实现最差的成本的分布是通过简单地在两种情况下扰动每个样本来作为“经验”分布的。最后，实验说明了所提出的模型的优势，从样本外的性能和计算复杂性方面。
This paper proposes a second-order conic programming (SOCP) approach to solve distributionally robust two-stage stochastic linear programs over 1-Wasserstein balls. We start from the case with distribution uncertainty only in the objective function and exactly reformulate it as an SOCP problem. Then, we study the case with distribution uncertainty only in constraints, and show that such a robust program is generally NP-hard as it involves a norm maximization problem over a polyhedron. However, it is reduced to an SOCP problem if the extreme points of the polyhedron are given as a prior. This motivates to design a constraint generation algorithm with provable convergence to approximately solve the NP-hard problem. In sharp contrast to the exiting literature, the distribution achieving the worst-case cost is given as an "empirical" distribution by simply perturbing each sample for both cases. Finally, experiments illustrate the advantages of the proposed model in terms of the out-of-sample performance and the computational complexity.
