The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis

Abstract

We introduce a max-plus analogue of the Petrov-Galerkin finite element method to solve finite horizon deterministic optimal control problems. The method relies on a max-plus variational formulation. We show that the error in the sup norm can be bounded from the difference between the value function and its projections on max-plus and min-plus semimodules, when the max-plus analogue of the stiffness matrix is exactly known. In general, the stiffness matrix must be approximated: this requires approximating the operation of the Lax-Oleinik semigroup on finite elements. We consider two approximations relying on the Hamiltonian. We derive a convergence result, in arbitrary dimension, showing that for a class of problems, the error estimate is of order $\delta +\Delta x(\delta {)}^{-1}$ or $\sqrt{\delta }+\Delta x(\delta {)}^{-1}$, depending on the choice of the approximation, where $\delta$ and $\Delta x$ are respectively the time and space discretization steps. We compare our method with another max-plus based discretization method previously introduced by Fleming and McEneaney. We give numerical examples in dimension 1 and 2.

31 pages, 11 figures

References in corpus (1)

• Duality and separation theorems in idempotent semimodules

Cited by in corpus (20)

• The Minkowski Theorem for Max-plus Convex Sets
• On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton--Jacobi partial differential equations
• Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms
• Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations
• Optimal Feedback Law Recovery by Gradient-Augmented Sparse Polynomial Regression
• Neural network architectures using min-plus algebra for solving certain high dimensional optimal control problems and Hamilton-Jacobi PDEs
• A max-plus based fundamental solution for a class of discrete time linear regulator problems
• Idempotent and tropical mathematics and problems of mathematical physics (Volume II)
• Overcoming the curse of dimensionality for some Hamilton--Jacobi partial differential equations via neural network architectures
• Certification of Bounds of Non-linear Functions: the Templates Method
• Max-Plus Matching Pursuit for Deterministic Markov Decision Processes
• Semigroups of max-plus linear operators
• Multigrid methods for two-player zero-sum stochastic games
• Bundle-based pruning in the max-plus curse of dimensionality free method
• Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
• Approximate dynamic programming with $(\min ,+)$ linear function approximation for Markov decision processes
• Hopf-type representation formulas and efficient algorithms for certain high-dimensional optimal control problems
• Fast weak-KAM integrators for separable Hamiltonian systems
• Approximate Dynamic Programming based on Projection onto the (min,+) subsemimodule
• Fast Approximate Dynamic Programming for Infinite-Horizon Markov Decision Processes