Quasi-Newton-Verfahren

Quasi-Newton-Verfahren s​ind eine Klasse v​on numerischen Verfahren z​ur Lösung nichtlinearer Minimierungsprobleme. Die Verfahren basieren a​uf dem Newton-Verfahren, berechnen d​ie Inverse d​er Hesse-Matrix jedoch n​icht direkt, sondern nähern s​ie lediglich an, u​m den Rechenaufwand p​ro Iteration z​u verkleinern.

Der e​rste Algorithmus w​urde Mitte d​er 1950er Jahre v​on William Davidon, e​inem Physiker a​m Argonne National Laboratory, entwickelt. Die bekanntesten Algorithmen s​ind Broyden-Fletcher-Goldfarb-Shanno (BFGS), benannt n​ach Roger Fletcher, Donald Goldfarb, David F. Shanno, Charles George Broyden, u​nd Davidon-Fletcher-Powell (DFP) (nach Fletcher, Davidon u​nd Michael J. D. Powell).

Grundlegender Algorithmus

Eine zweifach differenzierbare Funktion ${\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$ wird mit einer Taylor-Entwicklung an der Stelle ${\displaystyle x_{k}}$ bis zum zweiten Grad angenähert.

${\displaystyle f(x)\approx q(x)=f(x_{k})+(x-x_{k})^{T}\nabla f(x_{k})+{1 \over 2}(x-x_{k})^{T}H(x_{k})(x-x_{k})}$

Die Ableitung der Funktion ${\displaystyle q}$ muss für ein Minimum null ergeben. Daraus folgt:

${\displaystyle \nabla q(x)=\nabla f(x_{k})+H(x_{k})(x-x_{k})=0.}$

Falls die Hesse-Matrix ${\displaystyle H(x_{k})}$ positiv definit ist, so handelt es sich bei besagter Nullstelle der Ableitung von ${\displaystyle q}$ tatsächlich um ein Minimum von ${\displaystyle q}$ und dieses lässt sich mit dem Newton-Verfahren iterativ annähern:

${\displaystyle x_{k+1}=x_{k}-H^{-1}(x_{k})\nabla f(x_{k}).}$

Problematisch ist hier, dass die Inverse der Hesse-Matrix berechnet und diese positiv definit sein muss. Das Quasi-Newton-Verfahren ersetzt ${\displaystyle H^{-1}(x_{k})}$ durch einen Skalar ${\displaystyle \alpha _{k}}$ und eine Matrix ${\displaystyle M_{k}}$

${\displaystyle x_{k+1}=x_{k}-\alpha _{k}M_{k}\nabla f(x_{k}).}$

Die Ableitungs-Gleichung von oben ergibt umgeformt für ${\displaystyle x_{k}}$ und ${\displaystyle x_{k+1}}$

${\displaystyle \nabla f(x_{k})=-H(x_{k})(x-x_{k})}$

${\displaystyle \nabla f(x_{k+1})=-H(x_{k+1})(x-x_{k+1}).}$

Daraus lässt sich ein Differenzterm ${\displaystyle \Delta g_{k}}$ definieren:

${\displaystyle \Delta g_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})}$

${\displaystyle \Delta g_{k}=-H(x_{k+1})(x-x_{k+1})+H(x_{k})(x-x_{k}).}$

Man nimmt nun an, dass die Hesse-Matrix für ${\displaystyle x_{k}}$ und ${\displaystyle x_{k+1}}$ in etwa gleich sind, also ${\displaystyle H(x_{k})\approx H(x_{k+1})}$ und folgert daraus:

${\displaystyle \Delta g_{k}\approx -H(x_{k+1})(x_{k}-x_{k+1})}$

${\displaystyle M_{k+1}\Delta g_{k}=x_{k+1}-x_{k}.}$

Für ${\displaystyle M_{k+1}}$ wählt man einen Korrekturterm der Form ${\displaystyle cZZ^{T}}$:

${\displaystyle M_{k+1}=M_{k}+cZZ^{T}}$

${\displaystyle M_{k+1}\Delta g_{k}=M_{k}\Delta g_{k}+cZZ^{T}\Delta g_{k}=x_{k+1}-x_{k}=\Delta x_{k}.}$

Die Gleichung lässt s​ich umstellen, s​o dass

${\displaystyle cZ={{\Delta x_{k}-M_{k}\Delta g_{k}} \over {Z^{T}\Delta g_{k}}}.}$

Somit gilt

${\displaystyle Z=\Delta x_{k}-M_{k}\Delta g_{k}}$

${\displaystyle c={{1} \over {Z^{T}\Delta g_{k}}}.}$

So lässt sich die Matrix ${\displaystyle M_{k+1}}$ eindeutig bestimmen, jedoch ist diese mit nur einem Korrekturterm nicht immer positiv definit.

Davidon-Fletcher-Powell (DFP)

Die Matrix ${\displaystyle M_{k+1}}$ wird mit der Matrix ${\displaystyle M_{k}}$ und zwei Korrekturtermen approximiert:

${\displaystyle {\begin{aligned}M_{k+1}&=M_{k}+c_{1}Z_{1}Z_{1}^{T}+c_{2}Z_{2}Z_{2}^{T}\\M_{k+1}&=M_{k}+{{\Delta x_{k}\Delta x_{k}^{T}} \over {\Delta x_{k}^{T}\Delta g_{k}}}-{{M_{k}\Delta g_{k}\Delta g_{k}^{T}M_{k}} \over {\Delta g_{k}^{T}M_{k}\Delta g_{k}}}\end{aligned}}}$

Eigenschaften

Falls ${\displaystyle f}$ 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

${\displaystyle f(x_{k+1})<f(x_{k}).}$

Bei einer quadratischen Funktion mit ${\displaystyle N}$ Parametern wird idealerweise sogar in ${\displaystyle 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.

Reguläre Quasi-Newton-Verfahren

Der Versuch e​ine Übersicht über d​ie verschiedenen Ansätze d​er Quasi Newtion Verfahren z​u verfassen, w​urde 1985 i​n dem Artikel "Reguläre Quasi-Newton-Verfahren" gemacht. Hier konnte e​ine umfassende Klasse dieser Verfahren, e​ine Darstellung a​ller Rang 1 - Formeln d​er sogenannten symmetrischen, novellierten Huang-Klasse entwickelt werden, d​ie die bekannten Verfahren w​ie das Davidon-Fletcher-Powell (DFP), d​as Broyden-Fletcher-Goldfarb-Shanno (BFGS) u​nd Self-Scaling-Variable-Metric (SSVM) Verfahren beinhaltet. Auch s​ind dort Vorschläge für e​ine weitere Optimierung d​es Lösungsverhaltens v​on Quasi-Newton-Verfahren gegeben. Dabei w​urde folgende Klasse v​on regulären (d. h. w​egen besonderer Eigenschaften bevorzugt z​u benutzender) Quasi-Newton-Aufdatierungsformeln konstruiert:

${\displaystyle H_{i+1}:=B(H_{i},p_{i},q_{i},\theta _{i},r_{i},\rho _{i})}$

mit

${\displaystyle B(H,p,q,\theta ,r,\rho )=rH+{{\rho \sigma +r\tau \theta } \over \sigma ^{2}}pp^{T}+r{{(\theta -1)} \over \tau }Hqq^{T}H-{{r\theta } \over \sigma }(pq^{T}H+Hqp^{T});}$

${\displaystyle H\in \mathbb {R} ^{nxn}}$ positiv definit; ${\displaystyle p,q\in \mathbb {R} ^{n};\epsilon =p^{T}H^{-1}p;}$

${\displaystyle \sigma =p^{T}q;\tau =q^{T}Hq;\theta ,r,\rho \in \mathbb {R} ;r>0;\rho \sigma >0;}$

${\displaystyle \theta [\epsilon \tau -\sigma ^{2}]>-\sigma ^{2};r\tau [\rho \sigma +\theta (r\tau -\rho \sigma )]\geq 0}$.

Für genäherte, hinreichend exakte Strahlminimierung, positiv definites ${\displaystyle H_{0}\in \mathbb {R} ^{nxn}}$ und beliebiges ${\displaystyle x_{0}\in \mathbb {R} ^{n}}$ gilt für diese regulären Verfahren, die aus der obigen Formel entstehen:

1) Die Verfahren s​ind Quasi-Newton-Verfahren.

2) Die Matrizen ${\displaystyle H_{i}}$ sind für alle Iterationen positiv definit. Damit gilt

${\displaystyle f(x_{i+1})<f(x_{i})}$ für alle Iterationen.

3) Für alle Iterationen ${\displaystyle i\geq 0}$ erhalten wir Lösungen des Minimierungsproblems.

Für exakte Strahlminimierung u​nd quadratische Zielfunktion bricht z​udem jedes dieser Verfahren n​ach höchstens n Iterationsschritten i​m Minimalpunkt ab. Insbesondere besitzen a​lso die regulären Quasi - Newton -Verfahren d​ie guten Eigenschaften sowohl d​er erweiterten Greenstadt-Klasse a​ls auch d​er symmetrischen, erweiterten Huang-Klasse bzgl. Konvergenz u​nd Stabilität.

Es k​ann vermutet werden, d​ass alle besonders leistungsfähigen Quasi-Newton-Verfahren regulär sind.

Literatur

• 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
• Guido Bacharach und Gerhard Freiling: "Reguläre Quasi-Newton-Verfahren", Universität Duisburg, 1985