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

Zheng Qu 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : Max-plus based methods have been recently explored for solution of first-order Hamilton--Jacobi--Bellman equations by several authors. Among several max-plus numerical methods, 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\tau))$+$O(\sqrt{\tau})$, where $\tau$ is the time discretization step and $N$ is the number of iterations. Here we use a recently established contraction result for the indefinite Riccati flow in Thompson's part metric to show that under different technical assumptions, still covering an important class of problems, the error is only of order $O(e^{-\alpha N\tau})+O(\tau)$ for some $\alpha>0$. This also allows us to obtain improved estimates of the execution time and to tune the precision of the pruning procedure, which in practice is a critical element of the method.
Type de document :
Article dans une revue
SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2014, 52 (5), pp.2677-2709. 〈10.1137/130906702〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01112251
Contributeur : Stephane Gaubert <>
Soumis le : lundi 2 février 2015 - 15:07:53
Dernière modification le : jeudi 10 mai 2018 - 02:04:12

Lien texte intégral

Identifiants

Collections

Citation

Zheng Qu. Contraction of Riccati flows applied to the convergence analysis of a max-plus curse of dimensionality free method. SIAM Journal on Control and Optimization, Society for Industrial and Applied Mathematics, 2014, 52 (5), pp.2677-2709. 〈10.1137/130906702〉. 〈hal-01112251〉

Partager

Métriques

Consultations de la notice

181