Analyse lisse d'algorithme
# Analyse lisse d'algorithme

En informatique théorique, l'analyse lisse d'algorithme (smoothed analysis) est une manière de mesurer la complexité d'un algorithme, c'est-à-dire ses performances. Elle complète et améliore les mesures classiques de complexité : la complexité dans le pire des cas, la complexité en moyenne et la complexité amortie. Elle a été inventée dans les années 2000 par Daniel Spielman et Shang-Hua Teng.

## Motivations pour une nouvelle mesure de complexité

L'introduction de cette nouvelle mesure de complexité a été motivée, d'une part par l'existence de certains algorithmes fonctionnant très bien en pratique mais dont l'analyse dans le pire des cas ne montrait pas l'efficacité, et d'autre part par la difficulté de l'analyse en moyenne en général.

## Principe

Le principe de l'analyse lisse est de mesurer les performances de l'algorithme sur les pires cas, mais avec une légère perturbation des instances. On calcule donc une espérance de performance. D'une certaine manière, c'est une méthode « locale ».

Plus précisément, on ajoute un bruit gaussien aux entrées, c'est-à-dire une variation aléatoire des données qui suit une loi normale. La complexité mesurée dépend alors de deux paramètres : la taille de l'entrée mais aussi l'écart-type de la gaussienne utilisée.

Si l'analyse lisse annonce pour un algorithme de bonnes performances parmi l'espace des valeurs centrées autour d'une donnée en ajoutant du bruit (gaussien) à cette donnée, cela signifie que, dans la pratique, il devrait y avoir aussi de bonnes performances pour cet algorithme dans tous les cas.

### Comparaison avec les autres analyses de complexité

Conceptuellement, l'analyse lisse se place entre l'analyse de la complexité dans le pire cas, puisque l'on s’intéresse aux pires performances, et l'analyse de la complexité moyenne, puisque l'on considère une perturbation aléatoire.

Cette méthode ne peut pas toujours être facilement mise en pratique : il faut pouvoir définir une perturbation gaussienne, ce qui est assez naturel pour le cas de l'optimisation linéaire par exemple, mais l'est beaucoup moins pour d'autres problèmes plus combinatoires.

## Applications

### Le cas du simplexe

L'une des applications majeures de l'analyse lisse est une démonstration de l'efficacité du simplexe, un algorithme utilisé en optimisation linéaire et connu pour son efficacité pratique et pour sa complexité exponentielle dans le pire cas. Il a été démontré que la complexité lisse du simplexe est polynomiale (Spielman et Teng 2004).

Plus précisément, un problème d'optimisation linéaire s'écrit sous la forme :

$\left\{{\begin{array}{l}{\max }_{x}\;c^{\top }x\\Ax\leqslant b.\end{array}}\right.$

On s’intéresse alors à des instances du problème de la forme

$\left\{{\begin{array}{l}{\max }_{x}\;c^{\top }x\\{\tilde {A}}x\leqslant {\tilde {b}}.\end{array}}\right.$

où la matrice ${\tilde {A}}$ et le vecteur ${\tilde {b}}$ sont les résultats d'une perturbation gaussienne de $A$ et $b$, d'écart-type $\sigma \max(a_{ij},b_{j})$.

Le maximum sur $A$, $b$, et $c$, de l'espérance du temps de calcul du simplexe sur ${\tilde {A}}$ et le vecteur ${\tilde {b}}$, est polynomiale en la taille de $A$ et en $1/\sigma$.

Il avait été démontré précédemment que le simplexe a une complexité polynomiale en espérance (pour plusieurs distributions naturelles des instances).

### Autres applications

L'analyse lisse a entre autres été utilisée dans les domaines de l'apprentissage automatique (par exemple pour le problème des k-moyennes et dans le cadre de l'apprentissage PAC) et de l'exploration de données.

En algorithmique plus classique elle a permis une nouvelle approche de certains algorithmes connus, comme le pivot de Gauss ou le tri $rapide^,.$

## Histoire

L'analyse lisse a été inventée en 2000 par Daniel Spielman et Shang-Hua Teng (Spielman et Teng 2004). Pour cela, ils ont reçu le prestigieux prix Gödel 2008 et le prix Fulkerson 2009. Spielman a aussi reçu le prix Nevanlinna en 2010, pour ses travaux sur l'analyse lisse.

Le nom smoothed analysis a été proposé par Alan $Edelman^,.$

