| dbo:abstract
|
- 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 Schor 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, da sie dem Simplex-Verfahren numerisch in der Praxis weit unterlegen ist. Die Ellipsoidmethode ist ein Algorithmus zur Entscheidung, ob ein volldimensionales Polyeder der Form , wobei eine reelle -Matrix und 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. Der Algorithmus funktioniert folgendermaßen: 1.
* Es wird ein Ellipsoid (im Bild rot) bestimmt, welches – falls (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 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 und bestimmen. 2.
* Bestimmung einer maximalen Iterationsanzahl für folgende Schritte: 3.
* Es wird getestet, ob das Zentrum (im Bild der rote Punkt) des Ellipsoids im Polyeder liegt (also ) 4.
* Falls ja, wird ausgegeben und der Algorithmus ist beendet. 5.
* Falls nein, sucht man eine Ungleichung (Schnittebene), die vom Polyeder trennt. Dies kann zum Beispiel eine Zeile der Matrix sein, die erfüllt. 6.
* In dem Halbraum liegt, falls das Polyeder nicht leer ist, ein Punkt von . 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 und abhängt. Wird diese Mindestgröße vom aktuellen Ellipsoid unterschritten, muss das Polyeder leer sein. (de)
- In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function. (en)
- En optimisation mathématique, la méthode de l'ellipsoïde est une méthode itérative utilisée pour minimiser des fonctions convexes. En informatique théorique, cette méthode est connue comme étant le premier algorithme de complexité polynomiale découvert pour résoudre les problèmes d'optimisation linéaire. L'algorithme construit une suite d'ellipsoïdes de plus en plus petits, qui enserrent à chaque étape le minimum de la fonction objectif. (fr)
- Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств. Разработан А. С. Немировским и доведён до алгоритмической реализации Л. Г. Хачияном в ВЦ АН СССР. (ru)
|
| rdfs:comment
|
- In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function. (en)
- En optimisation mathématique, la méthode de l'ellipsoïde est une méthode itérative utilisée pour minimiser des fonctions convexes. En informatique théorique, cette méthode est connue comme étant le premier algorithme de complexité polynomiale découvert pour résoudre les problèmes d'optimisation linéaire. L'algorithme construit une suite d'ellipsoïdes de plus en plus petits, qui enserrent à chaque étape le minimum de la fonction objectif. (fr)
- Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств. Разработан А. С. Немировским и доведён до алгоритмической реализации Л. Г. Хачияном в ВЦ АН СССР. (ru)
- 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 Schor 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, da sie dem Simplex-Verfahren numerisch in der Praxis weit unterlegen ist. (de)
|
