Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2011

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

Résumé

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.

Dates et versions

hal-00935266 , version 1 (23-01-2014)

Identifiants

Citer

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⟩
302 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More