On the convergence of decomposition methods for multistage stochastic convex programs
Published in Mathematics of Operations Research, 2015
Recommended citation: Girardeau, Pierre, Vincent Leclere, and Andrew B. Philpott. "On the convergence of decomposition methods for multistage stochastic convex programs." Mathematics of Operations Research 40.1 (2015): 130-145. https://pubsonline.informs.org/doi/pdf/10.1287/moor.2014.0664
We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of stochastic dual dynamic programming, cutting-plane and partial-sampling (CUPPS) algorithm, and dynamic outer-approximation sampling algorithms when applied to problems with general convex cost functions.