S. Gaubert
3-4 Décembre 1997, Groupe de Travail Algèbres Tropicales
Synthèse de travaux joints avec Jean Cochet-Terrasson, Jeremy Gunawardena, et Max Plus.
L'algorithme d'itération sur les politiques a été introduit par Howard dans les années 50 pour résoudre les équations de Hamilton-Jacobi-Bellman associées à des problèmes variés de commande optimale stochastique.
Il s'agit d'un outil à (presque) tout faire, qui permet de résoudre de manière très efficace des classes d'équations satisfaisant certaines propriétés de monotonie analogues au ``principe du maximum'' classique.
Après avoir rappelé les résultats standards, nous visiterons les variantes de cet algorithme pertinentes dans le cas des divers problèmes spectraux et problèmes de point-fixe sur le semi-anneau max-plus.
Pour le problème spectral max-plus linéaire de base, une simple adaptation de l'algorithme de Howard ``multichaine'' (valable pour les problèmes de commande stochastique avec coût moyen et classes finales multiples), accompagnée de quelques remarques de théorie des graphes, permet de déterminer vecteur propre et valeur propre en temps moyen quasiment linéaire, en pratique.
Grâce aux versions ``semi-Markov'' de l'algorithme de Howard, il n'est pas plus cher de calculer le valeurs propres et vecteurs propres généralisées, pour des systèmes dynamiques max-plus linéaires à retards incommensurables.
Nous présenterons ensuite les extensions
de cette classe d'algorithmes aux fonctions
min-max. Cette classe de fonctions,
a été introduite par Olsder
et Gunawardena. Une ``fonction min-max'' est
une application de 
dans ,
additivement homogène, dont les composantes
s'écrivent finiment avec les lois 
et les variables.
Des systèmes dynamiques de la forme x(k)=f(x(k-1)),
où f est une fonction min-max, apparaissent
bien-sûr pour des problèmes de jeux, mais aussi
pour modéliser le comportement temporel
de systèmes à événements discrets
(e.g. circuits digitaux asynchrones).
Comme dans le cas max-plus de base,
on veut calculer le ``temps de cycle'' 
,
et dans ce cas, prouver son existence, qui est non banale.
Une nouvelle version de l'algorithme de Howard, couplée à un analogue max-plus du principe du maximum, permet de calculer efficacement ce temps de cyle, et de montrer, en passant, la conjecture de dualité, proposée par J. Gunawardena en 94 (qui affirme que la fonction temps de cycle est un morphisme de treillis, en un sens spécial).
Au dela des fonctions min-max, ces techniques permettent de déterminer l'asymptotique de classes plus larges de systèmes dynamiques monotones additivement homogènes.