Journal Home Page

Cumulative Index

List of all Volumes

Complete Contents
of this Volume

Previous Article

Next Article

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

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.