Quasi-Newton-Verfahren

Kernidee und Zweck

Quasi-Newton-Verfahren sind numerische Verfahren zur Lösung nichtlinearer Minimierungsprobleme. Sie bauen auf dem Newton-Verfahren auf, vermeiden aber einen wichtigen Rechenaufwand: Die Inverse der Hesse-Matrix wird nicht direkt berechnet, sondern nur angenähert. Die Hesse-Matrix beschreibt die zweiten Ableitungen einer Funktion und damit die Krümmung; ihre Inverse ist im Newton-Verfahren nötig, um eine neue Näherung für das Minimum zu bestimmen.

Der Vorteil der Quasi-Newton-Verfahren liegt darin, dass sie pro Iteration weniger aufwendig sind als das klassische Newton-Verfahren. Bekannte Verfahren sind Broyden-Fletcher-Goldfarb-Shanno (BFGS), benannt nach Roger Fletcher, Donald Goldfarb, David F. Shanno und Charles George Broyden, sowie Davidon-Fletcher-Powell (DFP), benannt nach Fletcher, William Davidon und Michael J. D. Powell. Der erste Algorithmus wurde Mitte der 1950er Jahre von William Davidon am Argonne National Laboratory entwickelt.

Grundidee des Algorithmus

Ausgangspunkt ist eine zweifach differenzierbare Funktion f: R^n -> R. Sie wird an einer Stelle x_k durch eine Taylor-Entwicklung bis zum zweiten Grad angenähert:

f(x) ≈ q(x) = f(x_k) + (x - x_k)^T ∇f(x_k) + 1/2 (x - x_k)^T H(x_k)(x - x_k).

Für ein Minimum der Näherungsfunktion q muss ihre Ableitung null sein:

∇q(x) = ∇f(x_k) + H(x_k)(x - x_k) = 0.

Ist die Hesse-Matrix H(x_k) positiv definit, dann ist diese Nullstelle tatsächlich ein Minimum von q. Das Newton-Verfahren verwendet dann die Iterationsformel:

x_{k+1} = x_k - H^{-1}(x_k)∇f(x_k).

Problematisch ist dabei, dass H^{-1}(x_k), also die Inverse der Hesse-Matrix, berechnet werden muss und dass die Hesse-Matrix positiv definit sein muss. Quasi-Newton-Verfahren ersetzen deshalb H^{-1}(x_k) durch einen Skalar α_k und eine Matrix M_k:

x_{k+1} = x_k - α_k M_k ∇f(x_k).

M_k ist dabei eine Näherung für die inverse Hesse-Matrix.

Aufdatierung der Näherungsmatrix

Um die Näherungsmatrix weiterzuentwickeln, betrachtet man die Änderung des Gradienten zwischen zwei Iterationspunkten. Der Gradient ∇f(x) ist der Vektor der ersten Ableitungen. Man definiert:

Δg_k = ∇f(x_{k+1}) - ∇f(x_k).

Aus der umgeformten Ableitungsbedingung folgt näherungsweise, wenn man annimmt, dass sich die Hesse-Matrix zwischen x_k und x_{k+1} nur wenig ändert, also H(x_k) ≈ H(x_{k+1}):

M_{k+1} Δg_k = x_{k+1} - x_k.

Mit Δx_k = x_{k+1} - x_k soll also die neue Matrix M_{k+1} so gewählt werden, dass sie die beobachtete Änderung des Gradienten passend auf die Änderung des Punkts abbildet. Dafür wird zunächst ein Korrekturterm der Form cZZ^T angesetzt:

M_{k+1} = M_k + cZZ^T.

Daraus ergeben sich:

Z = Δx_k - M_k Δg_k

und

c = 1 / (Z^T Δg_k).

Damit lässt sich M_{k+1} eindeutig bestimmen. Allerdings ist eine solche Aufdatierung mit nur einem Korrekturterm nicht immer positiv definit. Positive Definitheit ist wichtig, weil sie mit der Richtung und Stabilität der Minimierung zusammenhängt.

DFP-Verfahren

Das Davidon-Fletcher-Powell-Verfahren, kurz DFP, verwendet nicht nur einen, sondern zwei Korrekturterme, um die Matrix M_{k+1} aus M_k zu approximieren. Die Formel lautet:

M_{k+1} = M_k + c_1 Z_1 Z_1^T + c_2 Z_2 Z_2^T

beziehungsweise konkret:

M_{k+1} = M_k + (Δx_k Δx_k^T)/(Δx_k^T Δg_k) - (M_k Δg_k Δg_k^T M_k)/(Δg_k^T M_k Δg_k).

Diese Aufdatierung ist ein typisches Beispiel dafür, wie Quasi-Newton-Verfahren aus den Informationen der letzten Schritte eine bessere Näherung für die inverse Hesse-Matrix gewinnen. Statt die Hesse-Matrix jedes Mal vollständig neu zu berechnen und zu invertieren, wird die vorhandene Näherung gezielt korrigiert.

Wichtige Eigenschaften

Für quadratische Funktionen hat der Algorithmus eine besonders starke Eigenschaft: Bei exakter Arithmetik liefert er nach einer endlichen Anzahl von Iterationen die exakte Lösung. Hat eine quadratische Funktion N Parameter, wird idealerweise sogar in N Schritten die Lösung erreicht.

Für alle anderen Funktionen gilt laut Artikel:

f(x_{k+1}) < f(x_k).

Das bedeutet: Der Funktionswert wird in jedem Schritt kleiner. In der Praxis benötigt man oft mehr Iterationen als im idealen Fall, zum Beispiel wenn die lineare Schrittweitensuche nicht genau genug durchgeführt wird oder die Gradienten nicht genau genug bestimmt werden. Häufig beendet man die Optimierung, wenn der Gradient sehr klein ist oder wenn eine festgelegte Anzahl von Iterationen erreicht wurde.

Reguläre Verfahren

Ein Versuch, verschiedene Quasi-Newton-Ansätze systematisch darzustellen, wurde 1985 im Artikel „Reguläre Quasi-Newton-Verfahren“ unternommen. Dort wurde eine umfassende Klasse solcher Verfahren beschrieben, darunter eine Darstellung aller Rang-1-Formeln der symmetrischen, novellierten Huang-Klasse. Diese Klasse umfasst bekannte Verfahren wie Davidon-Fletcher-Powell (DFP), Broyden-Fletcher-Goldfarb-Shanno (BFGS) und Self-Scaling-Variable-Metric (SSVM). Außerdem wurden Vorschläge zur weiteren Verbesserung des Lösungsverhaltens gegeben.

Die regulären Quasi-Newton-Aufdatierungsformeln werden in der Form

H_{i+1} := B(H_i, p_i, q_i, θ_i, r_i, ρ_i)

angegeben. Dabei gilt unter anderem: H ∈ R^{n x n} ist positiv definit, p,q ∈ R^n, ε = p^T H^{-1}p, σ = p^T q, τ = q^T Hq, θ,r,ρ ∈ R, r > 0 und ρσ > 0. Zusätzlich müssen die im Artikel angegebenen Ungleichungen erfüllt sein:

θ[ετ - σ^2] > -σ^2

und

rτ[ρσ + θ(rτ - ρσ)] ≥ 0.

Für genäherte, hinreichend exakte Strahlminimierung, positiv definites H_0 ∈ R^{n x n} und beliebiges x_0 ∈ R^n entstehen daraus Verfahren mit mehreren garantierten Eigenschaften: Sie sind Quasi-Newton-Verfahren, die Matrizen H_i bleiben für alle Iterationen positiv definit, und deshalb gilt f(x_{i+1}) < f(x_i) für alle Iterationen. Außerdem erhält man für alle Iterationen i ≥ 0 Lösungen des Minimierungsproblems. Bei exakter Strahlminimierung und quadratischer Zielfunktion bricht jedes dieser Verfahren nach höchstens n Iterationsschritten im Minimalpunkt ab.

Der Artikel fasst zusammen, dass reguläre Quasi-Newton-Verfahren die guten Eigenschaften sowohl der erweiterten Greenstadt-Klasse als auch der symmetrischen, erweiterten Huang-Klasse bezüglich Konvergenz und Stabilität besitzen. Außerdem wird vermutet, dass alle besonders leistungsfähigen Quasi-Newton-Verfahren regulär sind.