Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

Convergence of Trajectory Following Dynamic Programming algorithms for multistage stochastic problems without finite support assumptions

Abstract : We introduce a class of algorithms, called Trajectory Following Dynamic Programming (TFDP) algorithms, that iteratively refines approximation 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.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

https://hal-enpc.archives-ouvertes.fr/hal-03683697
Contributeur : Vincent Leclère Connectez-vous pour contacter le contributeur
Soumis le : mardi 31 mai 2022 - 18:51:33
Dernière modification le : samedi 25 juin 2022 - 03:14:19

Fichier

SDDP_gen_cost.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-03683697, version 1

Collections

Citation

Maël Forcier, Vincent Leclère. Convergence of Trajectory Following Dynamic Programming algorithms for multistage stochastic problems without finite support assumptions. 2022. ⟨hal-03683697⟩

Partager

Métriques

Consultations de la notice

0

Téléchargements de fichiers

0