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. 3, 951--999
Copyright Heldermann Verlag 2023

Trajectory Following Dynamic Programming Algorithms without Finite Support Assumptions

Maël Forcier
CERMICS, Ecole des Ponts, Marne-la-Vallée, France

Vincent Leclère
CERMICS, Ecole des Ponts, Marne-la-Vallée, France

We introduce a class of algorithms, called Trajectory Following Dynamic Programming (TFDP) algorithms, that iteratively refines approximations of cost-to-go functions of multistage stochastic problems with independent random variables. This framework encompasses most variants of the Stochastic Dual Dynamic Programming algorithm. Leveraging a Lipschitz assumption on the expected cost-to-go functions, we provide a new convergence and complexity proof that allows random variables with non-finitely supported distributions. In particular, this leads to new complexity results for numerous known algorithms. Further, we detail how TFDP algorithms can be implemented without the finite support assumption, either through approximations or exact computations.

Keywords: Multistage stochastic programming, SDDP, duality.

MSC: 90C15, 90C25, 90C39, 90C06, 49M37, 93A15.

[ Fulltext-pdf  (353  KB)] for subscribers only.