Skip to Main content Skip to Navigation

Programmation dynamique tropicale en optimisation stochastique multi-étapes

Abstract : In this thesis, we are interested in the resolution by dynamic programming of Multistage Stochastic optimization Problems (MSP).In the first part, we are interested in the approximation of the value functions of a MSP as min-plus or max-plus linear combinations of basic functions. This approach can be interpreted as the tropical algebra analogue of Approximate Dynamic Programming parametric models, notably studied by Bertsekas and Powell.In the simplified framework of multistage deterministic optimisation problems, we introduce an algorithm, called Tropical Dynamic Programming (TDP), which iteratively constructs approximations of value functions as min-plus or max-plus linear combinations. At each iteration, a trajectory of states is randomly drawn and the states forming this trajectory are called trial points. Based on the current approximations of the value functions, TDP then recursively calculates, by going back in time, a new basic function to be added to the current linear min-plus or max-plus combination. The basic function added to the approximation at time t must verify two compatibility conditions: it must be tight at the t-th trial point and valid. In this way TDP avoids discretising the entire state space and tries to emancipate itself from the curse of dimensionality.Our first contribution, within the framework of deterministic multistage optimization problems, is sufficient conditions on the richness of the trial points in order to ensure almost surely the asymptotic convergence of the generated approximations to the value functions, at points of interest.In the second part, the framework of the TDP algorithm was extended to Lipschitz MSPs where the noises are finite and independent. In this framework, max-plus linear and min-plus linear approximations of the value functions are generated simultaneously. At each iteration, in a forward phase, a particular deterministic trajectory of states called the problem-child trajectory is generated. Then, in the backward phase in time, the common approximations are refined by adding basic functions that are tight and valid.Our second contribution is the proof that the difference between the max-plus and min-plus linear combinations thus generated tends towards 0 along the problem-child trajectories. This result generalises a result from Baucke, Downward and Zackeri in 2018 who proved the convergence of a similar scheme, introduced by Philpott, de Matos and Zackeri in 2013, for convex MSPs. However, the algorithmic complexity of the TDP extension presented is highly dependent on the size of the noise support of a given MSP.In the third part, we are interested in quantifying the difference between the values of two MSPs differing only in their scenario tree. Under assumptions of regularities, Pflug and Pichler showed in 2012 that the value of such MSPs is Lipschitz-continuous with respect to the Nested Distance they introduced. However, the computation of the Nested Distance requires an exponential number (w.r.t. the horizon T) of computation of optimal transport problems.Motivated by the success of Sinkhorn's algorithm for computing entropic relaxation of the optimal transport problem, as a third contribution we propose an entropic relaxation of the Nested Distance which we illustrate numerically.Finally, in order to justify the resolution by dynamic programming in more general cases of MSPs, interchange between integration and minimisation must be justified. In the fourth contribution, we establish a general interchange result between integration and minimization which includes some usual results.
Document type :
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Tuesday, February 2, 2021 - 4:44:17 PM
Last modification on : Thursday, June 3, 2021 - 3:16:37 AM
Long-term archiving on: : Monday, May 3, 2021 - 8:37:47 PM


Version validated by the jury (STAR)


  • HAL Id : tel-03129146, version 1



Duy-Nghi Tran. Programmation dynamique tropicale en optimisation stochastique multi-étapes. Optimisation et contrôle [math.OC]. Université Paris-Est, 2020. Français. ⟨NNT : 2020PESC1040⟩. ⟨tel-03129146⟩



Record views


Files downloads