Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Complete list of metadata

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

Links full text

Identifiers

  • 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. 2011. ⟨hal-00935266⟩

Share

Metrics

Record views

471