Skip to Main content Skip to Navigation
Conference papers

A Min-plus-SDDP Algorithm for Deterministic Multistage Convex 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 consider discrete time optimal control problems with finite horizon involving continuous states and possibly both continuous and discrete controls, subject to non-stationary linear dynamics and convex costs. In this general framework, we present a stochastic algorithm which generates monotone approximations of the value functions as a pointwise supremum or infimum of basic functions (for example affine or quadratic) which are randomly selected. We give sufficient conditions on the way basic functions are selected in order to ensure almost sure convergence of the approximations to the value function on a set of interest. Then we study a linear-quadratic optimal control problem with one control constraint. On this toy example we show how to use our algorithm in order to build lower approximations, like the SDDP algorithm, as supremum of affine cuts and upper approximations, by min-plus techniques, as infimum of quadratic fonctions.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-02436343
Contributor : Marianne Akian <>
Submitted on : Monday, January 13, 2020 - 2:28:53 AM
Last modification on : Friday, April 24, 2020 - 5:19:13 PM
Long-term archiving on: : Tuesday, April 14, 2020 - 1:14:46 PM

File

CDC2019.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02436343, version 1

Citation

Marianne Akian, Jean-Philippe Chancelier, Benoît Tran. A Min-plus-SDDP Algorithm for Deterministic Multistage Convex Programming. CDC 2019 - 58th IEEE Conference on Decision and Control, Dec 2019, Nice, France. ⟨hal-02436343⟩

Share

Metrics

Record views

83

Files downloads

399