Stochastic Dynamic Linear Programming: A Sequential Sampling-based Multistage Stochastic Programming Algorithm
Abstract: Multistage stochastic programming deals with operational and planning problems that involve a sequence of decisions over time while responding to realizations that are uncertain. Algorithms designed to address multistage stochastic linear programming (MSLP) problems often rely upon scenario trees to represent the underlying stochastic process. When this process exhibits stagewise independence, sampling-based techniques, particularly the stochastic dual dynamic programming (SDDP) algorithm, have received wide acceptance. However, these sampling-based methods still operate with a deterministic representation of the problem which uses the so-called sample average approximation. In this work we present a sequential sampling approach for MSLP problems while allowing the decision process to assimilate new sampling information in a recursive fashion. We refer to this method as the stochastic dynamic linear programming (SDLP) algorithm. Since we use sequential sampling, the algorithm does not necessitate a priori representation of uncertainty, either through a scenario tree or sample average approximation, which require the knowledge/estimation of the underlying distribution. In this regard, SDLP is a distribution-free approach to address the MSLP problems. We employ regularization at non-terminal stages and have a piecewise-affine solution discovery scheme to identify incumbent solutions used in the regularization term embedded into the algorithm. The SDLP algorithm is shown to provide asymptotically convergent value functions and an optimal policy, with probability one.
Keywords: Multistage stochastic programming, regularized cutting-plane methods, stochastic decomposition, sequential sampling.
Category 1: Stochastic Programming
Citation: Southern Methodist University, September/2019.
Entry Submitted: 09/30/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|