
Journal of Convex Analysis 30 (2023), No. 3, 951999 Copyright Heldermann Verlag 2023 Trajectory Following Dynamic Programming Algorithms without Finite Support Assumptions Maël Forcier CERMICS, Ecole des Ponts, MarnelaVallée, France Vincent Leclère CERMICS, Ecole des Ponts, MarnelaVallée, France vincent.leclere@enpc.fr We introduce a class of algorithms, called Trajectory Following Dynamic Programming (TFDP) algorithms, that iteratively refines approximations of costtogo 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 costtogo functions, we provide a new convergence and complexity proof that allows random variables with nonfinitely 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. [ Fulltextpdf (353 KB)] for subscribers only. 