Optimization Online


Stochastic Dynamic Linear Programming: A Sequential Sampling-based Multistage Stochastic Programming Algorithm

Harsha Gangammanavar(harsha***at***smu.edu)
Suvrajeet Sen(sen***at***datadrivendecisions.org)

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.

Download: [PDF]

Entry Submitted: 09/30/2019
Entry Accepted: 09/30/2019
Entry Last Modified: 09/30/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society