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

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

2011-09-24

arxiv.org/abs/1109.5241v1

Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC 11),Orlando, FL, USA,

Mathematics

Optimization and Control

8pages 5 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-602424