Ellipsoidmethode

Die Ellipsoidmethode i​st ein polynomialer Algorithmus z​ur Linearen Optimierung. Sie w​urde ursprünglich i​n den Jahren 1976 u​nd 1977 v​on David Yudin u​nd Arkadi Nemirovski u​nd unabhängig d​avon von Naum Schor z​ur Lösung konvexer Optimierungsprobleme entwickelt. Im Jahre 1979 w​urde sie v​om russischen Mathematiker Leonid Khachiyan z​um ersten polynomialen Algorithmus z​ur Lösung linearer Programme erweitert. Damit bewies e​r erstmals d​ie polynomiale Lösbarkeit linearer Optimierungsprobleme. Für praktische Zwecke i​st die Ellipsoidmethode allerdings n​icht geeignet, d​a sie d​em Simplex-Verfahren numerisch i​n der Praxis w​eit unterlegen ist.

Die Ellipsoidmethode ist ein Algorithmus zur Entscheidung, ob ein volldimensionales Polyeder der Form ${\displaystyle P=\{x\in \mathbb {R} ^{n}\;|\;Ax\leq b\}}$, wobei ${\displaystyle A}$ eine reelle ${\displaystyle m\times n}$-Matrix und ${\displaystyle x,b}$ dimensionskompatible Vektoren sind, leer ist oder nicht. Falls das Polyeder einen Punkt enthält, dann gibt die Methode auch einen solchen aus. Man kann zeigen, dass dieses Problem äquivalent zum Finden der Optimallösung eines linearen Programms ist.

Zwei Iterationen der Ellipsoidmethode

Der Algorithmus funktioniert folgendermaßen:

1. Es wird ein Ellipsoid (im Bild rot) bestimmt, welches – falls ${\displaystyle P}$ (im Bild blau) nicht leer ist – einen Punkt des Polyeders enthält. Man kann dabei eine hinreichend große Kugel wählen, die alle möglichen Ecken von ${\displaystyle P}$ enthalten muss. Deren maximale Koordinaten und damit der notwendige Radius der Kugel lässt sich durch Lösung von linearen Gleichungssystemen mit Einträgen aus ${\displaystyle A}$ und ${\displaystyle b}$ bestimmen.
2. Bestimmung einer maximalen Iterationsanzahl für folgende Schritte:
3. Es wird getestet, ob das Zentrum ${\displaystyle z}$ (im Bild der rote Punkt) des Ellipsoids im Polyeder liegt (also ${\displaystyle Az\leq b}$)
4. Falls ja, wird ${\displaystyle z}$ ausgegeben und der Algorithmus ist beendet.
5. Falls nein, sucht man eine Ungleichung (Schnittebene), die ${\displaystyle z}$ vom Polyeder trennt. Dies kann zum Beispiel eine Zeile ${\displaystyle a_{i}}$ der Matrix ${\displaystyle A}$ sein, die ${\displaystyle a_{i}z>b_{i}}$ erfüllt.
6. In dem Halbraum ${\displaystyle \{x\in R^{n}\;|\;a_{i}(x-z)\leq 0\}}$ liegt, falls das Polyeder nicht leer ist, ein Punkt von ${\displaystyle P}$. Nun sucht man ein Ellipsoid (im Bild grün), das möglichst klein ist, aber den Schnitt dieses Halbraums mit dem ursprünglichen Ellipsoid enthält.
7. Ist die maximale Iterationszahl erreicht, ohne dass ein Ellipsoidzentrum im Polyeder lag, ist dieses leer. Andernfalls macht man wieder bei 3. weiter.

Die maximale Iterationsanzahl berechnet sich polynomial aus der Länge der Binärcodierung der Matrix A und des Vektors b. Dieses Abbruchkriterium beruht darauf, dass das untersuchte Polyeder eine Mindestgröße haben muss, die von der Kodierungslänge von ${\displaystyle A}$ und ${\displaystyle b}$ abhängt. Wird diese Mindestgröße vom aktuellen Ellipsoid unterschritten, muss das Polyeder leer sein.

Literatur

• Korte, Bernhard; Vygen, Jens: Kombinatorische Optimierung, Springer Berlin Heidelberg, 2008. ISBN 978-3-540-76918-7, S. 79–107