Voir la source de Méthode de l'ellipsoïde

[[Fichier:Ellipsoid-method.png|vignette|Montre un polytope de programmation linéaire (bleu) ainsi que deux itérations de la méthode ellipsoïde utilisée pour déterminer un point dans le polytope.]]
En [[Optimisation (mathématiques)|optimisation mathématique]], la '''méthode de l'ellipsoïde''' est une [[méthode itérative]] utilisée pour minimiser des [[fonction convexe|fonctions convexes]]. En [[informatique théorique]], cette méthode est connue comme étant le premier [[algorithme]] de [[P (complexité)|complexité polynomiale]] découvert pour résoudre les problèmes d'[[optimisation linéaire]].

L'algorithme construit une suite d'[[Ellipsoïde|ellipsoïdes]] de plus en plus petits, qui enserrent à chaque étape le minimum de la [[fonction objectif]].

== Histoire ==
Depuis son invention par [[George Dantzig]] en 1947, la [[Algorithme du simplexe|méthode du simplexe]] avait relégué un certain nombre d'[[heuristique]]s antérieures pour résoudre les problèmes d'affectation sous [[Contrainte (mathématiques)|contrainte]]s 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 {{Lien|lang=de|George Minty}} 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<ref name=Klee-Minty>Le problème du cube déformé de Klee-Minty a été publié dans {{Ouvrage|prénom1=Victor|nom1=Klee|prénom2=George&nbsp;J.|nom2=Minty|nom3=Shisha Oved|directeur3=Shisha Oved|titre=Inequalities&nbsp;III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September&nbsp;1–9,&nbsp;1969|lieu=New York et Londres|éditeur=[[Academic Press]]|année=1972|pages totales=159–175|isbn=|math reviews=332165|titre chapitre=How good is the simplex algorithm?}}</ref>.

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, [[Naum Z. Shor|Nahum Chor]] (1976–77) ; un mathématicien arménien, [[Leonid Khatchian|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'' ({{date-|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'{{date-|août 1979}}, puis grâce à un article de Peter Gács et László Lovász<ref name=Gács>Cf. {{article|nom1=P. Gács|nom2= L. Lovász|titre=Khachiyan’s algorithm for linear programming|journal=Math. Programming Studies|numéro= 14|pages= 61–68|année= 1981}}.</ref>, qui évitait les changements continuels de systèmes de coordonnées familiers aux mathématiciens russes. Enfin, dans un article publié en 1980, Khatchian publia ses démonstrations<ref name=polynomial>{{article|auteur=L. G. Khatchian|journal=USSR Computational Mathematics and Mathematical Physics|volume=20|numéro= 1|année= 1980|pages=53-72|titre=Polynomial algorithms in linear programming|doi=10.1016/0041-5553(80)90061-0}}</ref>.

{{Lien|trad=David Borissowitsch Judin|fr=David B. Youdine|lang=de}}, [[Arkadi Nemirovski]], [[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{{refm|1982a|1982b|1982c|1982d}}.

== Principe ==
On cherche à optimiser une fonction <math>f(x): \mathbb{R}^n \to \mathbb{A}</math> d'une manière à trouver au moins un point <math>x^\star \in \mathbb{R}^n</math> satisfaisant un ensemble de contrainte. (Pour une fonction à valeur réelle, on peut chercher un point tel que <math>f(x^\star)</math> soit positif par exemple.)

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'à chaque étape le volume de l'ellipsoïde est divisé par un facteur au moins <math>\frac{n}{n-1}</math>, donc aymptotiquement par [[e (nombre)|{{math|e}}]] après <math>n</math> étapes.

== Description de l'algorithme ==

=== Optimisation convexe sans contrainte ===
On se donne une fonction [[Fonction convexe|convexe]] <math>f:\mathbb{R}^n\rightarrow\mathbb{R}</math>, que l'on cherche à minimiser. On décrit une ellipsoïde <math>\mathcal{E}</math> par son centre ''y'' et une [[matrice symétrique]] définie positive ''A'', afin que :

<math>\mathcal{E}=\{z\in\mathbb{R}^n|(z-y)^TA^{-1}(z-y)\leq1\}</math>.

On suppose que l'on dispose d'une ellipsoïde initiale <math>\mathcal{E}_0</math> contenant <math>x^*</math>, et que l'on peut déterminer un [[sous-gradient]] de ''f'' en tout point. La suite d'ellipsoïdes se construit alors par récurrence. Si <math>\mathcal{E}_k</math> a pour centre <math>x_k</math> et pour matrice <math>A_k</math>, on pose <math>s_k</math> un sous-gradient de ''f'' en <math>x_k</math>. Alors :

<math>s_k^T(x^*-x_k)\leq f(x^*)-f(x_k)\leq0</math>.

Par conséquent <math>x^*\in\mathcal{F}_k:=\mathcal{E}_k\cap\{z\in\mathbb{R}^n|s_k^T(z-x_k)\leq0\}</math>. On pose alors :

<math>t_k=\left(\dfrac{1}{\sqrt{s_k^TA_ks_k}}\right)s_k</math>

ce qui permet de calculer l'ellipsoïde contenant <math>\mathcal{F}_k</math> de volume minimal :

<math>x_{k+1}=x_k-\dfrac{1}{n+1}A_kt_k</math>

<math>A_{k+1}=\dfrac{n^2}{n^2-1}\left(A_k-\dfrac{2}{n+1}A_kt_kt_k^TA_k\right)</math>.

=== Optimisation linéaire ===
On considère une famille finie d'inégalités de la forme <math>a_i^Tx<b_i</math>, avec <math>(a_i)</math> une famille de vecteurs à coordonnées entières et <math>(b_i)</math> une famille d'entiers. On cherche à déterminer l'existence d'un <math>x\in\mathbb{R}^n</math> vérifiant ces contraintes. L'algorithme est alors comparable au cas de l'optimisation convexe. L'ellipsoïde initiale est déterminée par <math>x_0=0</math> et <math>A_0=2^LI_n</math>, avec ''L'' la taille en mémoire des paramètres du problème. À l'étape ''k'', soit <math>x_k</math> vérifie toutes les contraintes auquel cas l'algorithme s'arrête, soit l'une des inégalités n'est pas vérifiée, c'est-à-dire <math>a_i^Tx\geq b_i</math>. On définit alors l'ellipsoïde avec les mêmes formules que dans le cas de la minimisation convexe, en posant <math>s_k=a_i</math>. Si le problème a une solution, l'algorithme s'arrête en moins de <math>6n^2L</math> étapes<ref name="Gács" />.

On peut alors résoudre un problème d'optimisation linéaire en cherchant l'existence d'une solution [[Optimisation linéaire#Conditions d'optimalité|primale-duale]] au problème<ref name="Gács" />.

== Illustration ==
{{...}}

== Performances ==
C'était le premier algorithme qui garantissait la résolution d'un programme linéaire en [[P (complexité)|temps polynomial]] mais reste assez lente en pratique.

== Notes et références ==
{{Crédit d'auteurs|interne|Équilibres et jeux matriciels|122504308}}
{{Références|colonnes=2|références= 
<ref name=1982a>
{{article|prénom1=D. B.|nom1=Judin|prénom2=Arkadi|nom2=Nemirovski|titre=Informational complexity and effective methods of solution for convex extremal problems|journal=Ekonomika i Matematicheskie Metody|volume=12|numéro=|pages=357–369|année=1976}}.</ref>

<ref name=1982b>
{{article|prénom1=Leonid|nom1=Khachiyan|prénom2=|nom2=|titre=A polynomial algorithm in linear programming|journal=Akademiia Nauk SSSR. Doklady|volume=244|numéro=|pages=1093–1096|année=1979}}.</ref>

<ref name=1982c>
{{article|périodique=[[Boston Globe]]|url=http://www.boston.com/news/globe/obituaries/articles/2005/05/05/leonid_khachiyan_professor_leading_computer_scientist/|jour=5|mois=mai|année=2005|titre=Leonid Khachiyan, professor, leading computer scientist}}.</ref>

<ref name=1982d>
{{article |prénom1=Martin|nom1=Grötschel |prénom2=László|nom2=Lovász|prénom3=Alexander |nom3=Schrijver|titre=The ellipsoid method and its consequences in combinatorial optimization|journal=Combinatorica|volume=1|numéro=|pages=169–197|année=1981}}.</ref>
}}
{{Palette|Optimisation}}
{{Portail|analyse|informatique théorique}}
[[Catégorie:Recherche opérationnelle]]
[[Catégorie:Algorithme d'optimisation|Ellipsoide]]