On the Convergence of Sampling-Based Decomposition Algorithms for Multistage Stochastic Programs
On the Convergence of Sampling-Based Decomposition Algorithms for Multistage Stochastic Programs
复制标题
DOI：
10.1007/s10957-004-1842-z
复制
发表时间：
2005-05
影响因子：
1.9
通讯作者：
Karsten Linowsky;A. Philpott
中科院分区：
文献类型：
--
作者：
Karsten Linowsky;A. Philpott
本文给出了一类多阶段随机线性规划抽样算法的收敛性证明，其中不确定参数只出现在约束右端。此类包括SDDP、AND、ReSa和CUPPS。我们表明，在一些独立的假设下的采样过程中，算法收敛概率为1。
The paper presents a convergence proof for a broad class of sampling algorithms for multistage stochastic linear programs in which the uncertain parameters occur only in the constraint right-hand sides. This class includes SDDP, AND, ReSa, and CUPPS. We show that, under some independence assumptions on the sampling procedure, the algorithms converge with probability 1.