École Nationale Supérieure de
Techniques Avancées

Abstract

Le pire cas d'un algorithme n'est souvent pas représentatif de ses performances effectives. Comme il est parfois difficile d'obtenir la répartition exacte des cas d'entrée d'un algorithme pour calculer le cas moyen, une nouvelle approche (voir \cite{spielman2009smoothed}) préconise d'étudier le pire cas (ici, la pire fonction objectif) modifié par une perturbation pertinente. Nous avons appliqué cette méthode à l'algorithme du gradient afin d'observer si sa complexité décroît significativement. Nous fournissons plusieurs procédés permettant de perturber la fonction de pire cas de l'algorithme du gradient, ce qui fait appel à des outils d'optimisation discrète. Finalement, nous calculons de nouvelles valeurs et de nouveaux encadrements caractérisant l'efficacité de l'algorithme du gradient grâce à ces différentes méthodes.