Journal of Convex Analysis 30 (2023), No. 2, 627--658
Copyright Heldermann Verlag 2023
Time Block Decomposition of Multistage Stochastic Optimization Problems
Pierre Carpentier
UMA, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France
pierre.carpentier@ensta-paris.fr
Jean-Philippe Chancelier
CERMICS, Ecole des Ponts ParisTech, Marne-la-Vallée, France
Michel De Lara
CERMICS, Ecole des Ponts ParisTech, Marne-la-Vallée, France
Thomas Martin
CERMICS, Ecole des Ponts ParisTech, Marne-la-Vallée, France
Tristan Rigaut
Efficacity, Marne-la-Vallée, France
Multistage stochastic optimization problems are, by essence, complex as their solutions are functions of both stages and uncertainties. Their large scale nature makes decomposition methods appealing, like dynamic programming which is a sequential decomposition using a state variable defined at all stages. By contrast, in this paper we introduce the notion of state reduction by time blocks, that is, at stages that are not necessarily all the original stages. Then, we prove a dynamic programming equation with value functions that are functions of a state only at some stages. This equation crosses over time blocks, but involves a dynamic optimization inside each block. We illustrate our contribution by showing its potential in three applications in multistage stochastic optimization: mixing dynamic programming and stochastic programming, two-time-scale optimization problems, decision-hazard-decision optimization problems.
Keywords: Multistage stochastic optimization, dynamic programming, time scales, time block decomposition, decision-hazard-decision.
MSC: 60J05 90C15 90C39 90C06 49M27.
[ Fulltext-pdf (535 KB)] for subscribers only.