TY - GEN
T1 - Curse of dimensionality reduction in max-plus based approximation methods
T2 - Joint 50th IEEE Conference on Decision and Control and 2011 European Control Conference, CDC-ECC 2011
AU - Gaubert, Stéphane
AU - McEneaney, William
AU - Qu, Zheng
PY - 2011/1/1
Y1 - 2011/1/1
N2 - Max-plus based methods have been recently developed to approximate the value function of possibly high dimensional optimal control problems. A critical step of these methods consists in approximating a function by a supremum of a small number of functions (max-plus "basis functions") taken from a prescribed dictionary. We study several variants of this approximation problem, which we show to be continuous versions of the facility location and k-center combinatorial optimization problems, in which the connection costs arise from a Bregman distance. We give theoretical error estimates, quantifying the number of basis functions needed to reach a prescribed accuracy. We derive from our approach a refinement of the curse of dimensionality free method introduced previously by McEneaney, with a higher accuracy for a comparable computational cost.
AB - Max-plus based methods have been recently developed to approximate the value function of possibly high dimensional optimal control problems. A critical step of these methods consists in approximating a function by a supremum of a small number of functions (max-plus "basis functions") taken from a prescribed dictionary. We study several variants of this approximation problem, which we show to be continuous versions of the facility location and k-center combinatorial optimization problems, in which the connection costs arise from a Bregman distance. We give theoretical error estimates, quantifying the number of basis functions needed to reach a prescribed accuracy. We derive from our approach a refinement of the curse of dimensionality free method introduced previously by McEneaney, with a higher accuracy for a comparable computational cost.
U2 - 10.1109/CDC.2011.6161386
DO - 10.1109/CDC.2011.6161386
M3 - Conference contribution
AN - SCOPUS:84860654722
SN - 9781612848006
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 1054
EP - 1061
BT - 2011 50th IEEE Conference on Decision and Control and European Control Conference, CDC-ECC 2011
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 12 December 2011 through 15 December 2011
ER -