Quasi-Newton-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Quasi-Newton-Verfahren sind eine Klasse von numerischen Verfahren zur Lösung nichtlinearer Minimierungsprobleme. Die Verfahren basieren auf dem Newton-Verfahren, berechnen die Inverse der Hesse-Matrix jedoch nicht direkt, sondern nähern sie lediglich an, um den Rechenaufwand pro Iteration zu verkleinern.

Der erste Algorithmus wurde Mitte der 1950er Jahre von William Davidon, einem Physiker am Argonne National Laboratory, entwickelt. Die bekanntesten Algorithmen sind Broyden-Fletcher-Goldfarb-Shanno (BFGS), benannt nach Roger Fletcher, Donald Goldfarb, David F. Shanno, Charles George Broyden, und Davidon-Fletcher-Powell (DFP) (nach Fletcher, Davidon und Michael J. D. Powell).

Grundlegender Algorithmus[Bearbeiten | Quelltext bearbeiten]

Eine zweifach differenzierbare Funktion wird mit einer Taylor-Entwicklung bis zum zweiten Grad angenähert.

Die Ableitung der Funktion q muss für ein Minimum null ergeben. Daraus folgt :

Falls die Hesse-Matrix positiv definit ist, so handelt es sich bei besagter Nullstelle der Ableitung von q tatsächlich um ein Minimum von q und dieses lässt sich mit dem Newton-Verfahren iterativ annähern:

Problematisch ist hier, dass die Inverse der Hesse-Matrix berechnet und diese positiv definit sein muss. Das Quasi-Newton-Verfahren ersetzt durch einen Skalar und eine Matrix

Die Ableitungs-Gleichung von oben ergibt umgeformt für und

Daraus lässt sich herleiten :

Man nimmt nun an, dass die Hesse-Funktion für und in etwa dasselbe sind und folgert daraus :

Für wählt man einen Korrekturterm der Form :

Die Gleichung lässt sich umstellen, so dass

Somit gilt

So lässt sich die Matrix eindeutig bestimmen, jedoch ist diese mit nur einem Korrekturterm nicht immer positiv definit.

Davidon-Fletcher-Powell (DFP)[Bearbeiten | Quelltext bearbeiten]

Die Matrix wird mit der Matrix und zwei Korrekturtermen approximiert:

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Falls eine quadratische Funktion ist, liefert der Algorithmus bei exakter Arithmetik nach einer endlichen Anzahl an Iterationen die exakte Lösung. Für alle anderen Funktionen gilt

Bei einer quadratischen Funktion mit N Parametern wird idealerweise sogar in N Schritten die Lösung erreicht. In der Praxis benötigt man etwas mehr Iterationen, z.B. wenn die lineare Schrittweitensuche nicht genau genug durchgeführt wird oder die Gradienten nicht genau genug ermittelt werden. Meist stoppt man die Optimierung wenn z.B. der Gradient sehr klein ist oder eine bestimmte Anzahl von Iterationen erreicht wird.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • William C. Davidon, Variable Metric Method for Minimization, SIOPT Volume 1 Issue 1, Pages 1-17, 1991 (zuerst als Argonne National Laboratory Report 1959).
  • Jorge Nocedal und Stephen J. Wright: Numerical Optimization, Springer-Verlag, 1999 ISBN 0-387-98793-2.
  • Edwin K.P. Chong and Stanislaw H.Zak: An Introduction to Optimization, 2ed, John Wiley & Sons Pte. Ltd. August 2001.
  • P. Gill, W. Murray und M. Wright: Practical Optimization, 1981