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]

David B. Judin (en), Arkadi Nemirovski (de), Leonid Khachiyan (en), 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[1],[2],[3],[4].

Principe[modifier | modifier le code]

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

  1. D. B. Judin et Arkadi Nemirovski, « Informational complexity and effective methods of solution for convex extremal problems », Ekonomika i Matematicheskie Metody, vol. 12,‎ 1976, p. 357–369.
  2. Leonid Khachiyan, « A polynomial algorithm in linear programming », Akademiia Nauk SSSR. Doklady, vol. 244,‎ 1979, p. 1093–1096.
  3. « Leonid Khachiyan, professor, leading computer scientist », Boston Globe,‎ 5 mai 2005 (lire en ligne).
  4. Martin Grötschel, László Lovász et Alexander Schrijver, « The ellipsoid method and its consequences in combinatorial optimization », Combinatorica, vol. 1,‎ 1981, p. 169–197.