Analyse lisse d'algorithme

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.

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 :

${\displaystyle \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

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

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

Le maximum sur ${\displaystyle A}$, ${\displaystyle b}$, et ${\displaystyle c}$, de l'espérance du temps de calcul du simplexe[2] sur ${\displaystyle {\tilde {A}}}$ et le vecteur ${\displaystyle {\tilde {b}}}$, est polynomiale en la taille de ${\displaystyle A}$ et en ${\displaystyle 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)[3].

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[4] et dans le cadre de l'apprentissage PAC[5]) et de l'exploration de données[6].

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

• Daniel A. Spielman et Shang-Hua Teng, « Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time », Journal of the ACM, vol. 51, n^o 3,‎ 2004, p. 385–463 (lire en ligne)
• Daniel A. Spielman et Shang-Hua Teng, « Smoothed analysis: an attempt to explain the behavior of algorithms in practice », Communications of the ACM, vol. 52, n^o 10,‎ 2009, p. 76–84 (lire en ligne)
• (en) David Arthur, Bodo Manthey et Heiko Roglin, « k-Means Has Polynomial Smoothed Complexity », dans Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2009 (lire en ligne), p. 405--414
• Cyril Banderier, Rene Beier et Kurt Mehlhorn, « Smoothed analysis of three combinatorial problems », Lecture notes in computer science,‎ 2003, p. 198-207 (lire en ligne)
• Arvind Sankar, Daniel Spielman et Shang-Hua Teng, « Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices », SIAM J. Matrix Analysis Applications, vol. 28, n^o 2,‎ 2006, p. 446-476
• (en) Adam Tauman Kalai, Alex Samorodnitsky et Shang-Hua Teng, « Learning and smoothed analysis », dans Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, IEEE Computer Society, 2009, p. 395--404

• Étienne Ghys, « Des événements rares... », Images des Mathématiques,‎ 2010 (lire en ligne)