Tropical dynamic programming in stochastic multistage optimization ; Programmation dynamique tropicale en optimisation stochastique multi-étapes

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 ...