Analyse d'algorithmes de type Nesterov et leurs applications à l'imagerie numérique

Abstract

Ce mémoire se veut d'abord un recueil des principales variantes de l'algorithme optimal en pire cas pour la résolution de problèmes convexes et fortement convexes sans contraintes présenté par Yurii Nesterov en 1983 et en 2004. Ces variantes seront présentées dans un cadre unifié et analysées de manière théorique et empirique. On y retrouve une analyse des rôles des différents paramètres composant l'algorithme de base ainsi que de l'influence des constantes L et mu, respectivement la constante de Lipschitz du gradient et la constante de forte convexité de la fonction objectif, sur le comportement des algorithmes. On présentera également une nouvelle variante hybride et nous démontrerons empiriquement qu'elle performe mieux que plusieurs variantes dans la majorité des situations. La comparaison empirique des différentes variantes sur des problèmes sans contraintes utilise un modèle de calcul se basant sur le nombre d'appels à un oracle de premier ordre plutôt que sur le nombre d'itérations. Enfin, une application de ces variantes sur trois instances de problèmes en imagerie numérique ainsi qu'une analyse empirique des résultats obtenus en confrontation avec la méthode optimale FISTA et l'algorithme classique L-BFGS-B viennent clore ce mémoire.