Quasi-Newton-Verfahren

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 sich umstellen, so 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.

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}}}$

Der Versuch eine Übersicht über die verschiedenen Ansätze der Quasi Newtion Verfahren zu verfassen, wurde 1985 in dem Artikel "Reguläre Quasi-Newton-Verfahren" gemacht. Hier konnte eine umfassende Klasse dieser Verfahren, eine Darstellung aller Rang 1 - Formeln der sogenannten symmetrischen, novellierten Huang-Klasse entwickelt werden, die die bekannten Verfahren wie das Davidon-Fletcher-Powell (DFP), das Broyden-Fletcher-Goldfarb-Shanno (BFGS) und Self-Scaling-Variable-Metric (SSVM) Verfahren beinhaltet. Auch sind dort Vorschläge für eine weitere Optimierung des Lösungsverhaltens von Quasi-Newton-Verfahren gegeben. Dabei wurde folgende Klasse von regulären (d. h. wegen besonderer Eigenschaften bevorzugt zu 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 sind 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 und quadratische Zielfunktion bricht zudem jedes dieser Verfahren nach höchstens n Iterationsschritten im Minimalpunkt ab. Insbesondere besitzen also die regulären Quasi - Newton -Verfahren die guten Eigenschaften sowohl der erweiterten Greenstadt-Klasse als auch der symmetrischen, erweiterten Huang-Klasse bzgl. Konvergenz und Stabilität.

Es kann vermutet werden, dass alle besonders leistungsfähigen Quasi-Newton-Verfahren regulär sind.

• 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