A max-plus based randomized algorithm for solving a class of HJB PDEs

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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : McEneaney introduced the curse of dimensionality free method for the special class of infinite horizon optimal control problems where the Hamiltonian is represented as a maximum of quadratic affine functions. This method is featured by its cubic complexity with respect to the state space dimension, but the number of basis functions is multiplied by the number of switches at each iteration, referred to as the ’curse of complexity’. In previous works, an SDP-based pruning technique was incorporated into the method in order to reduce the curse of complexity. Its efficiency was proved on many examples. In this paper we develop a new max-plus based randomized algorithm to solve the same class of infinite horizon optimal control problems. The major difference between the new algorithm and the previous SDP-based curse of dimensionality free method is that, instead of adding a large number of functions and then pruning the less useful ones, the new algorithm finds in cheap computation time (linear in the current number of basis functions), by a randomized procedure, useful quadratic functions and adds only those functions to the set of basis functions. Experimental results show that the max- plus randomized algorithm can reach the same precision order obtained by the SDP-based method with a speedup varying from 10 up to 100 and that the maximal precision order attainable by the new algorithm is much better than what can be done by the SDP-based algorithm in reasonable computation time. Besides, with the randomized algorithm we are now able to tackle switched problems with more number of switches, which will allow us to extend the algorithm to more general classes of optimal control problems.
Type de document :
Communication dans un congrès
53rd IEEE Conference on Decision and Control, Dec 2014, Los Angeles, United States. IEEE, pp.1575--1580, 2014, Proceedings of the 53rd IEEE Conference on Decision and Control
Liste complète des métadonnées

https://hal.inria.fr/hal-01112264
Contributeur : Stephane Gaubert <>
Soumis le : lundi 2 février 2015 - 15:19:45
Dernière modification le : jeudi 12 avril 2018 - 01:49:31

Identifiants

  • HAL Id : hal-01112264, version 1

Collections

Citation

Zheng Qu. A max-plus based randomized algorithm for solving a class of HJB PDEs. 53rd IEEE Conference on Decision and Control, Dec 2014, Los Angeles, United States. IEEE, pp.1575--1580, 2014, Proceedings of the 53rd IEEE Conference on Decision and Control. 〈hal-01112264〉

Partager

Métriques

Consultations de la notice

239