Mehrotra-Prädiktor-Korrektor-Methode – Wikipedia
Mehrotra-Prädiktor-Korrektor-Methode Bei der Optimierung handelt es sich um eine spezielle Innenpunktmethode für die lineare Programmierung. Es wurde 1989 von Sanjay Mehrotra vorgeschlagen.[1]
Das Verfahren basiert auf der Tatsache, dass bei jeder Iteration eines inneren Punktalgorithmus die Cholesky-Zerlegung (Faktorisierung) einer großen Matrix berechnet werden muss, um die Suchrichtung zu finden. Der Faktorisierungsschritt ist der rechenintensivste Schritt im Algorithmus. Daher ist es sinnvoll, dieselbe Zerlegung mehrmals zu verwenden, bevor Sie sie neu berechnen.
Bei jeder Iteration des Algorithmus verwendet die Prädiktor-Korrektor-Methode von Mehrotra dieselbe Cholesky-Zerlegung, um zwei verschiedene Richtungen zu finden: einen Prädiktor und einen Korrektor.
Die Idee ist, zuerst eine optimierende Suchrichtung basierend auf einem Term erster Ordnung (Prädiktor) zu berechnen. Die Schrittgröße, die in diese Richtung genommen werden kann, wird verwendet, um zu bewerten, wie viel Zentralitätskorrektur erforderlich ist. Dann wird ein Korrektorterm berechnet: Dieser enthält sowohl einen Zentralitätsterm als auch einen Term zweiter Ordnung.
Die vollständige Suchrichtung ist die Summe aus Prädiktorrichtung und Korrektorrichtung.
Obwohl noch keine theoretische Komplexität daran gebunden ist, ist die Prädiktor-Korrektor-Methode von Mehrotra in der Praxis weit verbreitet.[2] Sein Korrektorschritt verwendet auf effektive Weise dieselbe Cholesky-Zerlegung, die während des Prädiktorschritts gefunden wurde, und ist daher nur unwesentlich teurer als ein Standard-Innenpunktalgorithmus. Der zusätzliche Aufwand pro Iteration zahlt sich jedoch normalerweise durch eine Verringerung der Anzahl der Iterationen aus, die zum Erreichen einer optimalen Lösung erforderlich sind. Es scheint auch sehr schnell zu konvergieren, wenn es nahe am Optimum liegt.
Ableitung[edit]
Die Ableitung dieses Abschnitts folgt dem Entwurf von Nocedal und Wright.[3]
Prädiktorschritt – Affine Skalierungsrichtung[edit]
Ein lineares Programm kann immer in der Standardform formuliert werden
wo
und
Definieren Sie das Problem mit
Einschränkungen und
Gleichungen während
ist ein Vektor von Variablen.
Die Karush-Kuhn-Tucker (KKT) Bedingungen für das Problem sind
wo
und
woher
.
Diese Bedingungen können als Mapping umformuliert werden
wie folgt
Die Prädiktor-Korrektor-Methode arbeitet dann unter Verwendung der Newton-Methode, um die affine Skalierungsrichtung zu erhalten. Dies wird erreicht, indem das folgende lineare Gleichungssystem gelöst wird
wo
, definiert als
ist der Jakobianer von F.
Somit wird das System
Zentrierschritt[edit]
Der Durchschnittswert der Produkte
ein wichtiges Maß für die Wünschbarkeit eines bestimmten Satzes darstellen
(Die hochgestellten Zeichen bezeichnen den Wert der Iterationsnummer.
der Methode). Dies wird als Dualitätsmaß bezeichnet und ist definiert durch
Für einen Wert des Zentrierungsparameters gilt
Der Zentrierungsschritt kann als Lösung für berechnet werden
Korrekturschritt[edit]
In Anbetracht des Systems, das zur Berechnung der oben definierten affinen Skalierungsrichtung verwendet wird, kann man feststellen, dass ein vollständiger Schritt in der affinen Skalierungsrichtung dazu führt, dass die Komplementaritätsbedingung nicht erfüllt ist:
Als solches kann ein System definiert werden, um einen Schritt zu berechnen, der versucht, diesen Fehler zu korrigieren. Dieses System stützt sich auf die vorherige Berechnung der affinen Skalierungsrichtung.
Aggregiertes System – Richtung des Mittelkorrektors[edit]
Die Prädiktor-, Korrektor- und Zentrierungsbeiträge zur rechten Seite des Systems können zu einem einzigen System zusammengefasst werden. Dieses System hängt von der vorherigen Berechnung der affinen Skalierungsrichtung ab, jedoch ist die Systemmatrix mit der des Prädiktorschritts identisch, so dass ihre Faktorisierung wiederverwendet werden kann.
Das aggregierte System ist
Der Prädiktor-Korrektor-Algorithmus berechnet dann zuerst die affine Skalierungsrichtung. Zweitens löst es das aggregierte System, um die Suchrichtung der aktuellen Iteration zu erhalten.
Adaptive Auswahl des Zentrierparameters[edit]
Die affine Skalierungsrichtung kann verwendet werden, um eine Heuristik zu definieren, mit der der Zentrierungsparameter adaptiv als ausgewählt werden kann
wo
Hier,
ist das Dualitätsmaß des affinen Schrittes und
ist das Dualitätsmaß der vorherigen Iteration.[3]
Schrittlängen[edit]
In praktischen Implementierungen wird eine Version der Zeilensuche durchgeführt, um die maximale Schrittlänge zu erhalten, die in Suchrichtung ausgeführt werden kann, ohne die Nicht-Negativität zu verletzen.
.[3]
Anpassung an die quadratische Programmierung[edit]
Obwohl die von Mehrotra vorgestellten Modifikationen für innere Punktalgorithmen für die lineare Programmierung gedacht waren, wurden die Ideen erweitert und auch erfolgreich auf die quadratische Programmierung angewendet.[3]
Verweise[edit]
- ^ Mehrotra, S. (1992). “Zur Implementierung einer Primal-Dual-Interior-Point-Methode”. SIAM Journal zur Optimierung. 2 (4): 575–601. doi:10.1137 / 0802028.
- ^ “1989 beschrieb Mehrotra einen praktischen Algorithmus für die lineare Programmierung, der die Grundlage der meisten aktuellen Software bleibt. Seine Arbeit erschien 1992.”
Potra, Florian A.; Stephen J. Wright (2000). “Innenpunktmethoden”. Zeitschrift für Computergestützte und Angewandte Mathematik. 124 (1–2): 281–302. doi:10.1016 / S0377-0427 (00) 00433-7.
- ^ ein b c d Nocedal, Jorge; Wright, Stephen J. (2006). Numerische Optimierung. Vereinigte Staaten von Amerika: Springer. S. 392–417, 448–496. ISBN 978-0387-30303-1.
Recent Comments