Quasi-Newton-Methode
Quasi-Newton-MethodeEs handelt sich um eine auf dem Newton-Verfahren basierende Optimierungsmethode, die hauptsächlich zur Lösung der Null-, Maximal- und Minimalwertprobleme nichtlinearer Gleichungen oder kontinuierlicher Funktionen verwendet wird.
Wenn die Jacobi-Matrix im Newton-Verfahren oder Hessisch Wenn die Berechnung der Matrix schwierig oder sogar unmöglich ist, kommt die Quasi-Newton-Methode zum Einsatz. Es ist eine der effektivsten Methoden zur Lösung nichtlinearer Optimierungsprobleme. Die Quasi-Newton-Methode wurde erstmals in den USA vorgeschlagen. Argonnen Physiker am National Laboratory WCDavidon Bei 20 Jahrhundert 50 Die vorgeschlagene Ära.
Die Idee der Quasi-Newton-Methode
Das Newton-Verfahren löst Hessisch Bei der Berechnung der Matrix muss zuerst die inverse Matrix berechnet werden, was zu einer Verringerung der Effizienz führt. Die Quasi-Newton-Methode verwendet jedoch eine positiv definite Matrix zur Annäherung Hessisch Die inverse Matrix der Matrix wird erhalten, wodurch die Komplexität des Algorithmus reduziert und die Effizienz verbessert wird.
Gängige Quasi-Newton-Algorithmen
- DFP-Algorithmus (Davidon-Fletcher-Powell)
Im DFP-Algorithmus wählen wir als Näherung von , wobei wir davon ausgehen, dass die Matrix in jeder Iteration aus plus zwei zusätzlichen Termen besteht, nämlich
In,
Und
ist die unbestimmte Matrix. Aber
Zu machen
Wenn wir die Quasi-Newton-Bedingung erfüllen, können wirUnderfüllen
Wünschenswert
Die Matrix kann erhalten werdenIterationsformel
Man kann beweisen, dass wenn die Ausgangsmatrix
ist positiv definit, dann jede Matrix im iterativen Prozess
Sie sind alle positiv.
- BFGS-Algorithmus (Broyden-Fletcher-Goldfard-Shano)
DFP ist einNäherung der Inversen der Hesse-Matrix
, während im BFGS-Algorithmus
Näherung an die Hesse-Matrix
, die entsprechende Quasi-Newton-Bedingung
Nehmen wir an, dass in jeder Iteration die Matrix
IstMit zwei zusätzlichen Begriffen, nämlich
In,Undist die unbestimmte Matrix. Aber
Zu machenWenn wir die Quasi-Newton-Bedingung erfüllen, können wirUnderfüllen
Wünschenswert
Die Matrix kann erhalten werdenIterationsformel
Man kann beweisen, dass wenn die Ausgangsmatrix
ist positiv definit, dann jede Matrix im iterativen ProzessSie sind alle positiv.
- Algorithmus vom Typ Broyden (Broyden-Algorithmus)
Wir können die BFGS-Algorithmusmatrix erhaltenDie iterative Formel des BFGS-Algorithmus lautetIterationsformel von .
erinnern
Wenn wir die Sherman-Morrison-Formel zweimal anwenden, erhalten wir
Er wird BFGS-Algorithmus genannt.Iterationsformel von .
Die Sherman-Morrison-Formel: Angenommen
ist eine reversible Matrix n-ter Ordnung,
ist ein n-dimensionaler Vektor und
ist auch eine reversible Matrix, dann:
Die iterative Formel, die durch den DFP-Algorithmus erhalten wird, seiAufgenommen als
, gemäß der iterativen Formel des BFGS-AlgorithmusWas Sie bekommenBezeichnet als, da und beide die Quasi-Newton-Bedingung erfüllen, die lineare Kombination der beiden
Es erfüllt auch die Quasi-Newton-Bedingung und ist positiv definit. In,
. Dieser Algorithmustyp wird als Algorithmus vom Broyden-Typ bezeichnet.