论文标题
两阶段分布的随机分解方法在强大的优化方面
Stochastic Decomposition Method for Two-Stage Distributionally Robust Optimization
论文作者
论文摘要
在本文中，我们提出了一种基于顺序采样的算法，用于两阶段分布稳健线性编程（2-DRLP）模型。 2-DRLP模型是在具有离散或连续概率分布的一般歧义集上定义的。该算法是Higle and Sen（Math。of OR 16（3），650-669，1991）的众所周知的随机分解算法的分布强大版本，用于两阶段的随机线性程序。我们将算法称为分布鲁棒的随机分解（DRSD）方法。该算法的关键特征包括（1）它与数据驱动的模棱两可集的近似作用，这些概况集是使用尺寸增加的样品以及（2）有效构建最差的期望函数的近似值，该函数仅解决了每个迭代中仅两个第二阶段的子问题。我们确定歧义设置近似收敛到真实歧义集的条件，并表明DRSD方法均无概率地鉴定出最佳解决方案。我们还计算评估DRSD方法的性能，以求解随机编程文献中考虑的实例的分布稳健版本。数值结果证实了DRSD方法的分析行为，并说明了基于外部采样的分解方法（分布稳健的L形方法）的计算优势。
In this paper, we present a sequential sampling-based algorithm for the two-stage distributionally robust linear programming (2-DRLP) models. The 2-DRLP models are defined over a general class of ambiguity sets with discrete or continuous probability distributions. The algorithm is a distributionally robust version of the well-known stochastic decomposition algorithm of Higle and Sen (Math. of OR 16(3), 650-669, 1991) for a two-stage stochastic linear program. We refer to the algorithm as the distributionally robust stochastic decomposition (DRSD) method. The key features of the algorithm include (1) it works with data-driven approximations of ambiguity sets that are constructed using samples of increasing size and (2) efficient construction of approximations of the worst-case expectation function that solves only two second-stage subproblems in every iteration. We identify conditions under which the ambiguity set approximations converge to the true ambiguity sets and show that the DRSD method asymptotically identifies an optimal solution, with probability one. We also computationally evaluate the performance of the DRSD method for solving distributionally robust versions of instances considered in stochastic programming literature. The numerical results corroborate the analytical behavior of the DRSD method and illustrate the computational advantage over an external sampling-based decomposition approach (distributionally robust L-shaped method).
