Méthode de l'ellipsoïde

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En optimisation mathématique, la méthode de l'ellipsoïde est une méthode itérative utilisée pour minimiser des fonctions convexes. En informatique théorique, cette méthode est connue comme étant le premier algorithme de complexité polynomiale découvert pour résoudre les problèmes d'optimisation linéaire.

L'algorithme construit une suite d'ellipsoïdes de plus en plus petits, qui contiennent le minimum.

Histoire[modifier | modifier le code]

Depuis son invention par George Dantzig en 1947, la méthode du simplexe avait relégué un certain nombre d'heuristiques antérieures pour résoudre les problèmes d'affectation sous contraintes linéaires, en particulier les itérations transposant le problème à une compétition entre deux joueurs. Tout au long des années 1950 et 1960, elle fut appliquée à des problèmes de taille de plus en plus grande jusqu'à ce qu'au début des années 1970, Victor Klee et George Minty (de) mettent en évidence l'existence de programmes pour lesquels l'algorithme de Dantzig conduit à examiner un nombre de pivots croissant exponentiellement avec la taille du problème[1].

La méthode des ellipsoïdes est une technique itérative d'optimisation qui avait été imaginée par David Youdine, Arcadi Nemirovski et, indépendamment, Nahum Chor (1976–77) ; Khatchian tenta de l'utiliser pour résoudre les programmes linéaires mais cela n'allait nullement de soi : l'algorithme exigeait le calcul d'une estimation de la distance à l'optimum ; pour cela, Khatchian établit un certain nombre de majorations sur les volumes de polyèdres, et analysa la précision de calcul requise pour que la méthode soit praticable. Il publia ces résultats sans les démonstrations dans une note de quatre pages des Soviet Mathematics Doklady (février 1979). L'algorithme vint à la connaissance des chercheurs occidentaux lors d'une conférence au Symposium de programmation mathématique de Montréal, au mois d'août 1979, puis grâce à un article de Peter Gács et Laci Lovász[2], qui évitait les changements continuels de systèmes de cordonnées familiers aux mathématiciens russes. Enfin, dans un article publié en 1980, Khatchian publia ses démonstrations[3].

David B. Youdine (en), Arkadi Nemirovski (de), Leonid Khatchian, Martin Grötschel, László Lovász et Alexander Schrijver ont reçu le prix Fulkerson en 1982 pour leurs articles sur la méthode de l'ellipsoïde[4],[5],[6],[7].

Principe[modifier | modifier le code]

Le principe est de commencer avec un ellipsoïde qui contient à coup sûr la région admissible (c'est-à-dire obéissant aux contraintes). Ensuite, on essaye le centre de l'ellipsoïde et on recense les contraintes qui sont enfreintes : s'il n'y en a plus aucune, on a terminé. Dans le cas contraire, on sait que la solution (si elle existe) se trouve dans une partie de l'ellipsoïde limitée par des hyperplans. On construit alors une nouvelle ellipse plus petite qui contient cette partie et on répète l'opération.

On estime qu'on diminue à chaque étape le volume de l'ellipsoïde par au moins un facteur de par rapport à l'ellipsoïde original. Donc, pour chaque n-étape, le volume diminue d'un facteur de .

Illustration[modifier | modifier le code]

Performances[modifier | modifier le code]

C'était le premier algorithme qui garantissait la résolution d'un programme linéaire en temps polynomial mais reste assez lente en pratique.

Notes et références[modifier | modifier le code]

  1. Le problème du cube déformé de Klee-Minty a été publié dans Victor Klee, George J. Minty et Shisha Oved (dir.), Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, New York et Londres, Academic Press, , 159–175 p., « How good is the simplex algorithm? »
  2. Cf. P. Gács et L. Lovász, « Khachiyan’s algorithm for linear programming », Math. Programming Studies, no 14,‎ , p. 61–68.
  3. L. G. Khatchian, « Polynomial algorithms in linear programming », USSR Computational Mathematics and Mathematical Physics, vol. 20, no 1,‎ , p. 53-72 (DOI 10.1016/0041-5553(80)90061-0)
  4. D. B. Judin et Arkadi Nemirovski, « Informational complexity and effective methods of solution for convex extremal problems », Ekonomika i Matematicheskie Metody, vol. 12,‎ , p. 357–369.
  5. Leonid Khachiyan, « A polynomial algorithm in linear programming », Akademiia Nauk SSSR. Doklady, vol. 244,‎ , p. 1093–1096.
  6. « Leonid Khachiyan, professor, leading computer scientist », Boston Globe,‎ (lire en ligne).
  7. Martin Grötschel, László Lovász et Alexander Schrijver, « The ellipsoid method and its consequences in combinatorial optimization », Combinatorica, vol. 1,‎ , p. 169–197.