论文标题
SDDP中的不精确切割应用于多阶段随机性非不同问题
Inexact cuts in SDDP applied to multistage stochastic nondifferentiable problems
论文作者
论文摘要
在[13]中，引入了一个名为ISDDP的随机双动力学编程（SDDP）的不精确变体，该变体使用了在该方法的正向和向后通行证中解决的问题的近似值（而不是与SDDP相关）。在[13]中研究了SDDP的那种变体，用于线性和可区分的非线性多阶段随机程序（MSP）。在本文中，我们将ISDDP扩展到非不同的MSP。我们首先为凸的非不同优化问题的价值函数提供了不精确削减的公式。然后，我们将这些切割与SDDP相结合，以描述非不同的MSP的ISDDP，并分析该方法的收敛性。更确切地说，对于t阶段的问题，我们表明，对于epsilon从上方界定的错误，上限和下限序列的极限和极限下的上限和下限序列在问题的最佳值上最多是距离3*epsilon*t在最佳值为最佳值，并且对于不体化的错误ISDDP iSDDP转换为最佳策略。 [13] V. Guigues，随机双动力学编程中的无精油，Siam优化期刊，30（1），407-438，2020。
In [13], an Inexact variant of Stochastic Dual Dynamic Programming (SDDP) called ISDDP was introduced which uses approximate (instead of exact with SDDP) primal dual solutions of the problems solved in the forward and backward passes of the method. That variant of SDDP was studied in [13] for linear and for differentiable nonlinear Multistage Stochastic Programs (MSPs). In this paper, we extend ISDDP to nondifferentiable MSPs. We first provide formulas for inexact cuts for value functions of convex nondifferentiable optimization problems. We then combine these cuts with SDDP to describe ISDDP for nondifferentiable MSPs and analyze the convergence of the method. More precisely, for a problem with T stages, we show that for errors bounded from above by epsilon, the limit superior and limit inferior of sequences of upper and lower bounds on the optimal value of the problem are at most at distance 3*epsilon*T to the optimal value and that for asymptotically vanishing errors ISDDP converges to an optimal policy. [13] V. Guigues, Inexact cuts in Stochastic Dual Dynamic Programming, Siam Journal on Optimization, 30(1), 407-438, 2020.
