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

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 diffierence 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 root 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 dimensions 1 and 2.