Quasi-Newton-Verfahren

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

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

$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 $q$ muss für ein Minimum null ergeben. Daraus folgt:

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

Falls die Hesse-Matrix $H(x_{k})$ 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:

$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 $H^{-1}(x_{k})$ durch einen Skalar $\alpha _{k}$ und eine Matrix $M_{k}$

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

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

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

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

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

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

$\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 $x_{k}$ und $x_{k+1}$ in etwa gleich sind, also $H(x_{k})\approx H(x_{k+1})$ und folgert daraus:

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

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

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

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

$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

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

Somit gilt

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

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

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

Davidon-Fletcher-Powell (DFP)

Die Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_{k+1}} wird mit der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_k} und zwei Korrekturtermen approximiert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} 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{align} }

Eigenschaften

Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x_{k+1}) < f(x_k).}

Bei einer quadratischen Funktion mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} Parametern wird idealerweise sogar in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H_{i+1} : = B ( H_i, p_i, q_i, \theta_i, r_i, \rho_i ) }

mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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^TH - {{r \theta} \over \sigma} (pq^T H + Hqp^T); }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H \isin \mathbb{R}^{nxn}} positiv definit; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p,q \isin \mathbb{R}^n ; \epsilon = p^T H^{-1} p; }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma = p^Tq; \tau = q^T Hq ; \theta ,r, \rho \isin \mathbb{R}; r > 0; \rho \sigma > 0; }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \theta [\epsilon \tau - \sigma^2] > - \sigma^2; r \tau [\rho \sigma + \theta (r \tau - \rho \sigma )] \ge 0 } .

Für genäherte, hinreichend exakte Strahlminimierung, positiv definites Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H_0 \isin \mathbb{R}^{nxn}} und beliebiges Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0 \isin \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H_i} sind für alle Iterationen positiv definit. Damit gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f (x_{i+1}) < f (x_i)} für alle Iterationen.

3) Für alle Iterationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \ge 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.

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