MULTISTAGE STOCHASTIC DECOMPOSITION: A BRIDGE BETWEEN STOCHASTIC PROGRAMMING AND APPROXIMATE DYNAMIC PROGRAMMING

作者：Sen Suvrajeet^*; Zhou Zhihong

来源：SIAM Journal on Optimization, 2014, 24(1): 127-153.

DOI：10.1137/120864854

• multistage stochastic programming
• sequential sampling
• stochastic decomposition
• approximate dynamic programming

Multistate stochastic programs pose some of the more challenging optimization problems. Because such models can become rather intractable in general, it is important to design algorithms that can provide approximations which, in the long run, yield solutions that are arbitrarily close to an optimum. In this paper, we propose such a sequential sampling method which is applicable to multistage stochastic linear programs, and we refer to it as the multistage stochastic decomposition (MSD) algorithm. This algorithm represents a dynamic extension of a regularized version of stochastic decomposition (SD). While the method allows general correlation structures, specialized streamlined versions are also possible for special cases of stagewise independent and autoregressive processes commonly incorporated in stochastic programming. As with its two-stage counterpart, the MSD algorithm is shown to provide an asymptotically optimal solution, with probability one. As a by-product of this study, we also show that SD algorithms draw upon features of both approximate dynamic programming as well as stochastic programming.

• 出版日期2014