Multi-stage Stochastic Decomposition: The Bridge between Stochastic Programming and Approximate Dynamic Programming
with Professor Suvrajeet Sen, Integrated Systems Engineering, Ohio State University, USA
4pm, A54 PSC
Multi-stage stochastic programs (MSP) 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 a statistically motivated sequential sampling method that is applicable to multi-stage stochastic linear programs, and we refer to it as the 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 of SD: asymptotic convergence of the solutions can be proven (with probability one) without any iteration requiring more than a small sample-size. This data-driven approach also allows us to sequentially update value function approximations, and the computations themselves can be organized in a manner that decomposes the scenario generation (stochastic) process from the optimization computations. As a by-product of this study, we also show that SD algorithms are essentially approximate dynamic programming algorithms for SP. The analysis also reveals conceptual connections between multiple SP algorithms.
Suvrajeet Sen is Professor of Integrated Systems Engineering at The Ohio State University (OSU). Until recently, he was also the Director of the Center for Energy, Sustainability, and the Environment at OSU. Prior to joining OSU, he was a Professor at the University of Arizona, and also served as a program director at NSF where he was responsible for the Operations Research, and the Service Enterprise Engineering programs. Starting in August 2012, he will assume a position on the faculty at the University of Southern California.
Professor Sen is a Fellow of INFORMS. He has served on the editorial board of several journals, including Operations Research as Area Editor for Optimization, and as Associate Editor for INFORMS Journal on Computing, and Journal of Telecommunications Systems. Professor Sen founded the INFORMS Optimization Section.