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 \begin{eqnarray}P=\{x|A\cdot x\le b\}\end{eqnarray} nicht-leer ist. Dies geschieht durch Anwendung des Dualitätssatzes der linearen Optimierung.

Dabei werden ein primales Problem \begin{eqnarray}{c}^{T}\cdot v\to \min \,,\,\,E\cdot v\ge f,\,\,v\ge 0\end{eqnarray} und das zugehörige duale Problem \begin{eqnarray}{d}^{T}\cdot y\to \max \,,\,\,{E}^{T}\cdot y\le c,\,\,y\ge 0\end{eqnarray} zum System \begin{eqnarray}-E\cdot v\le -f,-v\le 0,\\ {E}^{T}\cdot y\le c,-y\le 0,\\ {c}^{T}\cdot v-{d}^{T}\cdot y\le 0\end{eqnarray} zusammengefaßt. Dies liefert dasP definierende System A · x ≤ b (mit x := (v, y) und entsprechender Festsetzung von A und b).

Die Äquivalenz der Aufgabe, für dieses Problem einen zulässigen Punkt zu finden, zur ursprünglichen Optimierungsaufgabe folgt daraus, daß die Dualitätslücke c^T · x − b^T · y nur in Extremalpunkten verschwindet, aber sonst positiv ist.

Das eigentliche Verfahren beginnt nun mit der Konstruktion eines speziellen Ellipsoids E₀ = (z₀, B₀). Dabei heißt eine Teilmenge E(z, B) des ℝⁿ ein (spezielles) Ellipsoid mit Mittelpunkt z ∈ ℝⁿ, falls sie in der Form \begin{eqnarray}\{x\in {{\mathbb{R}}}^{n}|{(x-z)}^{T}\cdot {B}^{-1}\cdot (x-z)\le 1\}\end{eqnarray} schreibbar ist. Hierbei sei B eine positiv definite (n, n)-Matrix. Das erste Ellipsoid E₀ wird dabei so gewählt, daß es im Fall P ≠ ∅ einen Lösungspunkt von P enthält (s. unten).

Nun wird schrittweise eine Familie {E_i(z_i, B_i)}_i, 1 ≤ i ≤ s von Ellipsoiden konstruiert, die folgende Eigenschaften erfüllt:

Zur Konstruktion von E_i+1 aus E_i betrachtet man den Mittelpunkt z_i von E_i und prüft, ob z_i ∈ 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 z_i 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 E_i noch in einem Punkt P_i tangiert. Man wählt dann z. B. E_i+1 als dasjenige Ellipsoid minimalen Volumens, das \begin{eqnarray}{E}_{i}\cap \{x|{a}_{j}^{T}\cdot x\ge {a}_{j}^{T}\cdot {z}_{i}\}\end{eqnarray} ganz enthält und P_i ebenfalls als Randpunkt mit derselben Tangentialebene wie E_i besitzt. Es läßt sich zeigen, daß E_i+1 durch diese Forderungen eindeutig bestimmt ist. Die neue Matrix B_i+1, die das nächste Ellipsoid festlegt, entsteht dabei durch Störung von B_i mit einer Matrix vom Rang 1.

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 E_i mit einer Abschätzung des Mindestvolumens von P ∩ E₀.

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 \begin{eqnarray}A\cdot x\lt b+{2}^{-L}\cdot e,\end{eqnarray} wobei e = (1, …, 1)^T ist und L die Bitgröße des Ausgangsproblems bezeichnet. Das neue System ist genau dann lösbar, wenn es das alte war. Diese Beziehung zwischen den beiden Systemen basiert wesentlich auf der Ganzzahligkeit der Eingangsdaten und einer dadurch möglichen Abschätzung (nach oben) von der Bitgröße gewisser Lösungen mittels der Cramerschen Regel. Damit läßt sich aus den Ausgangsdaten zum einen ein geeignetes Startellipsoid E₀ mit (P ≠ ∅ ⇒ E₀ ∩ P ≠ ∅) finden; zum anderen kann man eine untere Schranke für das Volumen V der Schnittmenge von E₀ mit der Lösungsmenge \(\mathop{P}\limits^{\sim }\) von A ⋅ x < b + 2^−L · e bestimmen. Man wendet jetzt das Verfahren auf \(\mathop{P}\limits^{\sim }\) an und iteriert solange, bis \begin{eqnarray}\text{vol}({E}_{s})\le {\lambda }^{s}\cdot \text{vol}({E}_{0})\lt V\end{eqnarray} ist (was wegen λ < 1 eintreten muß). In dieser Situation gilt \(\mathop{P}\limits^{\sim }\ne \emptyset\) genau dann, wenn der Mittelpunkt z_s von E_s in \(\mathop{P}\limits^{\sim }\) liegt. Nach dem entsprechenden Test bricht das Verfahren ab. Die speziellen Werte für E₀ und λ beweisen dann die Polynomialität des Verfahrens in Abhängigkeit der Bitgröße der Eingabedaten. Dieser Nachweis der Polynomialität gelang erstmals Khachiyan 1979. Ellipsoidmethoden wurden bereits vorher von Nemirovskiǐ-Yudin und Shor verwendet.

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.