Stochastic Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming
From MaRDI portal
(Redirected from Publication:5152473)
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 that uses the so-called 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 two-stage SLP models. We employ quadratic regularization for optimization problems in the non-terminal stages. Furthermore, we introduce the notion of basic feasible policies which provide a piecewise-affine 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.
Recommendations
- A sequential sampling procedure for stochastic programming
- Adaptive sequential sample average approximation for solving two-stage stochastic linear programs
- Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
- Sequential importance sampling algorithms for dynamic stochastic programming
- On the convergence of sampling algorithms for solving dynamic stochastic programming
- Sampling-based approximation algorithms for multistage stochastic optimization
- Solving sequences of refined multistage stochastic linear programs
- Dynamic stochastic approximation for multi-stage stochastic optimization
- Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
- Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
Cites work
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- A comment on ``Computational complexity of stochastic programming problems
- A New Scenario Decomposition Method for Large-Scale Stochastic Optimization
- A regularized decomposition method for minimizing a sum of polyhedral functions
- A Stochastic Approximation Method
- Analysis of stochastic dual dynamic programming method
- Asymptotic results of stochastic decomposition for two-stage stochastic quadratic programming
- Computational complexity of stochastic programming problems
- Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
- Cut sharing for multistage stochastic linear programs with interstage dependency
- Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
- Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
- Finite master programs in regularized stochastic decomposition
- scientific article; zbMATH DE number 3539473 (Why is no real title available?)
- scientific article; zbMATH DE number 3354103 (Why is no real title available?)
- Improving the performance of stochastic dual dynamic programming
- Lectures on stochastic programming. Modeling and theory.
- Lipschitz continuity of inf-projections
- Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction
- Multi-stage stochastic optimization applied to energy planning
- Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
- On the Convergence of Algorithms with Implications for Stochastic and Nondifferentiable Optimization
- On the convergence of sampling-based decomposition algorithms for multistage stochastic programs
- On the convergence of stochastic dual dynamic programming and related methods
- Partitioning procedures for solving mixed-variables programming problems
- Regularized decomposition of high-dimensional multistage stochastic programs with Markov uncertainty
- Regularized stochastic dual dynamic programming for convex nonlinear optimization problems
- Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures
- Scenario reduction in stochastic programming
- Scenarios and Policy Aggregation in Optimization Under Uncertainty
- Scenarios for multistage stochastic programs
- Statistical approximations for stochastic linear programming problems
- Stochastic Decomposition for Two-Stage Stochastic Linear Programs with Random Cost Coefficients
- Stochastic decomposition. A statistical method for large scale stochastic linear programming
- Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
- stochastic quasigradient methods and their application to system optimization†
- The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse
- The Scenario Generation Algorithm for Multistage Stochastic Linear Programming
Cited in
(11)- Dynamic stochastic approximation for multi-stage stochastic optimization
- Two-stage linear decision rules for multi-stage stochastic programming
- Step decision rules for multistage stochastic programming: a heuristic approach
- Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
- Comparison of Sampling Methods for Dynamic Stochastic Programming
- Stochastic decomposition method for two-stage distributionally robust linear optimization
- On the impact of deep learning-based time-series forecasts on multistage stochastic programming policies
- Compromise policy for multi-stage stochastic linear programming: variance and bias reduction
- Coordinating international humanitarian inventory by stochastic dual dynamic programming
- Decomposition algorithms for computational stochastic mixed-integer programming: a survey
- MSLiP: A computer code for the multistage stochastic linear programming problem
This page was built for publication: Stochastic Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5152473)
