Inexact Cuts in Stochastic Dual Dynamic Programming Applied to Multistage Stochastic Nondifferentiable Problems
将不精确随机对偶动态规划（ISDDP）从线性与可微非线性多阶段随机规划扩展到不可微情形，给出了凸不可微优化问题值函数的不精确割公式，并证明了在误差有界时上下界序列的极限与最优值距离不超过3εT，渐近消失误差下收敛到最优策略。
In [V. Guigues, SIAM J. Optim., 30 (2020), pp. 407--438], 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 [V. Guigues, SIAM J. Optim., 30 (2020), pp. 407--438] 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 $\varepsilon$, 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 \varepsilon T$ to the optimal value and that for asymptotically vanishing errors ISDDP converges to an optimal policy. Finally, we present the results of encouraging numerical experiments on a multistage nondifferentiable stochastic convex program solved using exact SDDP and the proposed ISDDP.