Time Blocks Decomposition of Multistage Stochastic Optimization Problems

Pierre Carpentier, Jean-Philippe Chancelier, Michel De Lara,
Thomas Martin and Tristan Rigaut
2023
Publication type:
Paper in peer-reviewed journals
Journal:
Journal of Convex Analysis
Keywords :
Multistage stochastic optimization, dynamic programming, time scales, time block decomposition, decision-hazard-decision
Abstract:
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.
BibTeX:
@article{Car-Cha-DeL-Mar-Rig-2023,
    author={Pierre Carpentier and Jean-Philippe Chancelier and Michel De 
           Lara and Thomas Martin and Tristan Rigaut },
    title={Time Blocks Decomposition of Multistage Stochastic 
           Optimization Problems },
    journal={Journal of Convex Analysis },
    year={2023 },
}