Convergence Analysis of Sampling-Based Decomposition Methods for Risk-Averse Multistage Stochastic Convex Programs
Convergence Analysis of Sampling-Based Decomposition Methods for Risk-Averse Multistage Stochastic Convex Programs
复制标题
DOI：
10.1137/140983136
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
V. Guigues
中科院分区：
文献类型：
--
作者：
V. Guigues
我们考虑一类基于采样的分解方法来解决风险规避的多阶段随机凸规划。我们证明了一个用于计算构建追索函数的外部线性化所需的削减的公式。该公式可用于获得应用于凸非线性问题的随机对偶动态规划的有效实现。我们证明了当相对完整的追索权假设成立时，这些分解方法几乎肯定收敛。我们还证明了当应用于不满足相对完整的追索权假设的风险规避多阶段随机线性程序时，这些算法几乎肯定会收敛。首先进行分析，假设底层随机过程是阶段间独立且离散的，每个阶段都有一组有限的可能实现。然后，我们指出了将方法和收敛分析扩展到过程依赖级间的情况的两种方法。
We consider a class of sampling-based decomposition methods to solve risk-averse multistage stochastic convex programs. We prove a formula for the computation of the cuts necessary to build the outer linearizations of the recourse functions. This formula can be used to obtain an efficient implementation of Stochastic Dual Dynamic Programming applied to convex nonlinear problems. We prove the almost sure convergence of these decomposition methods when the relatively complete recourse assumption holds. We also prove the almost sure convergence of these algorithms when applied to risk-averse multistage stochastic linear programs that do not satisfy the relatively complete recourse assumption. The analysis is first done assuming the underlying stochastic process is interstage independent and discrete, with a finite set of possible realizations at each stage. We then indicate two ways of extending the methods and convergence analysis to the case when the process is interstage dependent.