On the Convergence of Sampling-Based Decomposition Algorithms for Multistage Stochastic Programs

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.The first author acknowledges support by the Swiss National Science Foundation. The second author acknowledges support by NZPGST Grant UOAX0203. The authors are grateful to the anonymous referees for comments improving the exposition of this paper.     

Convergent Cutting-Plane and Partial-Sampling Algorithm for Multistage Stochastic Linear Programs with Recourse

We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.