# Numerical Methods for Convex Multistage Stochastic Optimization

arXiv: https://arxiv.org/abs/2303.15672 · HTML: https://mlsanity.com/paper/2303.15672/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 50 references that are in the map.
- First posted on arXiv 28 Mar 2023.

## Builds on (most cited first, 8 of 8)

- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [Dynamic Stochastic Approximation for Multi-stage Stochastic Optimization](https://mlsanity.com/paper/1707.03324/) (2017)
- [Mathematical Foundations of Distributionally Robust Multistage Optimization](https://mlsanity.com/paper/2101.02498/) (2021)
- [Complexity of Stochastic Dual Dynamic Programming](https://mlsanity.com/paper/1912.07702/) (2019)
- [Dual dynamic programming for stochastic programs over an infinite horizon](https://mlsanity.com/paper/2303.02024/) (2023)
- [Duality and sensitivity analysis of multistage linear stochastic programs](https://mlsanity.com/paper/1911.07080/) (2019)
- [Stochastic Dual Dynamic Programming for Multistage Stochastic Mixed-Integer Nonlinear Optimization](https://mlsanity.com/paper/1912.13278/) (2019)
- [Risk-Averse Stochastic Optimal Control: an efficiently computable statistical upper bound](https://mlsanity.com/paper/2112.09757/) (2021)

## Built on by (most cited first, 1 of 1)

- [AI4OPT: AI Institute for Advances in Optimization](https://mlsanity.com/paper/2307.02671/) (2023)

## Abstract (arXiv)

Optimization problems involving sequential decisions in a stochastic environment were studied in Stochastic Programming (SP), Stochastic Optimal Control (SOC) and Markov Decision Processes (MDP). In this paper we mainly concentrate on SP and SOC modelling approaches. In these frameworks there are natural situations when the considered problems are convex. Classical approach to sequential optimization is based on dynamic programming. It has the problem of the so-called ``Curse of Dimensionality", in that its computational complexity increases exponentially with increase of dimension of state variables. Recent progress in solving convex multistage stochastic problems is based on cutting planes approximations of the cost-to-go (value) functions of dynamic programming equations. Cutting planes type algorithms in dynamical settings is one of the main topics of this paper. We also discuss Stochastic Approximation type methods applied to multistage stochastic optimization problems. From the computational complexity point of view, these two types of methods seem to be complimentary to each other. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables. On the other hand, stochastic approximation type methods can only deal with a small number of stages, but a large number of decision variables.