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

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 : mercredi 14 novembre 2018 - 15:20:11

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

372