TY - GEN
T1 - A Min-plus-SDDP Algorithm for Deterministic Multistage Convex Programming
AU - Akian, Marianne
AU - Chancelier, Jean Philippe
AU - Tran, Benoit
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/12/1
Y1 - 2019/12/1
N2 - 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.
AB - 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.
KW - Deterministic multistage optimization problems
KW - Dynamic Programming
KW - Stochastic Dual Dynamic Programming
KW - min-plus algebra
KW - tropical algebra
U2 - 10.1109/CDC40024.2019.9028935
DO - 10.1109/CDC40024.2019.9028935
M3 - Conference contribution
AN - SCOPUS:85082435731
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 3334
EP - 3339
BT - 2019 IEEE 58th Conference on Decision and Control, CDC 2019
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 58th IEEE Conference on Decision and Control, CDC 2019
Y2 - 11 December 2019 through 13 December 2019
ER -