Lexikon der Mathematik: Ellipsoidmethoden
Die Ellipsoidmethoden bilden eine Klasse von Verfahren zur Lösung linearer (und konvexer) Optimierungsprobleme. Grundidee ist dabei die folgende: Zunächst wird das Optimierungsproblem umformuliert als Entscheidungsproblem, ob ein Polyeder
Dabei werden ein primales Problem
Die Äquivalenz der Aufgabe, für dieses Problem einen zulässigen Punkt zu finden, zur ursprünglichen Optimierungsaufgabe folgt daraus, daß die DualitätslückecT · x − bT · y nur in Extremalpunkten verschwindet, aber sonst positiv ist.
Das eigentliche Verfahren beginnt nun mit der Konstruktion eines speziellen Ellipsoids E0 = (z0, B0). Dabei heißt eine Teilmenge E(z, B) des ℝn ein (spezielles) Ellipsoid mit Mittelpunkt z ∈ ℝn, falls sie in der Form
Nun wird schrittweise eine Familie {Ei(zi, Bi)}i, 1 ≤ i ≤ s von Ellipsoiden konstruiert, die folgende Eigenschaften erfüllt:
Zur Konstruktion von Ei+1 aus Ei betrachtet man den Mittelpunkt zi von Ei und prüft, ob zi ∈ P. Falls dies zutrifft, so ist das Entscheidungsproblem positiv beantwortet. Andernfalls findet man eine Ungleichung \({a}_{j}^{T}\cdot x\le {b}_{j}\) von P, die von zi verletzt wird. Nun wird die Hyperebene \(\{x|{a}_{j}^{T}\cdot x={b}_{j}\}\) in Richtung des Halbraums \(\{x|{a}_{j}^{T}\cdot x\ge {b}_{j}\}\) parallel verschoben, bis sie Ei noch in einem Punkt Pi tangiert. Man wählt dann z. B. Ei+1 als dasjenige Ellipsoid minimalen Volumens, das
Das Verfahren wird fortgesetzt, bis man entweder einen Mittelpunkt z ∈ P findet oder garantieren kann, daß P = ∅ ist. Letzteres gelingt durch einen Vergleich des Volumens der Ellipsoide Ei mit einer Abschätzung des Mindestvolumens von P ∩ E0.
Wesentliche historische Bedeutung kommt den Ellipsoidverfahren deswegen zu, weil sie die ersten Polynomzeitverfahren für die lineare Programmierung im Turingmodell waren. Dabei betrachtet man solche Probleme, die nur aus rationalen Eingabedaten bestehen. Ohne Einschränkung nimmt man hier an, das Ausgangssystem bestehe sogar nur aus ganzzahligen Daten (was nach Multiplikation des Systems mit dem gemeinsamen Hauptnenner aller rationalen Daten erreicht werden kann).
Nun betrachtet man statt A ⋅ x ≤ b ein System strikter Ungleichungen
Trotz seiner Überlegenheit gegenüber der Simplexmethode im worst-case-Verhalten zeigten praktische Versuche, daß die Ellipsoidmethode i. allg. nicht effizienter als die Simplexmethode ist und numerische Instabilitäten zeigt. Dies hat die Suche nach weiteren Verfahren initiiert, die sowohl theoretisch mit polynomialem Aufwand (im Turingmodell) arbeiten, als auch praktisch schnell ausführbar sind. Als Ergebnis dieser Suche stehen heute innerePunkte Methoden im Zentrum des Interesses.
Abschließend sei bemerkt, daß es keine Funktion nur in der geometrischen Dimension n · m eines linearen Optimierungsproblems {x|A · x ≤ b, A ∈ ℝm×n} gibt, die die Anzahl der arithmetischen Operation der bekannten Ellipsoidmethoden nach oben beschränkt. Ellipsoidverfahren sind daher nicht polynomial in algebraischen Rechenmodellen (Ergebnis von Traub und Wozniakowski (1982)).
[1] Grötschel, M.; Lovasz, L.; Schrijver, A.: Geometrie Algorithms and combinatorial optimization. Springer-Verlag Heidelberg, 1988.
[2] Khachiyan, L.G.: A polynomial algorithm in linear programming. Soviet Mathematics Doklady 20, 1979.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.