Geodesic
Trajectory Following Dynamic Programming Algorithms without Finite Support Assumptions
Journal of convex analysis, Tome 30 (2023) no. 3, pp. 951-999
Cet article a éte moissonné depuis la source Heldermann Verlag

Voir la notice de l'article

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.
Classification : 90C15, 90C25, 90C39, 90C06, 49M37, 93A15
Mots-clés : Multistage stochastic programming, SDDP, duality 
@article{JCA_2023_30_3_JCA_2023_30_3_a9,
     author = {M. Forcier and V. Lecl\`ere},
     title = {Trajectory {Following} {Dynamic} {Programming} {Algorithms} without {Finite} {Support} {Assumptions}},
     journal = {Journal of convex analysis},
     pages = {951--999},
     year = {2023},
     volume = {30},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/JCA_2023_30_3_JCA_2023_30_3_a9/}
}
TY  - JOUR
AU  - M. Forcier
AU  - V. Leclère
TI  - Trajectory Following Dynamic Programming Algorithms without Finite Support Assumptions
JO  - Journal of convex analysis
PY  - 2023
SP  - 951
EP  - 999
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/JCA_2023_30_3_JCA_2023_30_3_a9/
ID  - JCA_2023_30_3_JCA_2023_30_3_a9
ER  - 
%0 Journal Article
%A M. Forcier
%A V. Leclère
%T Trajectory Following Dynamic Programming Algorithms without Finite Support Assumptions
%J Journal of convex analysis
%D 2023
%P 951-999
%V 30
%N 3
%U http://geodesic.mathdoc.fr/item/JCA_2023_30_3_JCA_2023_30_3_a9/
%F JCA_2023_30_3_JCA_2023_30_3_a9
M. Forcier; V. Leclère. Trajectory Following Dynamic Programming Algorithms without Finite Support Assumptions. Journal of convex analysis, Tome 30 (2023) no. 3, pp. 951-999. http://geodesic.mathdoc.fr/item/JCA_2023_30_3_JCA_2023_30_3_a9/