Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming

Abstract

Multi-stage stochastic programs (MSP) pose some of the more challenging optimizationproblems. Because such models can become rather intractable in general, it is important todesign algorithms that can provide approximations which, in the long run, yield solutions that arearbitrarily close to an optimum. In this paper, we propose a statistically motivated sequentialsampling method that is applicable to multi-stage stochastic linear programs, and we refer to it asthe multistage stochastic decomposition (MSD) algorithm. As with earlier SD methods for two-stage stochastic linear programs, this approach preserves one of the most attractive features ofSD: asymptotic convergence of the solutions can be proven (with probability one) without anyiteration requiring more than a small sample-size. This data-driven approach also allows us tosequentially update value function approximations, and the computations themselves can beorganized in a manner that decomposes the scenario generation (stochastic) process from theoptimization computations. As a by-product of this study, we also show that SD algorithms areessentially approximate dynamic programming algorithms for SP. Our asymptotic analysis alsoreveals conceptual connections between multiple SP algorithms.