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

Stephane Gaubert 1, 2 William Mceneaney 3 Zheng Qu 1, 2, *
* Auteur correspondant
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
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.
Type de document :
Pré-publication, Document de travail
8pages 5 figures. 2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00935266
Contributeur : Zheng Qu <>
Soumis le : jeudi 23 janvier 2014 - 12:04:29
Dernière modification le : jeudi 12 avril 2018 - 01:47:06

Lien texte intégral

Identifiants

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

Collections

Citation

Stephane Gaubert, William Mceneaney, Zheng Qu. Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms. 8pages 5 figures. 2011. 〈hal-00935266〉

Partager

Métriques

Consultations de la notice

336