  


Stochastic Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming
Harsha Gangammanavar (harshasmu.edu) 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, samplingbased techniques, particularly the stochastic dual dynamic programming (SDDP) algorithm, have received wide acceptance. However, these samplingbased methods still operate with a deterministic representation of the problem that uses the socalled sample average approximation. In this work, we present a sequential sampling approach for MSLP problems that allows the decision process to assimilate newly sampled data recursively. 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, both of which require a knowledge/estimation of the underlying distribution. In this regard, SDLP is a sequential sampling approach to address MSLP problems. This method constitutes a generalization of the Stochastic Decomposition (SD) for twostage SLP models. We employ quadratic regularization for optimization problems in the nonterminal stages. Furthermore, we introduce the notion of basic feasible policies which provide a piecewiseaffine solution discovery scheme, that is embedded within the optimization algorithm to identify incumbent solutions used for regularization. Finally, we show that the SDLP algorithm provides a sequence of decisions and corresponding value function estimates along a sequence of state trajectories that asymptotically converge to their optimal counterparts, with probability one. Keywords: Multistage stochastic programming, regularized cuttingplane methods, stochastic decomposition, sequential sampling. Category 1: Stochastic Programming Citation: Download: [PDF] Entry Submitted: 09/30/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  