论文标题
关于分布稳健的多阶段凸优化：新算法和复杂性分析
On Distributionally Robust Multistage Convex Optimization: New Algorithms and Complexity Analysis
论文作者
论文摘要
本文介绍了算法研究和复杂性分析，用于求解分布强劲的多阶段凸优化（DR-MCO）。我们将通常连续的双动态编程（DDP）算法推广到DR-MCO，并提出了一种新的非连续DDP算法，该算法以自适应方式探索阶段。我们在DDP递归中引入了双重界限，以防止由递归切割平面方法引起的双重近似值的Lipschitz常数的生长。然后，我们对所提出的算法提供了彻底的子问题 - 奥科群岛的复杂性分析，既证明了上的复杂性边界和匹配的下限。据我们所知，这是DR-MCO上DDP型算法的第一个非染色复杂性结果，该算法揭示了在某些实际情况下，新的非连续DDP算法相对于阶段的数量线性缩放。给出了数值示例，以显示提出的非连续DDP算法和双结合技术的有效性，包括缩短计算时间或子问题的数量Oracle评估的数量，以及解决问题的能力而没有相对完整的诉讼。
This paper presents an algorithmic study and complexity analysis for solving distributionally robust multistage convex optimization (DR-MCO). We generalize the usual consecutive dual dynamic programming (DDP) algorithm to DR-MCO and propose a new nonconsecutive DDP algorithm that explores the stages in an adaptive fashion. We introduce dual bounds in the DDP recursions to prevent the growth of Lipschitz constants of the dual approximations caused by recursive cutting plane methods. We then provide a thorough subproblem-oracle-based complexity analysis of the proposed algorithms, proving both upper complexity bounds and a matching lower bound. To the best of our knowledge, this is the first nonasymptotic complexity result for DDP-type algorithms on DR-MCO, which reveals that in some practical settings the new nonconsecutive DDP algorithm scales linearly with respect to the number of stages. Numerical examples are given to show the effectiveness of the proposed nonconsecutive DDP algorithm and the dual-bounding technique, including the reduction of the computation time or the number of subproblem oracle evaluations, and the capability to solve problems without relatively complete recourse.
