Ellipsoidmethode

Die Ellipsoidmethode ist ein polynomialer Algorithmus zur Linearen Optimierung. Sie wurde ursprünglich in den Jahren 1976 und 1977 von David Yudin und Arkadi Nemirovski und unabhängig davon von Naum Shor zur Lösung konvexer Optimierungsprobleme entwickelt. Im Jahre 1979 wurde sie vom russischen Mathematiker Leonid Khachiyan zum ersten polynomialen Algorithmus zur Lösung linearer Programme erweitert. Damit bewies er erstmals die polynomiale Lösbarkeit linearer Optimierungsprobleme. Für praktische Zwecke ist die Ellipsoidmethode allerdings nicht geeignet.
Die Ellipsoidmethode ist ein Algorithmus zur Entscheidung, ob ein volldimensionales Polyeder der Form P={x∈Rn  ∣  Ax≤b} P = \{x \in \mathbb{R}^n \;|\; A x \leq b\}, wobei AA eine reelle m×nm \times n-Matrix und x,bx,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.
Ellipsoid-method.png
Zwei Iterationen der Ellipsoidmethode
Der Algorithmus funktioniert folgendermaßen:
  1. Es wird ein Ellipsoid (im Bild rot) bestimmt, welches - falls PP (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 PP 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 AA und bb bestimmen.
  2. Bestimmung einer maximalen Iterationsanzahl für folgende Schritte:
  3. Es wird getestet, ob das Zentrum zz (im Bild der rote Punkt) des Ellipsoids im Polyeder liegt (also Az≤b A z \leq b)
  4. Falls ja, wird zz ausgegeben und der Algorithmus ist beendet.
  5. Falls nein, sucht man eine Ungleichung (Schnittebene), die zz vom Polyeder trennt. Dies kann zum Beispiel eine Zeile aia_i der Matrix AA sein, die aiz>bi a_i z > b_i erfüllt.
  6. In dem Halbraum {x∈Rn  ∣  ai(x−z)≤0} \{x\in R^n \;|\; a_i (x-z) \leq 0\} liegt, falls das Polyeder nicht leer ist, ein Punkt von PP. 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 AA und des Vektors bb. Dieses Abbruchkriterium beruht darauf, dass das untersuchte Polyeder eine Mindestgröße haben muss, die von der Kodierungslänge von AA und bb abhängt. Wird diese Mindestgröße vom aktuellen Ellipsoid unterschritten, muss das Polyeder leer sein.
Siehe auch: Simplex-Verfahren
 
 

Im großen Garten der Geometrie kann sich jeder nach seinem Geschmack einen Strauß pflücken.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Ellipsoidmethode aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Optimierung