Abstract FR:

Cette these presente quatre types d'acceleration pour les algorithmes d'optimisation stochastiques classiques tels que les dynamiques de metropolis ou de glauber. Toutes sont basees sur l'idee de reduire la taille de l'espace des etats actifs de chaque phase de l'algorithme. Dans la premiere partie, on s'interesse au recuit simule avec des schemas de temperature triangulaires geometriques decroissants, constants par paliers. On montre que de tels schemas permettent d'obtenir l'exposant optimal pour la vitesse de convergence. Dans la seconde partie, on construit un algorithme markovien potentiellement parallele, appele algorithme multi-resolution. Il utilise des tentatives locales et multiples de l'algorithme de metropolis. En jouant sur le nombre de tentatives (resp. La taille des fenetres de localisation), on peut abaisser la barriere de potentiel locale (resp. Globale). Dans la troisieme partie, on se place sur un espace hierarchisable en plusieurs niveaux de resolution. On definit un algorithme markovien, appele algorithme hierarchique, pour lequel chaque recherche basse resolution est validee par une optimisation a haute resolution. Cet algorithme echantillonne partiellement la loi de gibbs. C'est un pre-traitement de l'algorithme de metropolis standard. On calcule un gain de temps effectif sur le probleme de meta-stabilite du modele d'ising. La quatrieme partie, experimentale, accompagne l'etude theorique faite sur les algorithmes precedents. On illustre leurs performances pour la restauration de sequences video corrompues par un bruit gaussien. On propose un modele de reconstruction dichotomique des lignes de niveaux introduit par o. Catoni, prenant en compte un bruit gaussien et les correlations temporelles.