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.

8pages 5 figures

References in corpus (2)

• Duality and separation theorems in idempotent semimodules
• A reduced complexity numerical method for optimal gate synthesis

Cited by in corpus (16)

• On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton--Jacobi partial differential equations
• Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations
• Neural network architectures using min-plus algebra for solving certain high dimensional optimal control problems and Hamilton-Jacobi PDEs
• Piece-wise quadratic approximations of arbitrary error functions for fast and robust machine learning
• Sparsity in Max-Plus Algebra and Systems
• Single cut and multicut SDDP with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments
• Certification of Bounds of Non-linear Functions: the Templates Method
• Overcoming the curse of dimensionality for some Hamilton--Jacobi partial differential equations via neural network architectures
• Max-Plus Matching Pursuit for Deterministic Markov Decision Processes
• Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
• Bundle-based pruning in the max-plus curse of dimensionality free method
• Multicut decomposition methods with cut selection for multistage stochastic programs
• Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression
• Hopf-type representation formulas and efficient algorithms for certain high-dimensional optimal control problems
• Approximate dynamic programming with $(\min ,+)$ linear function approximation for Markov decision processes
• Dual Dynamic Programming with cut selection: convergence proof and numerical experiments