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,
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 Ausgangsmatrixist positiv definit, dann jede Matrix im iterativen ProzessSie sind alle positiv.

• BFGS-Algorithmus (Broyden-Fletcher-Goldfard-Shano)

DFP ist einNäherung der Inversen der Hesse-Matrix, während im BFGS-AlgorithmusNäherung an die Hesse-Matrix, die entsprechende Quasi-Newton-Bedingung

Nehmen wir an, dass in jeder Iteration die MatrixIstMit 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 Ausgangsmatrixist 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: Angenommenist eine reversible Matrix n-ter Ordnung,ist ein n-dimensionaler Vektor undist 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.

Verwandte Wörter: Newton-Verfahren, Optimierung