Wir beschäftigen wir uns weiterhin mit der Lösung des unrestringierten Optimierungsproblems

In Kapitel 6 hatten wir unter geeigneten Voraussetzungen die superlineare und quadratische Konvergenz für das lokale und das globalisierte Newton-Verfahren nachgewiesen. In Abschnitt 6.3 hatten wir aber auch Nachteile des Newton-Verfahrens zumindest für größere Probleme erwähnt, wie insbesondere die, dass in jeder Iteration des Verfahrens die Hesse-Matrix bestimmt und ein lineares Gleichungssystem gelöst werden müssen.
Diese Nachteile versucht man mit den Quasi-Newton-Verfahren zu vermeiden, ohne dabei die superlineare Konvergenzrate des Newton-Verfahrens zu verlieren. Das Newton-Verfahren konvergiert zwar unter gewissen Voraussetzungen sogar quadratisch, aber für die meisten praktischen Probleme ist eine superlineare, nicht notwendig quadratische Konvergenzrate ausreichend. Überdies ist der numerische Aufwand pro Iteration für Quasi-Newton-Verfahren erheblich geringer als der für das Newton-Verfahren.
Wir definieren hier wiederum

und setzen in unserer Diskussion der Einfachheit halber voraus, dass
ist. (In den Lemmata und Sätzen geben wir jeweils, wie zuvor, die genauen Voraussetzungen an.) Die Quasi-Newton-Verfahren, mit denen wir uns beschäftigen werden, haben dann die folgende allgemeine Form.
Modellalgorithmus 7.1 (Quasi-Newton-Modellalgorithmus)
[Bearbeiten]
- (0) Wähle
, eine symmetrische, positiv definite Matrix
und eine semieffiziente Schrittweitenregel. Setze
.
- (1) Falls
ist, stop! (
ist kritische Lösung von Problem
.)
- (2) Berechne
- (7.1)

- eine Schrittweite
und setze

- (3) Setze

- und bestimme aus
und
mittels einer Aufdatierungsformel eine symmetrische, positiv definite Matrix
.
- (4) Setze
und gehe nach (1).
Da
im Modellalgorithmus 7.1 symmetrisch und positiv definit ist und in Schritt (2)
gilt, folgt
- (7.2)

Somit ist
eine Abstiegsrichtung von
in
und gilt damit
, da eine semieffiziente Schrittweite verwendet wird. Bei Algorithmen dieses Typs versucht man offenbar das Newton-Verfahren zu simulieren, indem man
durch eine geeignete Matrix
ersetzt (normalerweise schreibt man
und nicht
). Daher bezeichnet man solche Verfahren als Quasi-Newton-Verfahren.
Gelegentlich werden Verfahren vom Typ des Modellalgorithmus 7.1 auch als Variable-Metrik-Verfahren bezeichnet. Dies ist dadurch begründet, dass man die Richtung
gemäß Bemerkung 2.4 als Richtung des steilsten Abstiegs für
in
bezüglich der Norm
interpretieren kann. In dem Modellalgorithmus 7.1 wählt man demnach in jeder Iteration die Richtungsteilsten Abstiegs bezüglich einer von
abhängenden Metrik. Wird
gewählt, so ist
gerade die Richtung steilsten Abstiegs in
bezüglich der Euklidischen Norm.
Die zentrale Frage ist nun, wie man aus den in der
-ten Iteration vorliegenden Daten
und
eine geeignete Matrix
berechnet. Man stellt diesbezüglich die folgenden drei Forderungen an
auf:
- (F1) Es gilt

- für eine Konstante
und eine Matrix
mit

- (F2) Es gilt die Quasi-Newton-Gleichung
- (7.3)

- (F3) Mit
ist auch
eine symmetrische, positiv definite Matrix.
Eine Formel wie in (F1), gemäß der man aus Größen, die in der
-ten Iteration bekannt sind, eine Größe für die
-te Iteration eines Verfahrens bestimmt, bezeichnet man als Update-Formel. (Das englische „Update“ hat sich allgemein gegenüber der deutschen „Aufdatierung“ durchgesetzt, so dass wir es hier auch verwenden wollen.) Je nachdem, ob
in (F1) normalerweise den Rang 1 oder den Rang 2 hat, spricht man von einem Rang-1- oder Rang-2-Verfahren. Die Berechnung einer Rang-1-Matrix erfordert weniger Rechenoperationen als die einer Rang-2-Matrix. Auf der anderen Seite kann man aber erwarten, dass man mittels einer Rang-2-Matrix in einem Verfahren vom Typ des Modellalgorithmus 7.1 mit wachsendem
schneller eine Annäherung an das Newton-Verfahren erreichen kann.
Die Forderung (F2) lässt sich dabei auf folgende Weisen motivieren, sofern
eine reguläre Matrix ist. Für jede quadratische Funktion

mit symmetrischer, positiv definiter Matrix
hat man

und somit
![{\displaystyle \left[\nabla ^{2}f(x^{k+1})\right]^{-1}y^{k}=Q^{-1}\left(Qx^{k+1}-Qx^{k}\right)=x^{k+1}-x^{k}=s^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80094b7dc0222f585f9947bf2be6c1ba4edd6856)
Demnach genügt
der Quasi-Newton-Gleichung. Außerdem folgt für eine beliebige Funktion
mit der quadratischen Näherung

im Fall, dass die Quasi-Newton-Gleichung erfüllt und
eine reguläre Matrix ist:


Diese Beziehungen deuten darauf hin, dass unter den genannten Bedingungen
eine gute quadratische Approximation für
und folglich
eine gute Näherung für
ist.
Im Fall
besagt die Quasi-Newton-Gleichung:

In diesem Fall entspricht also
gerade der Steigung der Sekante für
durch die Punkte
und
und ist somit
. Wählt man im Modellalgorithmus 7.1 für jedes
die Schrittweite
, so stimmt dieser also für
mit dem aus der Numerischen Mathematik bekannten Sekanten-Verfahren zur Bestimmung einer Nullstelle der Gleichung
überein. Quasi-Newton-Verfahren verallgemeinern demnach in gewisser Weise das Sekantenverfahren für Funktionen in einer Veränderlichen auf solche in n Veränderlichen, weswegen sie gelegentlich auch als Sekanten-Verfahren bezeichnet werden. Entsprechend spricht man bei (F2) auch manchmal von der Sekanten-Gleichung.
In Abschnitt 7.2 werden wir allgemein Rang-1-Update-Formeln für Quasi-Newton-Verfahren aus den Forderungen (F1) - (F3) ableiten. Im Fall von Rang-2-Update-Formeln werden wir nicht so axiomatisch vorgehen, sondern in Abschnitt 7.3 gleich die wichtige Klasse der Broyden-Update-Formeln angeben und genauer betrachten. Die Formel aus dieser Klasse, die sich im Laufe der Zeit als die vom numerischen Verhalten her in den meisten Situationen beste Formel herausgestellt hat, ist die sog. BFGS-Update-Formel. Die Konvergenz des dadurch definierten BFGS-Verfahrens sowie Aussagen über dessen Konvergenzgeschwindigkeit werden wir in Abschnitt 7.4 beweisen. Mit einigen Bemerkungen zur Numerik werden wir in Abschnitt 7.5 dieses Kapitel abschließen.
Als erstes wollen wir nun untersuchen, inwieweit die drei Forderungen (F1) - (F3) im Fall
eine Update-Formel für
festlegen. Dazu leiten wir zunächst Gestalt und Eigenschaften von Rang-1-Matrizen her.
- Sei
eine Matrix mit
.
- (i) Dann gilt
für gewisse
.
- (ii) Ist
, dann gilt
für ein
und
.
Nach Voraussetzung hat der Bildraum von
die Dimension 1. Demnach gibt es einen Vektor
, so dass für jedes
mit einem
gilt:
. Ist
der
-te Standardeinheitsvektor, so folgt insbesondere für
mit gewissen
- (7.4)

wobei
die
-te Spalte von
ist. Also hat man mit

Offenbar ist
, da anderenfalls nach (7.4)
und nicht
wäre.
Im Fall
folgt somit
und mit
daher

Also ergibt sich für

q.e.d.
Man beachte, dass eine symmetrische Matrix maximal
unterschiedliche Elemente enthält, so dass das Aufstellen einer Rang-1-Matrix

die Berechnung von höchstens
reellen Produkten erfordert. Wir benötigen weiter folgende Aussagen für Rang-1-Matrizen, wobei die Spur einer Matrix die Summe ihrer Diagonalelemente ist:
- Es seien
. Dann gilt:
- (i) Die Matrix
hat im Fall
den
-fachen Eigenwert 0 und im Fall
den
-fachen Eigenwert 0 und den 1-fachen Eigenwert
.
- (ii)

- (iii)

Nach Voraussetzung hat man
und
. Sei nun
ein Eigenwert von
mit zugehörigem Eigenvektor
, d. h., es sei
- (7.5)

Dann kann also nur
orthogonal zu
und damit
sein oder (nicht im ausschließenden Sinne) es sind
und
parallel zueinander, wobei dann
oder
möglich ist.
Ist
orthogonal zu
, so ist
und die Menge

der zugehörige Eigenraum. Wegen
hat dieser die Dimension
. Da die geometrische Vielfachheit eines Eigenwertes kleiner oder gleich seiner algebraischen Vielfachheit ist, besitzt der Eigenwert
von
somit mindestens die Vielfachheit
. Sind andererseits
und
parallel zueinander, d. h. gilt
für ein
, so folgt aus (7.5) die Beziehung

Wegen
schließt man daraus, dass
ist (wobei
möglich ist).
Aussage (ii) folgt wegen

Schließlich hat die Matrix
im Fall
den
-fachen Eigenwert 1 und im Fall
den
-fachen Eigenwert 1 und den 1-fachen Eigenwert
. Da die Determinante einer reellen
-Matrix gleich dem Produkt ihrer
Eigenwerte ist, folgt damit das gewünschte Ergebnis in (iii).
q.e.d.
Ist die Bedingung (F1) für eine Matrix
mit
erfüllt und soll
, wie es in (F3) gefordert wird, symmetrisch sein, so muss auch
symmetrisch sein und muss gemäß Lemma 7.4 mit
und einem Vektor
gelten:
- (7.6)

Die Quasi-Newton-Gleichung (F2) hat demnach in diesem Fall die Gestalt

Unter der Voraussetzung
- (7.7)

impliziert die letztere Beziehung
- (7.8)

womit man erhält:
- (7.9)

Mit (7.8) und (7.9) bekommt man schließlich

Also ergibt sich aus (7.6) die Formel
- (7.10)

Für
erhält man aus (7.10) gerade die Broyden-Rang-1- bzw. SR1-Formel („symmetric-rank-1 formula“)
- (7.10)

Diese Formel hat den Vorteil, eine recht einfache Update-Formel zu sein. Für Algorithmen mit Schrittweitenstrategien, wie wir sie hier untersuchen, hat sie jedoch den schwerwiegenden Nachteil, dass nicht auszuschließen ist, dass der Nenner darin verschwindet und dass die Forderung (F3) der positiven Definitheit von B_{k+1} nicht erfüllt ist. (Insbesondere ist offenbar der Nenner in (7.11) identisch Null und dann diese Update-Formel nicht definiert, wenn die Voraussetzung (7.7) für den hier gewählten Weg ihrer Herleitung nicht erfüllt ist.)
Trotz einiger attraktiver Eigenschaften, wie z. B. der endlichen Konvergenz bei quadratischer Zielfunktion auch bei inexakten Schrittweiten, wenn das Verfahren durchführbar ist, wollen wir daher das Quasi-Newton-Verfahren mit der SR1-Formel nicht weiter untersuchen. Wir verweisen aber darauf, dass sich herausgestellt hat, dass die (modifizierte) SR1-Formel in manchen Zusammenhängen, insbesondere im Zusammenhang mit Trust-Region-Verfahren, die wir in Kapitel 8 diskutieren werden, hervorragende und oft bessere Ergebnisse als die unten untersuchte BFGS-Formel liefert (siehe [NoWri06] und die Literaturverweise in [GeiKa99]).
Wir wollen nun als nächstes der Frage nachgehen, ob nicht für
eine Rang-1-Update-Formel vom Typ (7.11) existiert, für die auch (F3) erfüllt ist. Dazu führen wir zunächst für eine symmetrische, positiv definite Matrix
auf folgende Weise eine ebenfalls symmetrische, positiv definite Matrix
ein: es sei
das durch
definierte Skalarprodukt
- (7.12)

und

die durch dieses Skalarprodukt induzierte elliptische Norm (vgl. Bemerkung 2.4). Weiter seien
mit
und
die zu
existierende Diagonalmatrix und orthogonale Matrix, so dass
gilt. Dann definieren wir

und

Die Matrix
ist wegen
ebenfalls symmetrisch und, da sie die Eigenwerte
hat, ebenfalls positiv definit. Ferner folgt für sie

sowie

Für die durch den Modellalgorithmus 7.1 erzeugten Größen gilt nun

und mit
- (7.13)

Wegen
hat man folglich

Also impliziert (7.10) unter Verwendung der Beziehung
- (7.14)


mit
- (7.15)

Im Fall
ist
offenbar genau dann positiv definit, wenn
dies ist.
Also stellt sich die Frage, wann
positiv definit ist. Die Matrix
hat gemäß Lemma 7.5
-mal den Eigenwert 1 sowie den Eigenwert
- (7.16)

Also ist
genau dann positiv definit, wenn
gilt. Insbesondere ist dies unter den Voraussetzungen des folgenden Lemmas der Fall.
- Es seien
sowie
und es sei
eine exakte Schrittweite. Dann folgt
(vgl. (7.7)) sowie
.
Gemäß Lemma 5.9 hat man

Unter Verwendung von (7.2) und (7.13) ergibt sicht somit für

Da
positiv definit ist, gilt
und folgt demnach in diesem Fall
. Da
ist und der Nenner in (7.16), wie die Herleitung von (7.15) zeigt, gerade dem Produkt

entspricht, ist demnach in diesem Fall auch (7.7) erfüllt.
q.e.d.
Die durch (7.14) gegebene Rang-1-Update-Formel
mit 
und mit einem frei wählbaren
wurde 1981 von Kleinmichel angegeben, wobei Kleinmichel aufgrund seiner numerischen Experimente die Wahl
für alle
vorschlägt. Das dadurch bestimmte Kleinmichel-Verfahren funktioniert im Allgemeinen gut (s. [GeiKa99]). Für eine Restart-Version konnte Kleinmichel die
-Schritt quadratische Konvergenz beweisen.
Nach ca. 1970 wurden zahlreiche Rang-2-Update-Formeln für Quasi-Newton-Verfahren vorgeschlagen. Die wenigsten dieser Formeln haben sich in der Praxis durchgesetzt. Wir wollen hier nur die ein-parametrische Broyden-Klasse von Update-Formeln untersuchen. Sie ist die für die Praxis wichtigste Unterklasse der zwei-parametrischen Oren-Luenberger-Klasse von Update-Formeln und enthält die sog. BFGS-Formel, die sich unter den Rang-2-Formeln als die im Allgemeinen numerisch effizienteste herausgestellt hat.
Für die Rang-2-Update-Formeln wollen wir nicht so axiomatisch vorgehen wie im Fall der Rang-1-Formeln, obwohl das möglich wäre, sondern wir geben hier direkt die durch einen Parameter
bestimmte Broyden-Klasse von Update-Formeln an, welche durch
- (7.17)
![{\displaystyle B_{k+1}:=B_{k}+\left(1+\theta _{k}{\frac {\tau _{k}}{\sigma _{k}}}\right){\frac {s^{k}(s^{k})^{T}}{\sigma _{k}}}-(1-\theta _{k}){\frac {B_{k}y^{k}(B_{k}y^{k})^{T}}{\tau _{k}}}-{\frac {\theta _{k}}{\sigma _{k}}}\left[s^{k}\left(B_{k}y^{k}\right)^{T}+\left(B_{k}y^{k}\right)(s^{k})^{T}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e3d498d54975a86532acece7292bc95df604a39)
definiert ist, wobei

und
- (7.18)

seien. Eine spezielle Update-Formel der Broyden-Klasse erhält man also durch Festlegung von
, wobei
typischerweise für alle
konstant gewählt wird. (Auch andere Schreibweisen der Formel in (7.17) sind gebräuchlich.)
Ein Quasi-Newton-Verfahren vom Typ des Modellalgorithmus 7.1 mit einer Update-Formel (7.17) für
bezeichnen wir als Quasi-Newton-Verfahren der Broyden-Klasse. Damit ein solches Verfahren überhaupt durchführbar ist, ist sicherzustellen, dass
für alle
gilt. Da mit
auch
ist, folgt mit der positiven Definitheit von
dann auch
für alle
.
Wir wollen nun zunächst diskutieren, unter welchen Voraussetzungen die Forderungen (F1) - (F3) für die Formel in (7.17) erfüllt sind. Dazu setzen wir insbesondere voraus:
- (7.19)
ist eine symmetrische, positiv definite Matrix,
wobei dies für
bereits im Modellalgorithmus 7.1 vorausgesetzt wurde. Somit ist
eine Abstiegsrichtung für
in
und damit insbesondere
.
Sind die Vektoren
und
linear unabhängig und gilt
, so handelt es sich bei (7.17) offenbar um eine Rang-2-Update-Formel mit
und ist somit (F1) erfüllt; im anderen Fall reduziert sich die Formel auf eine Rang-1-Update-Formel. (Übung!) Ferner gilt für
aus (7.17) die Quasi-Newton-Gleichung, wie das folgende Lemma besagt.
- Es sei
sowie
und es sei (7.19) erfüllt. Dann genügt
aus (7.17) der Quasi-Newton-Gleichung (7.3).
Da nach Voraussetzung
und
positiv definit ist, ist auch
. Somit ist die Update-Formel in (7.17) wohldefiniert. Weiter ist
identisch mit
![{\displaystyle B_{k}y^{k}+\left(1+\theta _{k}{\frac {\tau _{k}}{\sigma _{k}}}\right){\frac {s^{k}(s^{k})^{T}y^{k}}{\sigma _{k}}}-(1-\theta _{k}){\frac {B_{k}y^{k}(B_{k}y^{k})^{T}y^{k}}{\tau _{k}}}-{\frac {\theta _{k}}{\sigma _{k}}}\left[s^{k}\left(B_{k}y^{k}\right)^{T}y^{k}+\left(B_{k}y^{k}\right)(s^{k})^{T}y^{k}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc56bfc2db6d1d0a031de821fd5a81f08f3716af)
Verwendung der Definitionen von
und
aus (7.18) liefert

q.e.d.
Bleibt noch neben
zu garantieren, dass unter der Voraussetzung in (7.19) für
in (7.17) auch die Bedingung (F3) gesichert ist. Weil Matrizen vom Typ
und
mit
symmetrisch sind, ist mit
offenbar auch
symmetrisch. Im Fall, dass
positiv definit ist, ist dies auch die Matrix
. Da weiter
nach Lemma 7.7 der Quasi-Newton-Gleichung (7.3) genügt und da
und somit
gilt, folgt dann

Das folgende Lemma sagt nun aus, dass die Bedingung
auch hinreichend dafür ist, dass
in (7.17) positiv definit ist, wobei wir den Beweis dafür hier nur skizzieren wollen. (Für das genauer diskutierte BFGS-Verfahren werden wir die positive Definitheit von
weiter unten direkt nachweisen.)
Es sei
und es gelte (7.19). Ist
, so ist
in (7.17) symmetrisch und positiv definit.
Dass
symmetrisch ist, hatten wir schon erwähnt. Für den Nachweis der positiven Definitheit setze man

Dann gilt
für

Die Matrix
ist demnach genau dann positiv definit, wenn
dies ist. Letzteres ist der Fall, wenn alle Eigenwerte von
positiv sind.
Sind
und
linear unabhängig, so besitzt
, wie man zeigen kann, den
-fachen Eigenwert 1 und zwei Eigenwerte mit Eigenvektoren aus dem von
und
erzeugten Teilraum des
. Für diese Eigenvektoren mache man den Ansatz
und rechne man die beiden unbekannten Eigenwerte aus. Die gemachten Voraussetzungen garantieren dann, dass diese Eigenwerte positiv sind. Abschließend diskutiere man den einfacheren Fall, dass
und
linear abhängig sind.
q.e.d.
Insofern sind Voraussetzungen von Interesse, unter denen die Bedingung
erfüllt ist.
- Es seien (V1) - (V4) sowie die Voraussetzung in (7.19) erfüllt und es sei
. Dann folgt
.
Wie wir oben festgestellt haben, ist unter der Voraussetzung in (7.19)
eine Abstiegsrichtung für
in
, so dass gemäß Lemma 2.13
für die Menge
aus (2.9) folgt. Wegen
und
kann man daher insbesondere mit Lemma 2.9 (ii) schließen:

q.e.d.
Für gleichmäßig konvexe Funktionen ist also für alle
die Bedingung
und damit die Durchführbarkeit eines Quasi-Newton-Verfahrens der Broyden-Klasse gesichert. Ist jedoch
keine gleichmäßig konvexe Funktion, so kann die Bedingung
für alle Verfahren der Broyden-Klasse gemeinsam nur im Fall der Verwendung bestimmter Schrittweitenregeln garantiert werden. Und zwar gilt (Übung!):
- Es sei
und es gelte (7.19). Ist
eine exakte Schrittweite, eine Wolfe-Powell- oder eine strenge Wolfe-Powell-Schrittweite, so folgt
.
Im Fall, dass die Matrix
in (7.17) für das gewählte
positiv definit ist, kann ihre Inverse mit

explizit angegeben werden in der Form

- (7.20)
![{\displaystyle -{\frac {(1-\theta _{k})\sigma _{k}}{(\sigma _{k}^{2}+\theta _{k}(\varepsilon _{k}\tau _{k}-\sigma _{k}^{2}))}}\left[y^{k}(B_{k}^{-1}s^{k})^{T}+B_{k}^{-1}s^{k}(y^{k})^{T}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a217e5c229e9d5fca94adf477f45b3015348337)
Man prüft leicht, aber mit einiger Schreibarbeit nach, dass tatsächlich
gilt. Diese Formel ist offenbar eine Update-Formel für
. Ist
positiv definit, so ist auch
positiv definit.
In unserer Formulierung von Quasi-Newton-Verfahren (siehe den Modellalgorithmus 7.1) wird
als das Matrix-Vektor-Produkt „
“ bestimmt. Die Berechnung dieses Produktes erfordert
arithmetische Rechenoperationen. (Der Ausdruck
steht für
, wobei
eine von
unabhängige Konstante ist.) Im Hinblick auf das Newton-Verfahren kann man
mit
auch durch
definieren und
aus
gemäß (7.20) berechnen. Ähnlich wie beim Newton-Verfahren wird
bei einer solchen Vorgehensweise dann auch durch Lösung des linearen Gleichungssystems
gewonnen.
Ein derartiges Vorgehen wäre nicht sinnvoll, wenn man dann in jeder Iteration eine vollständige Cholesky-Zerlegung der Matrix
mit dem aus der Numerischen Mathematik bekannten Verfahren vornehmen würde, da eine solche Zerlegung
arithmetische Rechenoperationen erfordert. Es ist jedoch möglich, aus einer gegebenen Cholesky-Zerlegung
(die Startmatrix
wird oft als Diagonalmatrix gewählt) durch ein Rang-1-Update von
in
Rechenoperationen zu einer Cholesky-Zerlegung für
zu gelangen (z. B. [Wer92], [GeiKa99]).
Der Gewinn dabei ist, dass man dann anders als bei der zuerst beschriebenen Vorgehensweise quasi umsonst feststellen kann, ob
tatsächlich positiv definit und
damit eine Abstiegsrichtung für
in
ist (vgl. (7.2)). Denn in der Praxis kann man ja z. B. exakte Schrittweiten nicht genau berechnen oder kann man im Allgemeinen nicht verifizieren, ob man sich tatsächlich in einem Bereich von
befindet, in dem
gleichmäßig konvex ist (s. die Voraussetzungen von Lemma 7.9 und Satz 7.14).
In der nachfolgenden Bemerkung fassen wir außerdem ohne Beweis einige verblüffende Ergebnisse zu Quasi-Newton-Verfahren der Broyden-Klasse zusammen. Beweise dafür sind z.B. in [Fle91] und zum Teil auch in [Wer92] und [JaSt04] zu finden.
Der Modellalgorithmus 7.1 sei mit einer exakten Schrittweitenregel (!) und einer Update-Formel der Broyden-Klasse in (7.17) versehen. (Mit den Lemmata 7.10 und 7.8 schließt man induktiv, dass dann
für alle
symmetrisch und positiv definit ist.)
- (i) Ist
eine quadratische Funktion, d. h. ist

- und ist
positiv definit, so bricht jedes solche (durch die Wahl der
bestimmte) Quasi-Newton-Verfahren nach
Schritten ab und sind die von ihm erzeugten Richtungen
-konjugiert. Wird insbesondere
gewählt, so erzeugt jedes derartige Verfahren unabhängig von der Wahl der
bei gleichem Startwert
dieselben Iterierten wie das Fletcher-Reeves-Verfahren bzw. wie das im quadratischen Fall ja damit identische Polak-Ribière-Verfahren.
- (ii) Für jede, also auch jede nichtquadratische Funktion
erzeugen Quasi-Newton-Verfahren des oben spezifizierten Typs bei gleichen Startwerten für alle
dieselben Iterierten
.
Aus der allgemeinen Update-Formel der Broyden-Klasse in (7.17) erhält man insbesondere auch die Broyden-Rang-1- bzw. SR1-Formel (7.11), wenn man

setzt, wobei
nicht gesichert ist. Weiter leitet man für
aus (7.17) die sog. DFP-Formel
- (7.21)

ab, welche nach Davidon (1959) und Fletcher und Powell (1963) benannt wird, die diese Formel unabhängig voneinander angegeben hatten.
Schließlich gewinnt man aus (7.17) für
die wichtigste Update-Formel für Quasi-Newton-Verfahren, die BFGS-Formel
- (7.22)
![{\displaystyle B_{k+1}:=B_{k}+\left(1+{\frac {\tau _{k}}{\sigma _{k}}}\right){\frac {s^{k}(s^{k})^{T}}{\sigma _{k}}}-{\frac {1}{\sigma _{k}}}\left[s^{k}\left(B_{k}y^{k}\right)^{T}+\left(B_{k}y^{k}\right)(s^{k})^{T}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ef1fc976759e458555d8f4d0836d2192921f736)
Diese Formel bezieht ihren Namen aus den Anfangsbuchstaben der Namen von Broyden, Fletcher, Goldfarb und Shanno, die sie im Jahre 1970 unabhängig voneinander und nahezu zeitgleich mit unterschiedlichen Begründungen vorgeschlagen hatten. Die Quasi-Newton-Verfahren vom Typ des Modellalgorithmus 7.1 mit der DFP- und der BFGS-Formel heißen DFP- bzw. BFGS-Verfahren. Man kann leicht nachprüfen, dass die gesamte Broyden-Klasse von Update-Formeln in (7.17) in der Form

beschrieben werden kann, wobei
und
die Matrizen
in (7.21) und (7.22) bezeichnen mögen.
In der Praxis hat sich das BFGS-Verfahren als das verlässlichste und effizienteste unter den Rang-2-Quasi-Newton-Verfahren durchgesetzt. Im nächsten Abschnitt wollen wir daher die Konvergenz des BFGS-Verfahrens für gleichmäßig konvexe Funktionen beweisen, was sogar für beliebige semieffiziente Schrittweitenregeln gelingt. Man beachte, dass damit nach Bemerkung 7.12 bei Verwendung einer exakten Schrittweitenregel für gleichmäßig konvexe Funktionen auch die Konvergenz jedes anderen Verfahrens der Broyden-Klasse, also insbesondere die des DFP-Verfahrens bewiesen ist.
Es hat sich jedoch herausgestellt und numerische Beispiele in der angegebenen Literatur veranschaulichen dies, dass das DFP-Verfahren sehr viel empfindlicher auf die Wahl der Schrittweiten als das BFGS-Verfahren reagiert (z.B. [Fle91], [GeiKa99]). So konnte für das DFP-Verfahren im Hinblick auf die Schrittweitenregel auch kein so allgemeines Ergebnis wie das aus dem nächsten Abschnitt für das BFGS-Verfahren bewiesen werden. Hinweise darauf, warum das BFGS-Verfahren insgesamt bessere numerische Ergebnisse als z. B. das DFP-Verfahren liefert, findet man in der neueren Literatur (z. B. [NoWri06], [JaSt04, S. 180]).
Das BFGS-Verfahren, versehen mit einer semieffizienten Schrittweitenregel, lautet:
- (0) Wähle
, eine symmetrische, positiv definite Matrix
und eine semieffiziente Schrittweitenregel. Setze
.
- (1) Falls
ist, stop! (
ist kritische Lösung von Problem
.)
- (2) Berechne

- eine Schrittweite
und setze

- (3) Berechne

- und
- (7.23)
![{\displaystyle B_{k+1}:=B_{k}+\left(1+{\frac {\tau _{k}}{\sigma _{k}}}\right){\frac {s^{k}(s^{k})^{T}}{\sigma _{k}}}-{\frac {1}{\sigma _{k}}}\left[s^{k}(B_{k}y^{k})^{T}+B_{k}y^{k}(s^{k})^{T}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc3b268b66d5a78be67b0f806d27bb4cc38b82d4)
- (4) Setze
und gehe nach (1).
Wir wollen zunächst beweisen, dass die Matrix
im Fall der BFGS-Formel für eine gleichmäßig konvexe Zielfunktion
für jedes
positiv definit ist. (Den Beweis der positiven Definitheit von
für die ganze Broyden-Klasse hatten wir ja nicht vollständig ausgeführt.) Unter den entsprechenden Voraussetzungen fällt Algorithmus 7.13 also in das Schema des Modellalgorithmus 2.5.
- Es seien (V1) - (V4) erfüllt, und es sei
symmetrisch und positiv definit. In der
-ten Iteration von Algorithmus 7.13 hat man dann
und
und ist auch
in (7.23) positiv definit. Mit
folgt ferner
- (7.24)

Lemma 7.9 impliziert unter den gegebenen Voraussetzungen
. Damit hat man
und demnach
.
Die Matrix
und Vektoren
die Gestalt
![{\displaystyle B_{k+1}=B_{k}+\alpha aa^{T}-\beta \left[ab^{T}+ba^{T}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2eb241f2fffd0f2b7915accbed6c25beab65e206)
Somit folgt die Symmetrie von
wegen
![{\displaystyle B_{k+1}^{T}=B_{k}^{T}+\alpha aa^{T}-\beta \left[ba^{T}+ab^{T}\right]=B_{k+1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52978d1ec85c20e3d4fa59807a605df715c43ce8)
Bleibt zu zeigen, dass
für alle
gilt.
Mit

erhalten wir wegen
und
![{\displaystyle z^{T}B_{k+1}z=z^{T}B_{k}z+\left(1+{\frac {\tau _{k}}{\sigma _{k}}}\right){\frac {(z^{T}s^{k})^{2}}{\sigma _{k}}}-{\frac {1}{\sigma _{k}}}z^{T}\left[s^{k}(B_{k}y^{k})^{T}+B_{k}y^{k}(s^{k})^{T}\right]z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc2aaeba33db43de786fa43ce79194dc450c7b4d)
- (7.25)

Ist
, so folgt weiter
für
bzw.
, so dass in diesem Fall alles gezeigt ist. Gilt andererseits
und damit insbesondere
, so kann man folgendermaßen abschätzen:


Also ist
positiv definit. Dass die in (7.24) angegebene Matrix die Inverse von
ist, zeigt man durch Verifizierung der Gleichung
, was etwas aufwändig, aber nicht schwierig ist.
q.e.d.
Der erste Nachweis der Konvergenz des BFGS-Verfahrens wurde von Powell erbracht und stellt eine der großen Leistungen in der Optimierung dar. Da das BFGS-Verfahren eines der wichtigsten Optimierungsverfahren ist, wollen wir hier auch einen Konvergenzbeweis, der auf Werner zurückgeht, für gleichmäßig konvexe Funktionen und eine beliebige semieffiziente Schrittweitenregel führen. Dieser Beweis ist aber recht lang und technisch, so dass der eher numerisch orientierte Leser ihn überspringen mag. Wir benötigen dazu:
- (i) Es seien
. Dann gilt

- (ii) Es sei
eine symmetrische Matrix und
seien ihre Eigenwerte. Dann gilt

Damit können wir nun die Konvergenz des BFGS-Verfahrens für gleichmäßig konvexe Funktionen beweisen.
- Es seien (V1) - (V4) erfüllt. Algorithmus 7.13 bricht entweder nach endlich vielen Schritten mit der Lösung
von
ab oder er liefert eine Folge
, die gegen
konvergiert. Genauer gilt sogar

Wir nehmen an, dass Algorithmus 7.13 nicht nach endlich vielen Schritten abbricht. Aus Satz 7.14 schließt man dann induktiv für alle
, dass
und
gilt und dass
positiv definit ist. Für alle
ist damit ferner
eine Abstiegsrichtung (vgl. (7.2)) und gemäß Definition 2.12 einer semieffizienten Schrittweitenregel mit
auch
für die Menge
aus (2.9). Sei nun
beliebig.
Es wird eine semieffiziente Schrittweitenregel verwendet, so dass gemäß Definition 2.12 eine Konstante
existiert mit
- (7.26)

für

Nach Aussage (v) von Lemma 2.9 hat man

Folglich gilt mit (7.26)

Unter Verwendung der Beziehung
für
gewinnt man daraus


Wenn wir nun zeigen können, dass ein
existiert mit
- (7.27)

so folgte aus Letzterem

Da nach Lemma 2.9 (iii)

gilt, hätte man dann weiter

Summation über alle k lieferte schließlich
- (7.28)

wobei die Konvergenz der rechten Reihe wegen
und
leicht mit dem Quotientenkriterium erschlossen werden kann. Da die Konvergenz einer Reihe nach sich zieht, dass ihre Glieder gegen 0 streben, folgte aus (7.28) auch die gewünschte Konvergenz
.
Wir wollen also (7.27) für ein
nachweisen. Dazu zeigen wir, dass für Konstanten
die Ungleichungen
- (7.29)

und
- (7.30)

gelten. Denn hat man dies, so kann man folgenden, auf Powell zurückgehenden „Trick“ anwenden (
bezeichnet dabei die Anzahl der Elemente von
).
Es gilt: Sind
und
Zahlen mit
, dann hat man für

die Abschätzung
.
Setzt man
, so folgt dies für
sofort und für
aus

Ferner gilt: Sind
und
Zahlen mit
, dann hat man für

die Abschätzung
.
Letztere Aussage folgt offenbar aus der ersteren durch Logarithmisierung mit
und
.
Gibt es nun von einer
-elementigen Menge eine Teilmenge
mit
und einer „Eigenschaft 1“ sowie eine Teilmenge
mit
und einer „Eigenschaft 2“, so existiert offenbar eine Teilmenge
der Menge mit
, welche beide Eigenschaften besitzt. Aus (7.29) und (7.30) folgert man daher bei festem
die Existenz einer Teilmenge
mit
, d. h. insbesondere
und

Damit bekommt man weiter


so dass man für
die Ungleichung (7.27) erschließt. Folglich müssen wir noch (7.29) und (7.30) beweisen.
Zunächst wollen wir die Gültigkeit von (7.29) nachweisen. Mit
ist

und daher unter Verwendung der Lemmata (7.5) und (7.15)
- (7.31)

Nach Aussage (ii) von Lemma 2.9 hat man
- (7.32)

so dass mit (V3) folgt:
- (7.33)

Ferner gilt
- (7.34)

- (7.35)

Somit kann man mit

aus (7.31) schließen:

- (7.36)

Also gilt (7.29) und haben wir nur noch (7.30) zu zeigen. In diesem Zusammenhang halten wir aber noch die folgende Abschätzung fest, die sich aus (7.31) mit (7.33), (7.36) und der Definition von
ergibt:
- (7.37)

Offenbar ist
mit

Für
gilt nun, wie man leicht überprüft (siehe auch Aufgabenblatt 5):

so dass speziell für
folgt:
und somit

Demnach kann man schreiben


Berücksichtigt man nun Lemma 7.5, so bekommt man

Damit erreicht man:

- (7.38)

Sind
, so schließt man außerdem mit der Ungleichung vom geometrisch-arithmetischen Mittel, mit Lemma 7.15 sowie mit der Abschätzung in (7.37)
![{\displaystyle \det(B_{k+1}^{-1})=\prod _{i=1}^{n}\lambda _{i}(B_{k+1}^{-1})\leq \left\{{\frac {1}{n}}\sum _{i=1}^{n}\lambda _{i}(B_{k+1}^{-1})\right\}^{n}=\left\{{\frac {1}{n}}\operatorname {Spur} (B_{k+1}^{-1})\right\}^{n}\leq \left\{{\frac {1}{n}}\left[{\frac {1}{2}}c_{1}+{\frac {k+1}{2}}c_{1}+c_{1}(k+1)\right]\right\}^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b8725fda67aa94841779aab1081ebac1404d371)
- (7.39)

Die Ungleichung vom geometrisch-arithmetischen Mittel besagt, dass für Zahlen
und
gilt:
![{\displaystyle {\sqrt[{n}]{a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}}\leq {\frac {1}{n}}(a_{1}+a_{2}+\ldots +a_{n}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6511a8f05294b76b1f155283aed6a042141277c4)
Zusammen implizieren (7.38) und (7.39)
- (7.40)

Aus einer weiteren Anwendung der Ungleichung vom geometrisch-arithmetischen Mittel erhält man ferner mit (7.36)
- (7.41)

Unter Ausnutzung von (7.34), (7.35), (7.32), (7.41) und (7.40) gelangt man schließlich zu


wobei
eine gewisse Konstante ist. Damit ist auch die Gültigkeit von (7.30) bewiesen.
q.e.d.
Damit haben wir die globale Konvergenz des BFGS-Verfahrens für gleichmäßig konvexe Funktionen bewiesen. Obwohl das BFGS-Verfahren in der Praxis auch für andere nichtlineare Funktionen sehr robust ist, ist bisher nicht bekannt, ob es für beliebige Funktionen
und zumindest für einige Schrittweitenregeln in dem Sinne global konvergent ist, dass jeder Häufungspunkt einer durch das Verfahren erzeugten Folge ein stationärer Punkt von
ist. Letzteres kann man z. B. für das globalisierte Newton-Verfahren mit der Armijo-Schrittweitenregel zeigen (s. [GeiKa99]). Es sei aber bemerkt, dass jede Funktion in der Umgebung eines lokalen Minimalpunktes, in dem die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 1.14 erfüllt sind, gleichmäßig konvex ist. Denn es gilt (Beweis: Übung!):
- Es sei
. Man zeige, dass die Bedingung
- (7.42)

- genau dann für ein
und ein
erfüllt ist, wenn
positiv definit ist.
Der Nachweis der superlinearen Konvergenz des BFGS-Verfahrens ist noch aufwändiger als der seiner Konvergenz. Es werden dazu auch stärkere Glattheitsvoraussetzungen benötigt.
- Es seien (V1) - (V4) erfüllt und für die dann existierende eindeutige Lösung
von
gebe es Konstanten
und
, für die
gilt sowie
- (7.43)

- Weiter gelte
- (7.44)
![{\displaystyle \lim _{k\to \infty }{\frac {\left\|\left[B_{k}^{-1}-\nabla ^{2}f(x^{*})\right]p^{k}\right\|}{\left\|p^{k}\right\|}}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96528dcdc1ae53a74b2fc6e39be39032888758ac)
- und
- (7.45)

- Dann konvergiert die durch Algorithmus 7.13 erzeugte Folge
superlinear gegen die eindeutige Lösung
von
.
Wir wollen zeigen, dass
- (7.46)

gilt. Nach Lemma 2.9 (iv) hat man nämlich

so dass wegen

aus (7.46) folgt:

Daraus erschließt man die superlineare Konvergenz von
, da

genau dann für eine Folge von Zahlen
gilt, wenn
ist.
Wegen

erhalten wir nun im Hinblick auf den Zähler in (7.46)
- (7.47)

Für alle hinreichend großen
gilt weiter gemäß Satz 7.16
und liefern daher eine Taylor-Entwicklung von
mit einem
und die Anwendung von (7.43)
\right\|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efbe08050c615afbe53800b37ef932fdc554227c)
- (7.48) Fehler beim Parsen (Syntaxfehler): {\displaystyle \le L \left\| x^k + \vartheta_k(x^{k+1} - x^k) - x^* \right\| \left\| x^{k+1} - x^k \right\| \right\| \le L \left\{ \left\|x^k - x^*\right\| + \left\| x^{k+1} - x^k \right\| \right\} \left\| x^{k+1} - x^k \right\|.}
Außerdem hat man

- (7.49)
![{\displaystyle \leq \left|{\frac {1}{t_{k}}}-1\right|{\frac {\left\|B_{k}^{-1}p^{k}\right\|}{\left\|p^{k}\right\|}}+{\frac {\left\|\left[B_{k}^{-1}-\nabla ^{2}f(x^{*})\right]p^{k}\right\|}{\left\|p^{k}\right\|}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b397128172dc807c9053eec097756f20265d4c6)
Der zweite Summand in (7.49) konvergiert gemäß der Voraussetzung (7.44) gegen 0 für
und der erste tut dies aufgrund der Voraussetzung (7.45) und aufgrund der Beschränktheit der Folge
, welche sich wegen

aus (7.44) ergibt. Den Grenzwert in (7.46) gewinnt man nun mit den Abschätzungen (7.47), (7.48) und (7.49) und wegen der aus Satz 7.16 hervorgehenden Konvergenz
.
q.e.d.
Der folgende Satz zeigt, dass es für den Nachweis der superlinearen Konvergenz des BFGS-Verfahrens genügt, die Bedingung (7.44) nachzuweisen, wenn das Verfahren mit einer der Schrittweitenregeln aus Kapitel 3 verknüpft wird. Wir verwenden in diesem Zusammenhang wieder die Voraussetzung (V5), die gemäß Bemerkung 6.8 das Erfülltsein der Bedingungen (V1) - (V4) nach sich zieht (siehe auch Lemma 7.17):
- (V5) Es ist
, die Menge
aus (2.9) ist konvex und es existieren Konstanten
mit
- (7.50)

Satz 7.19