Skip to Main content Skip to Navigation

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

Zheng Qu 1, 2 
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
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.
Document type :
Complete list of metadata

Cited literature [134 references]  Display  Hide  Download
Contributor : Zheng Qu Connect in order to contact the contributor
Submitted on : Saturday, January 11, 2014 - 12:27:19 AM
Last modification on : Thursday, January 20, 2022 - 4:12:20 PM
Long-term archiving on: : Friday, April 11, 2014 - 10:30:14 PM


  • HAL Id : pastel-00927122, version 1



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. ⟨pastel-00927122⟩



Record views


Files downloads