# Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms

* Corresponding author
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : 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.
Document type :
Preprints, Working Papers, ...
Domain :

https://hal.inria.fr/hal-00935266
Contributor : Zheng Qu <>
Submitted on : Thursday, January 23, 2014 - 12:04:29 PM
Last modification on : Thursday, March 5, 2020 - 6:23:48 PM

### Identifiers

• HAL Id : hal-00935266, version 1
• ARXIV : 1109.5241

### Citation

Stephane Gaubert, William Mceneaney, Zheng Qu. Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms. 2011. ⟨hal-00935266⟩

Record views