Time Blocks Decomposition of Multistage Stochastic Optimization Problems

Pierre Carpentier, Jean-Philippe Chancelier, Michel De Lara and 
Tristan Rigaut
Publication type:
Paper in peer-reviewed journals
images/icons/icon_arxiv.png 1804.01711
Keywords :
decomposition; time blocks; MSC: 90C06; multistage stochastic optimization; dynamic programming; 93E20; 90C39; UMA; two time-scales; ENSTA ParisTech; Université Paris-Saclay; decision hazard decision;
Multistage stochastic optimization problems are, by essence, complex because their solutions are indexed both by stages (time) and by uncertainties. Their large scale nature makes decomposition methods appealing. We provide a method to decompose multistage stochastic optimization problems by time blocks. Our framework covers both stochastic programming and stochastic dynamic programming. We formulate multistage stochastic optimization problems over a so-called history space, with solutions being history feedbacks. We prove a general dynamic programming equation, with value functions defined on the history space. Then, we consider the question of reducing the history using a compressed " state " variable. This reduction can be done by time blocks, that is, at stages that are not necessarily all the original unit stages. We prove a reduced dynamic programming equation. Then, we apply the reduction method by time blocks to several classes of optimization problems, especially two timescales stochastic optimization problems and a novel class consisting of decision hazard decision models. Finally, we consider the case of optimization with noise process.
    author={Pierre Carpentier and Jean-Philippe Chancelier and Michel De 
           Lara and Tristan Rigaut },
    title={Time Blocks Decomposition of Multistage Stochastic 
           Optimization Problems },
    year={submitted },