Tropical Dynamic Programming and Entropic Nested Distance


Benoît Tran


Via Zoom


07 de Outubro de 2021, às 16h

In this presentation I will present two topics related to discrete time stochastic optimal control problems or Multistage Stochastic Programming (MSP).

The first one is a joint work with Marianne Akian (Ecole Polytechnique) and Jean-Philippe Chancelier (ENPC). I will present an iterative forward-backward algorithm for MSP. It is inspired by both max-plus numerical methods introduced by McEneaney and the Stochastic Dual Dynamic Programming (SDDP) algorithm of Pereira and Pinto. I will give an asymptotic convergence result and illustrate it numerically.

The second topic of the talk is a joint work with Zheng Qu (Hong Kong University). The Nested Distance, introduced by Pflug and Pichler in 2012, is a distance between discrete time stochastic processes and is a refinement of the Wasserstein distance which suited for MSP. 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, I will propose an entropic relaxation of the Nested Distance which we illustrate numerically.

*Texto informado pelo autor.

Registre-se com antecedência para este seminário aqui.


Benoît Tran - graduated from Paris-Saclay University (ex Université Paris-Sud) and obtained a Ph.D. prepared at both Ecole Polytechnique and Ecole des Ponts ParisTech (ENPC) in 2020. He is currently a postdoc at the School of Applied Mathematics of FGV Brazil.