Contraction of Riccati flows applied to the convergence analysis of the max-plus curse of dimensionality free method

Abstract

Max-plus based methods have been recently explored for solution of first-order Hamilton-Jacobi-Bellman equations by several authors. In particular, McEneaney's curse-of-dimensionality free method applies to the equations where the Hamiltonian takes the form of a (pointwise) maximum of linear/quadratic forms. In previous works of McEneaney and Kluberg, the approximation error of the method was shown to be O(1/(Nτ))+O(√τ) where τ is the time discretization step and N is the number of iterations. Here we use a recently established contraction result of the indefinite Riccati flow in Thompson's metric to show that under different technical assumptions, still covering an important class of problems, the total error incorporating a pruning procedure of error order τ2 is O(e-αNτ) +O(τ) for some α > 0 related to the contraction rate of the indefinite Riccati flow. © 2013 EUCA.