Arc-Search Techniques for Interior-Point Methods
Dieses Buch behandelt ein wichtiges Gebiet der numerischen Optimierung, die sogenannte Interieur-Punkt-Methode. Dieses Thema ist seit den 1980er Jahren populär, als man allmählich erkannte, dass nicht alle Simplex-Algorithmen in polynomialer Zeit konvergieren, während für viele Interieur-Punkt-Algorithmen bewiesen werden konnte, dass sie in polynomialer Zeit konvergieren.
Allerdings klaffte lange Zeit eine deutliche Lücke zwischen den theoretischen Polynomschranken der Interieur-Punkt-Algorithmen und der Effizienz dieser Algorithmen. Strategien, die für die Berechnungseffizienz wichtig waren, wurden zu Hindernissen beim Nachweis guter Polynomschranken. Je mehr Strategien in den Algorithmen verwendet wurden, desto schlechter wurden die polynomiellen Schranken.
Um das Problem weiter zu verschärfen, verwendet Mehrotras Prädiktor-Korrektor-Algorithmus (MPC), der bis vor kurzem der populärste und effizienteste Interieur-Punkt-Algorithmus war, alle guten Strategien und kann die Konvergenz nicht beweisen.
Daher hat MPC keine Polynomialität, was bei der Simplex-Methode ein kritisches Problem darstellt. In diesem Buch werden die jüngsten Entwicklungen erörtert, die dieses Dilemma auflösen.
Es besteht aus drei Hauptteilen. Der erste Teil, der die Kapitel 1, 2, 3 und 4 umfasst, stellt einige der wichtigsten Algorithmen während der Entwicklung der Interieur-Punkt-Methode in den 1990er Jahren vor, von denen die meisten weithin bekannt sind. Der Hauptzweck dieses Teils besteht darin, das oben beschriebene Dilemma zu erklären, indem die polynomiellen Schranken dieser Algorithmen analysiert und die mit ihnen verbundenen Berechnungserfahrungen zusammengefasst werden.
Der zweite Teil, der die Kapitel 5, 6, 7 und 8 umfasst, beschreibt die schrittweise Lösung des Dilemmas mit Hilfe von Arc-Search-Techniken. Am Ende dieses Teils wird ein sehr effizienter Algorithmus mit der niedrigsten polynomiellen Schranke vorgestellt. Der letzte Teil, der die Kapitel 9, 10, 11 und 12 umfasst, erweitert die Arc-Search-Techniken auf einige allgemeinere Probleme, wie konvexe quadratische Programmierung, lineare Komplementaritätsprobleme und semi-definite Programmierung.
| ISBN: | 9780367510091 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
| Erscheinungsjahr: | 2022 |
| Seitenzahl: | 306 |
Derzeit verfügbar, auf Lager.
