Nonlinear Perron-Frobenius theory and max-plus numerical methods for Hamilton-Jacobi equations - Archive ouverte HAL Access content directly
Theses Year : 2013

Nonlinear Perron-Frobenius theory and max-plus numerical methods for Hamilton-Jacobi equations

Théorie de Perron-Frobenius non linéaire et méthodes numériques max-plus pour la résolution d'équations d'Hamilton-Jacobi

(1, 2)
1
2

Abstract

Dynamic programming is one of the main approaches to solve optimal control problems. It reduces the latter problems to Hamilton-Jacobi partial differential equations (PDE). Several techniques have been proposed in the literature to solve these PDE. We mention, for example, finite difference schemes, the so-called discrete dynamic programming method or semi-Lagrangian method, or the antidiffusive schemes. All these methods are grid-based, i.e., they require a discretization of the state space, and thus suffer from the so-called curse of dimensionality. The present thesis focuses on max-plus numerical solutions and convergence analysis for medium to high dimensional deterministic optimal control problems. We develop here max-plus based numerical algorithms for which we establish theoretical complexity estimates. The proof of these estimates is based on results of nonlinear Perron-Frobenius theory. In particular, we study the contraction properties of monotone or non-expansive nonlinear operators, with respect to several classical metrics on cones (Thompson's metric, Hilbert's projective metric), and obtain nonlinear or non-commutative generalizations of the "ergodicity coefficients" arising in the theory of Markov chains. These results have applications in consensus theory and also to the generalized Riccati equations arising in stochastic optimal control.
Une approche fondamentale pour la résolution de problémes de contrôle optimal est basée sur le principe de programmation dynamique. Ce principe conduit aux équations d'Hamilton-Jacobi, qui peuvent être résolues numériquement par des méthodes classiques comme la méthode des différences finies, les méthodes semi-lagrangiennes, ou les schémas antidiffusifs. À cause de la discrétisation de l'espace d'état, la dimension des problèmes de contrôle pouvant être abordés par ces méthodes classiques est souvent limitée à 3 ou 4. Ce phénomène est appellé malédiction de la dimension. Cette thèse porte sur les méthodes numériques max-plus en contôle optimal deterministe et ses analyses de convergence. Nous étudions et developpons des méthodes numériques destinées à attenuer la malédiction de la dimension, pour lesquelles nous obtenons des estimations théoriques de complexité. Les preuves reposent sur des résultats de théorie de Perron-Frobenius non linéaire. En particulier, nous étudions les propriétés de contraction des opérateurs monotones et non expansifs, pour différentes métriques de Finsler sur un cône (métrique de Thompson, métrique projective d'Hilbert). Nous donnons par ailleurs une généralisation du "coefficient d'ergodicité de Dobrushin" à des opérateurs de Markov sur un cône général. Nous appliquons ces résultats aux systèmes de consensus ainsi qu'aux équations de Riccati généralisées apparaissant en contrôle stochastique.
Fichier principal
Vignette du fichier
thesis.pdf (5.51 Mo) Télécharger le fichier
Loading...

Dates and versions

pastel-00927122 , version 1 (11-01-2014)

Identifiers

  • HAL Id : pastel-00927122 , version 1

Cite

Zheng Qu. Nonlinear Perron-Frobenius theory and max-plus numerical methods for Hamilton-Jacobi equations. Optimization and Control [math.OC]. Ecole Polytechnique X, 2013. English. ⟨NNT : ⟩. ⟨pastel-00927122⟩
616 View
1145 Download

Share

Gmail Facebook Twitter LinkedIn More