Michel De Lara, École des Ponts ParisTech
Keywords: stochastic programming, scenario trees, progressive hedging, stochastic optimal control, stochastic dynamic programming, stochastic dual dynamic programming, spatial decomposition.
The course starts with basics in stochastic optimization.
When the problem incorporates several time steps, the stochastic programming approach proposes to build a scenario tree of uncertainties, and to attach one control per node, hence leading to an equivalent deterministic formulation. We present alternative equivalent deterministic formulations.
When a stochastic optimization is formulated on a large number of scenarios, decomposition techniques can be used in order to solve a collection of subproblems each formulated on a single scenario.
The stochastic optimal control approach looks at the problem from a Markovian point of view, where uncertainties are stagewise independent. We present a generic way of solving this problem by Dynamic Programming.
In the framework of dynamic programming, the SDDP (Stochastic Dual Dynamic Programming) method allows to push forward the limits of the curse of dimensionality. Taking advantage of linearity and convexity, SDDP builds (lower) approximations of the Bellman value functions in an iterative way.
Multistage stochastic optimization problems are, by essence, complex because their solutions are indexed both by stages (time) and by uncertainties (scenarios). Quite often, solutions are also indexed by decision units, like nodes in a graph (space), or agents in a team. Hence, their large scale nature makes decomposition methods appealing. We present, in an unified framework, three main approaches and methods to decompose multistage stochastic optimization problems for numerical resolution: time decomposition (and state-based resolution methods, like Stochastic Dynamic Programming, in Stochastic Optimal Control); scenario decomposition (like Progressive Hedging in Stochastic Programming); spatial decomposition (price or resource decompositions).
We will explore different decomposition schemes allowing to split a stochastic optimal control problem — involving a large number of units — so as to obtain several small-scale subproblems. These methods allow to solve the subproblems by Dynamic Programming or SDDP.