Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Tropical Dynamic Programming for Lipschitz Multistage Stochastic Programming

Marianne Akian 1 Jean-Philippe Chancelier 2 Benoît Tran 2, 1
1 TROPICAL - TROPICAL
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : We present an algorithm called Tropical Dynamic Programming (TDP) which builds upper and lower approximations of the Bellman value functions in risk-neutral Multistage Stochastic Programming (MSP), with independent noises of finite supports. To tackle the curse of dimensionality, popular parametric variants of Approximate Dynamic Programming approximate the Bellman value function as linear combinations of basis functions. Here, Tropical Dynamic Programming builds upper (resp. lower) approximations of a given value function as min-plus linear (resp. max-plus linear) combinations of "basic functions". At each iteration, TDP adds a new basic function to the current combination following a deterministic criterion introduced by Baucke, Downward and Zackeri in 2018 for a variant of Stochastic Dual Dynamic Programming. We prove, for every Lipschitz MSP, the asymptotic convergence of the generated approximating functions of TDP to the Bellman value functions on sets of interest. We illustrate this result on MSP with linear dynamics and polyhedral costs.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-03059701
Contributor : Marianne Akian <>
Submitted on : Sunday, December 13, 2020 - 12:50:12 AM
Last modification on : Friday, January 15, 2021 - 5:45:43 PM

Links full text

Identifiers

  • HAL Id : hal-03059701, version 1
  • ARXIV : 2010.10619

Citation

Marianne Akian, Jean-Philippe Chancelier, Benoît Tran. Tropical Dynamic Programming for Lipschitz Multistage Stochastic Programming. 2020. ⟨hal-03059701⟩

Share

Metrics

Record views

29