Wir haben bisher Verfahren zur Lösung des Problems

betrachtet, bei denen für jede Iterierte
zunächst eine Abstiegsrichtung
und anschließend eine Schrittweite, welche die Länge des Schrittes von
in Richtung
festlegt, berechnet werden mussten. Bei allen bisher vorgestellten Verfahren außer den CG-Verfahren kann man dabei die Richtung
aus einer quadratischen Näherung

für die Zielfunktion
bei
herleiten, wobei
eine symmetrische, positiv definite Matrix ist. Wählt man nämlich den Minimalpunkt
dieser Funktion, welcher sich aus der Gleichung

ergibt, als Näherung für einen Minimalpunkt von
, so gelangt man bei Schrittweite 1 zu der Richtung

Insbesondere ist beim Gradientenverfahren
, beim Newton-Verfahren
und bei den Quasi-Newton-Verfahren
, wobei
durch eine Update-Formel definiert war.
Bei den Trust-Region-Verfahren („trust region“ bedeutet Vertrauensbereich) kombiniert man die Richtungssuche und die Schrittweitenbestimmung, indem man in jeder Iteration die Richtung mittels eines lokalen quadratischen Modells für
unter einer Nebenbedingung an die Länge dieser Richtung bestimmt und indem man erforderlichenfalls die Vorgabe für die Länge der Richtung ändert und das Problem erneut löst, wenn die gefundene Richtung einem gewünschten Kriterium nicht genügt. Genauer gesagt, sucht man in der
-ten Iteration für die durch eine symmetrische, aber nicht notwendig positiv definite (!) Matrix
bestimmte quadratische Näherung von

und für ein
, welches möglicherweise noch geeignet anzupassen ist, eine globale Lösung des sog. Trust-Region-Teilproblems
- (8.1)

bei dem über
zu minimieren ist. Da
auf
stetig und der zulässige Bereich von
wegen
nichtleer ist, hat dieses Problem nach dem Satz von Weierstraß eine (globale) Lösung, die aber nicht notwendig eindeutig und eine Abstiegsrichtung für
in
sein muss. (Deshalb bezeichnen wir in diesem Abschnitt Richtungen, engl. „directions“, auch mit „
“, um keine Verwechslungen aufkommen zu lassen.)
Die Konstante
ist dabei eine in jeder Iteration geeignet zu wählende Konstante, welche den Radius des Trust-Regions, des Vertrauensbereichs, festlegt. Wenn der Schritt von
in Richtung der ermittelten Lösung
von
nach einem noch festzulegenden Kriterium als akzeptabel oder erfolgreich interpretiert werden kann, wird

gesetzt und
für die nächste Iteration beibehalten bzw. vergrößert. Im anderen Fall setzt man
, verkleinert man
und löst man
erneut. Wie wir bereits in Abschnitt 2.1 diskutiert hatten, wird man dann normalerweise eine andere Richtung erhalten.
Eventuell hat man also das Problem
mehrfach mit derselben Zielfunktion und einer modifizierten Nebenbedingung zu lösen. In einem solchen Fall hat man dann zwar Rechenaufwand zu leisten, müssen aber keine neuen Funktionswerte bestimmt werden, die bei großen Anwendungsproblemen auch real sehr teuer oder nur aufwändig zu beschaffen sein können. Denn ein Funktionswert kann ja z. B. Ergebnis eines realen Experimentes sein oder nur mit einem relativ hohen Aufwand zu berechnen sein. Der Interpretation der numerischen Resultate in [GeiKa99, S. 313] können wir uns daher nicht ohne weiteres anschließen.
Trust-Region-Verfahren, wie wir sie hier vorstellen, lösen also unrestringierte Optimierungsprobleme, indem in jeder Iteration ein restringiertes Optimierungsproblem gelöst wird, wobei aber nicht nur ein lokaler, sondern ein globaler Minimalpunkt von letzterem Problem zu finden ist. Sie sind also zwischen der unrestringierten und restringierten Optimierung einzuordnen. Da restringierte Probleme typischerweise einen höheren Aufwand für die numerische Lösung erfordern, steht und fällt die Effizienz von Trust-Region-Verfahren mit der Effizienz der Methode, die zur „Lösung“ des Trust-Region-Teilproblems, eines speziellen quadratischen Optimierungsproblems, verwendet wird. Dabei muss man dieses Teilproblem glücklicherweise nicht vollständig lösen. Zwei Vorgehensweisen im Sinne einer solchen „inexakten Lösung“ werden wir in Abschnitt 8.3 und auf einem Aufgabenblatt behandeln. Für weitere Vorschläge in diesem Zusammenhang verweisen wir auf die Literatur (z. B. [GeiKa99], [NoWri06] und [SuYu06]).
Wenn man die Euklidische Norm in (8.1) durch die Maximumnorm ersetzt (s. [CGT00]), so lässt sich die entsprechende Nebenbedingung des Trust-Region-Teilproblems wegen

mit
äquivalent durch
lineare Nebenbedingungen ausdrücken und kann man in diesem Fall zur Lösung des Teilproblems auch ein Verfahren für (linear restringierte) quadratische Optimierungsprobleme wählen.
In Abschnitt 8.1 leiten wir einige theoretische Resultate zum Trust-Region-Teilproblem her. Anschließend diskutieren wir in Abschnitt 8.2 ein konkretes Trust-Region-Verfahren, das Trust-Region-Newton-Verfahren, welches man als eine Trust-Region-Modifikation des globalisierten Newton-Verfahrens interpretieren kann. Der Aufwand der darin zu lösenden Teilprobleme kann recht hoch sein, so dass wir in Abschnitt 8.3 eine Modifikation dieses Verfahrens, das Teilraum-Trust-Region-Newton-Verfahren, behandeln werden, bei dem das Teilproblem nur auf einem niedrig-dimensionalen Teilraum des
zu lösen ist.
Wir wollen uns nun zunächst mit dem Trust-Region-Teilproblem beschäftigen. Der Einfachheit halber betrachten wir das von
unabhängige Problem

mit einer symmetrischen Matrix
und einer Konstanten
, wobei über
zu minimieren ist. Die Funktion
bezeichnen wir als Zielfunktion und die Ungleichung
als (Ungleichungs-) Nebenbedingung. Einen Vektor
mit
nennen wir zulässig. Letztere Nebenbedingung in Problem
können wir auch quadrieren und äquivalent durch

ersetzen. Die Menge aller für
zulässigen Vektoren, der zulässige Bereich von
, ist offenbar konvex und wegen
nichtleer.
Wie bereits gesagt wurde, hat das Problem
eine Lösung. Im Fall, dass
positiv definit ist, ist
gleichmäßig konvex und besitzt
somit eine eindeutige Lösung
(vgl. Satz 1.9). Da
aber hier nicht positiv definit sein muss, kann
auch lokale, nichtglobale Lösungen und mehr als eine globale Lösung besitzen. Erstaunlicherweise kann man jedoch globale Lösungen von
vollständig charakterisieren, wie der folgende Satz angibt.
ist genau dann eine globale Lösung von Problem
, wenn es ein
gibt, so dass die folgenden Bedingungen erfüllt sind:
- (a)

- (b)

- (c)
ist positiv semidefinit.
Es sei
eine globale Lösung von
. Dann ist
auch globale Lösung des zu
äquivalenten Problems, das man erhält, wenn man die Ungleichung in
gegen die Ungleichung
mit

austauscht. Ist nun diese Nebenbedingung inaktiv, d. h.
bzw.
, dann ist
lokaler Minimalpunkt des unrestringierten Problems
und sind nach Satz 1.14 die Bedingungen (a), (b) und (c) mit
und wegen der dritten Bedingung in (a) nur für dieses
erfüllt.
Also nehmen wir an, die Nebenbedingung sei aktiv, d. h. es gelte
und damit
und
. Sei nun
ein Vektor mit
. Dann ist
- (8.2)

und es gilt

Folglich liegen alle Vektoren

mit
bzw. alle Vektoren
mit
in der Kugel um 0 mit Radius
und sind damit zulässig für
. Da
globaler Minimalpunkt von
ist, gilt demnach weiter für alle
- (8.3)

was nach Division durch
und Grenzübergang für

liefert. Also gibt es keinen Vektor, der beiden Ungleichungen

gleichzeitig genügt.
Nun stellt man fest: gibt es keinen Vektor
mit
, welcher für zwei Vektoren
die Ungleichungen

gleichzeitig erfüllt, so muss
mit einem
sein. Denn anderenfalls wäre die Cauchy-Schwarz-Ungleichung strikt erfüllt, d. h. wäre

und erhielte man dagegen für


Also besitzen die beiden Ungleichungen
und
keine Lösung. Damit ist
, da anderenfalls
eine Lösung dieser Ungleichungen wäre.
Folglich ist mit einem eindeutig bestimmten
- (8.4)

wobei wir den Faktor 2 nur aus praktischen Gründen verwenden. Demnach sind die Bedingungen (a) und (b) im Satz erfüllt. Schließlich setzen wir in (8.3)
und folgern wir unter Verwendung von (8.4) und (8.2)

Demzufolge hat man
für alle
mit
und damit für alle
mit
, wie man mittels Ersetzung von
durch
ersieht. Somit ist

Denn anderenfalls gäbe es ein
mit
und
und könnte man eine Folge
mit
sowie
konstruieren, was aber
und damit
zur Folge hätte. Also ist auch (c) erfüllt.
Umgekehrt seien nun die Bedingungen (a) - (c) für
und
erfüllt. Insbesondere ist somit
. Dann folgt unter Verwendung von (a), (b) und (c) für alle Vektoren
mit


- (8.5)


Also ist
globaler Minimalpunkt von
.
q.e.d.
Zwei einfache Folgerungen aus Satz 8.1 werden in den folgenden beiden Korollaren gegeben. Wir hatten schon festgestellt, dass die positive Definitheit von
hinreichend dafür ist, dass das Problem
eine eindeutige Lösung besitzt. Das erste Korollar besagt, dass es für die Existenz einer eindeutigen Lösung genügt, dass die Matrix
positiv definit ist (was eine stärkere Annahme als die der positiven Definitheit von
ist).
- Sei
globaler Minimalpunkt von
und
eine Zahl, welche zusammen mit
den Bedingungen (a), (b) und (c) von Satz 8.1 genügt. Ist die Matrix
positiv definit, so ist
einziger globaler Minimalpunkt von
.
Sei
ein Vektor mit
und
. Da nach Voraussetzung
positiv definit ist, hat man

Daher kann man „
“ in (8.5) durch „
“ ersetzen und kann man analog schließen:

q.e.d.
Bei dem nächsten Resultat beachte man, dass z. B. in der
-ten Iteration des Trust-Region-Newton-Verfahrens, welches im nächsten Abschnitt behandelt wird,
und
ist.
- Sei
globaler Minimalpunkt von
. Dann sind die folgenden Aussagen äquivalent:
- (a)

- (b)
und
ist positiv semidefinit.
Übung!
Bei Anwendung des Trust-Region-Newton-Verfahrens kann man also von der Größe des optimalen Zielfunktionswertes des Trust-Region-Teilproblems her erschließen, ob die notwendigen Optimalitätsbedingungen zweiter Ordnung für
in dem aktuellen
erfüllt sind oder nicht.
Bisher haben wir nur globale Minimalpunkte für Problem
diskutiert. Ein interessantes Ergebnis in diesem Zusammenhang ist das folgende (s. [Mar94]).
- Das Problem
besitzt höchstens einen lokalen Minimalpunkt, der kein globaler Minimalpunkt von
ist.
In diesem Abschnitt wollen wir eine Trust-Region-Variante des Newton-Verfahrens vorstellen. Dazu sei
und mit einer symmetrischen Matrix
durch
- (8.6)

eine quadratische Näherung für
definiert. Da wir an einem Newton-ähnlichen Verfahren interessiert sind, setzen wir hier speziell

(vgl. Kapitel 6). Damit ist die Zielfunktion des Trust-Region-Teilproblems in der
-ten Iteration wohldefiniert. Wie zuvor bezeichne
eine globale Lösung dieses Problems.
Die entscheidende Frage ist nun, wie man den Radius
des Vertrauensbereichs steuert. Die Entscheidung, ob
gegenüber
vergrößert oder verkleinert werden sollte, macht man im Allgemeinen von dem Wert der Zahl

abhängig. Der Zähler von
gibt offenbar die tatsächliche Reduktion des Funktionswertes von
an, die man bei einem Übergang von
zu
erreicht, während der Nenner die durch das quadratische Modell vorausgesagte Reduktion beschreibt. Da 0 zulässiger Punkt von
ist und somit
- (8.7)

gilt, ist der Nenner von
nichtnegativ.
Ist also
oder
, so scheint
eine gute oder eher pessimistische quadratische Approximation von
bei
zu sein. Daher kann man in einem solchen Fall
setzen und den Radius
entweder gleich
oder größer als
wählen. Ist dagegen
klein oder sogar negativ, also die durch das quadratische Modell vorausgesagte Reduktion des Funktionswertes von
größer als die reale, so sollte man
und
wählen. Diese Überlegungen spiegeln sich in dem folgenden Verfahren wieder. Dabei sei wieder

Algorithmus 8.5 (Trust-Region-Newton-Verfahren)
[Bearbeiten]
- (0) Wähle
und
und setze
.
- (1) Falls
ist, stop! (
ist kritische Lösung von Problem
.)
- (2) Bestimme eine globale Lösung
des Problems

- (3) Berechne
- (8.8)

- und setze
- (8.9)

- sowie
- (8.10)

- (4) Setze
und gehe nach (1).
Dass der Nenner von
in Schritt (3) von Algorithmus 8.5 nicht verschwindet und der Algorithmus damit durchführbar ist, werden wir unten aus Lemma 8.6 schließen können. Typische Festlegungen für die Konstanten in Algorithmus sind z. B.

Die Abfrage
oder
wird offenbar bei solchen Setzungen sehr großzügig interpretiert. Man beachte weiter, dass man für Iterierte, die durch Algorithmus 8.5 erzeugt werden, die Monotoniebeziehung
- (8.11)

hat. Denn für festes
ist entweder
und damit

oder es ist
und folglich wegen (8.7) der Zähler
von
positiv. Eine Iteration, für die
ist, bezeichnen wir als eine erfolgreiche Iteration.
Algorithmus 8.5 ist die in [GeiKa99] angegebene Version des Trust-Region-Newton-Verfahrens. Sie unterscheidet sich von dem „klassischen“ Verfahren durch die Verwendung einer unteren Schranke
bei erfolgreichen Iterationen. Die Verwendung dieser unteren Schranke erlaubt den Beweis einer globalen Konvergenzaussage ohne zusätzliche Voraussetzungen. Sie ist praktisch unproblematisch, da sie beliebig klein gewählt werden kann.
Wir wollen als nächstes die Konvergenz von Algorithmus 8.5 beweisen. Dabei verwenden wir
statt
, wenn ein Ergebnis für eine beliebige symmetrische Matrix
gültig ist. Zunächst leiten wir eine untere Abschätzung für den Nenner in der Konstanten
her, welche ja für die Größe des Trust-Regions bestimmend ist.
- Sei
eine Lösung von Problem
. Dann ist

- wobei
für
gesetzt werde.
Da
globale Lösung des Teilproblems
ist, gilt für jedes
mit
, also für jedes für das Problem
zulässige
:
- (8.12)

Im Fall
ergibt sich damit für den Vektor
, der offenbar für
zulässig ist,

Ist andererseits
und damit insbesondere
, so ergibt sich für den Vektor

und folgt somit aus (8.12)

Kombination der gewonnenen Ungleichungen liefert das gewünschte Ergebnis.
q.e.d.
Aus dem letzten Lemma schließt man, dass der Nenner von
in (8.8) nur im Fall
identisch Null sein kann. Dieser Fall wird aber durch den dann erfolgenden Abbruch in Schritt (1) von Algorithmus 8.5 ausgeschlossen. Algorithmus 8.5 ist also durchführbar.
Das nächste Hilfsresultat liefert eine Aussage über Teilfolgen einer durch Algorithmus 8.5 erzeugten Iteriertenfolge, welche gegen einen nichtkritischen Punkt von
konvergieren.
- Sei
und Algorithmus 8.5 breche nicht nach endlich vielen Iterationen ab. Ist
eine Teilfolge der dann von ihm erzeugten Folge
, welche gegen ein
mit
konvergiert, so folgt

Sei
. Dann konvergiert nach Voraussetzung
gegen
und ist

zu zeigen.
Angenommen, es wäre
. Da wir gleich zu einer geeigneten Teilfolge von
hätten übergehen können, können wir dafür ohne Beschränkung der Allgemeinheit annehmen, dass gilt:

Aus den Update-Formeln (8.10) und (8.9) folgt dann für alle hinreichend großen
- (8.13)

Aus der vorausgesetzten Konvergenz der Folge
gegen
erschließt man damit die Konvergenz von
gegen
und wegen
folgert man
und somit
- (8.14)

Aufgrund der Voraussetzung
gilt nun weiter - ohne Beschränkung der Allgemeinheit für die ganze Folge
- mit einer Konstanten
- (8.15)

Ferner ist
als konvergente Folge beschränkt, so dass es wegen
eine Konstante
gibt mit
- (8.16)

und damit

Weiter wäre dann
, da der Algorithmus anderenfalls in Schritt (1)abgebrochen wäre. Dies widerspräche aber Lemma 8.7 bezogen auf die Teilfolge
von
.
Es sei nun
eine Teilfolge von
mit
- (8.19)

Dann können wir zunächst für jeden nicht erfolgreichen Iterationsschritt mit Nummer
schließen, dass

für ein
gilt, wobei die Iterationen
nicht erfolgreich sind und die Iteration
erfolgreich ist. Da es insgesamt unendlich viele erfolgreiche Iterationen gibt, können wir auf diese Weise jedem
, das zu einer nicht erfolgreichen Iteration gehört, (gegebenenfalls auch mehreren
hintereinander gleichzeitig) ein mit diesem identisches Folgenglied
von
aus einer erfolgreichen Iteration zuordnen und so eine gegen
konvergierende Teilfolge von
erzeugen, deren Glieder ausschließlich zu erfolgreichen Iterationen gehören. Ohne Beschränkung der Allgemeinheit sei dies die Folge
selbst, sei also
.
Es sei nun
angenommen. Dann existieren - ohne Beschränkung der Allgemeinheit für die ganze Folge
- Konstanten
und
mit
- (8.20)

Lemma 8.6 impliziert demzufolge zusammen mit (8.20) für alle
![{\displaystyle f(x^{k_{i}})-f(x^{k_{i}+1})=r_{k_{i}}\left[f(x^{k_{i}})-q_{k_{i}}(d^{k_{i}})\right]\geq \varrho _{1}\left[f(x^{k_{i}})-q_{k_{i}}(d^{k_{i}})\right]\geq {\frac {1}{2}}\varrho _{1}\left\|g^{k_{i}}\right\|\min \left\{\Delta _{k_{i}},{\frac {\left\|g^{k_{i}}\right\|}{\left\|B_{k_{i}}\right\|}}\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23b50efd8d3e03634e4fd28623450168250e8522)
- (8.21)

Nun kann man aber wegen (8.19)

schließen, was mit (8.11)

nach sich zieht. Also implizieren die Abschätzungen in (8.21) die Konvergenz
. Letzteres steht aber im Widerspruch zu Lemma 8.7. Folglich ist
und ist alles gezeigt.
q.e.d.
Wir betrachten nun die Situation, dass
eine gleichmäßig konvexe Funktion ist, wobei wir auch hier wieder die Voraussetzung (V5) verwenden.
- Das Teilproblem
besitzt für jedes
eine globale Lösung. Unter der Voraussetzung (V5) ist diese eindeutig.
Übung!
Unter der Voraussetzung (V5), welche gemäß Bemerkung 6.8 die Bedingungen (V1) - (V4) impliziert, hat man nun weiter das folgende Resultat.
- Es sei (V5) erfüllt und es sei
die somit existierende eindeutige Lösung von
. Dann bricht Algorithmus 8.5 entweder ab oder er erzeugt eine Folge
, für welche gilt:
- (i)

- (ii) Es ist
für alle
mit einem
.
- (iii) Es ist
für alle
mit einem
.
(i) Sei
eine konvergente Teilfolge von
. Nach Korollar 1.18 und Satz 8.8 gilt dann
- (8.22)

Aufgrund der Stetigkeit von
folgt damit

und dies wiederum impliziert wegen der Monotonie der Folge
(siehe (8.11)) die Konvergenz der ganzen Folge
gegen
. Die Konvergenz von
gegen
erschließt man nun mit Hilfe von Lemma 2.9 (iii).
(ii) Da
wegen (8.11) für alle
in
liegt, folgt aus (V5) für
- (8.23)

Weil der Vektor 0 für das Problem
zulässig ist, erhält man ferner

so dass

und daher
- (8.24)

folgt. Weiter schließt man aus der Konvergenz
und aufgrund der Stetigkeit von
die Existenz eines
mit

Daher ergibt sich mit
, der Abschätzung (8.24) und Lemma 8.6

für

Nach dem Satz von Taylor gilt nun für ein
auf der Verbindungsstrecke von
und

Daher ergibt sich
![{\displaystyle \left|f(x^{k}+d^{k})-q_{k}(d^{k})\right|={\frac {1}{2}}\left|(d^{k})^{T}\left[\nabla ^{2}f(\xi ^{k})-\nabla ^{2}f(x^{k})\right]d^{k}\right|\leq {\frac {1}{2}}\left\|d^{k}\right\|^{2}\left\|\nabla ^{2}f(\xi ^{k})-\nabla ^{2}f(x^{k})\right\|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec1a7555323bb52c635ec4b44f58e1e0d10b5a37)
Also schließt man unter Verwendung der Abschätzung in (8.25):

Nun gilt
(wegen Aussage (i) und (8.24)) und damit auch
. Demzufolge erhält man
und somit
für alle hinreichend großen
.
(iii) Aus dem letzten Resultat und den Vorschriften in Schritt (3) von Algorithmus 8.5 folgt
für alle hinreichend großen
. Dies impliziert die Behauptung.
q.e.d.
Mit Hilfe des letzten Satzes können wir beweisen, dass das Trust-Region-Newton-Verfahren lokal in das lokale Newton-Verfahren aus Abschnitt 6.1.2 übergeht und daher eine entsprechende Konvergenzrate aufweist:
- Es sei (V5) erfüllt und es sei
die dann existierende eindeutige Lösung von
. Dann bricht Algorithmus 8.5 entweder ab oder er erzeugt eine Folge
, für welche gilt:
- (i)
konvergiert superlinear gegen
.
- (ii) Hat man mit einem
und einem

- dann konvergiert
quadratisch gegen
.
Unter der Voraussetzung (V5) gilt für
und für die Menge
aus (2.9)
- (8.26)

Da alle
wegen der Monotonie der Folge
in
liegen, impliziert dies, dass
und somit
für alle
positiv definit ist. Daraus schließt man, dass die Newton-Richtung
![{\displaystyle d_{N}^{k}:=-\left[\nabla ^{2}f(x^{k})\right]^{-1}g^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6ca03f3199638c3535307716dfa1fbbf15f5ec6)
für jedes
der eindeutige globale Minimalpunkt von
bezüglich des ganzen Raumes
ist.
Weiter impliziert die Eigenschaft von
in (8.26), dass
![{\displaystyle \left\|\left[\nabla ^{2}f(x^{k})\right]^{-1}\right\|\leq {\frac {1}{\beta }},\quad k\in \mathbb {N} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf4f85482dd8739c94dfc888d4d33460c889ac71)
gilt (vgl. Bemerkung 6.8). Demzufolge ergibt sich

Aus Aussage (i) von Satz 8.10 folgt die Konvergenz
, so dass letztere Ungleichung die Konvergenz
liefert. Da weiter nach Satz 8.10
für ein
und alle
ist, hat man also
für alle hinreichend großen
. Für diese
folgt

und ist demnach
die Lösung von Problem
. Das Trust-Region-Newton-Verfahren geht also lokal in das lokale Newton-Verfahren über, so dass sich die Aussagen des Satzes aus Satz 6.6 ergeben.
q.e.d.
Algorithmus 8.5 kann also mit Recht als ein Trust-Region-Newton-Verfahren bezeichnet werden. Es gibt natürlich auch Trust-Region-Quasi-Newton-Verfahren. Bei diesen ist die Zielfunktion des
-ten Trust-Region-Teilproblems mit einer symmetrischen Matrix
durch

bestimmt, wobei
nach einer erfolgreichen Iteration gemäß einer der von den Quasi-Newton-Verfahren her bekannten Formeln aufdatiert wird (vgl. Kapitel 7). Anders als bei den herkömmlichen Quasi-Newton-Verfahren müssen die Matrizen
aber nicht mehr positiv definit sein und muss sich im Fall, dass
positiv definit ist, diese Eigenschaft nicht auf
übertragen. Letzteres ist ja beispielsweise für das BFGS-Verfahren gesichert, wenn
gleichmäßig konvex ist (siehe Satz 7.14).
Für die Iterierten des BFGS-Verfahrens gilt im Fall der gleichmäßigen Konvexität von
gemäß Satz 7.14 insbesondere die für den Nachweis der positiven Definitheit von
benötigte Bedingung

Diese Bedingung muss aber bei einem Trust-Region-BFGS-Verfahren nicht erfüllt sein. Daher ist es nicht klar, welche der Update-Formeln für Quasi-Newton-Verfahren vorzugsweise verwendet werden sollte. In der Tat hat sich gezeigt, dass das Trust-Region-SR1-Verfahren mit der SR1-Update-Formel aus (7.11) zum Teil bessere Ergebnisse als das Trust-Region-BFGS-Verfahren liefert.
Für die Lösung der Teilprobleme eines Trust-Region-Quasi-Newton-Verfahrens ist es jedoch nützlich, wenn alle Matrizen
positiv definit sind. Deshalb geht man gelegentlich so vor, dass man auch bei erfolgreichen Iterationen
wählt, wenn
ist. Ganz allgemein kann man aber unabhängig von derartigen Strategien für ein Trust-Region-Quasi-Newton-Verfahren eine dem Satz 8.8 entsprechende Aussage beweisen, wenn man zusätzlich die Beschränktheit der Folge
voraussetzt. (Damit ist nämlich auch in diesem Fall die Abschätzung für die
wie in (8.20) gesichert und lässt sich der Beweis ganz ähnlich führen.) Die Beschränktheit der Folge
kann man dann in der Praxis künstlich erzwingen, indem man beispielsweise
nicht aufdatiert, wenn
eine vorgegebene Schranke überschreitet. Für Details verweisen wir auf die angegebene Literatur und insbesondere auf [GeiKa99].
8.3 Teilraum-Trust-Region-Newton-Verfahren
[Bearbeiten]
Im Unterschied zum globalisierten Newton-Verfahren mit Schrittweitenbestimmung, bei dem sich in jeder Iteration die Richtung aus der Lösung eines linearen Gleichungssystems ergibt, muss beim Trust-Region-Newton-Verfahren zur Richtungsbestimmung ein quadratisches Optimierungsproblem mit einer Ungleichungsnebenbedingung gelöst werden. Dies ist zumeist erheblich aufwändiger. Allerdings entfällt dafür bei letzterem Verfahren die Schrittweitenbestimmung, die beim globalisierten Newton-Verfahren zumindest in Fällen, in denen der Startpunkt weit von der Lösung des Problems entfernt ist, eine größere Anzahl von Funktionsauswertungen erfordern kann.
Bemühungen, das Teilproblem beim Trust-Region-Newton-Verfahren durch ein einfacher und schneller lösbares Problem zu ersetzen, haben zu Varianten dieses Verfahrens geführt, die hier als nächstes diskutiert werden sollen. Diese Varianten unterscheiden sich von dem ursprünglichen Verfahren dadurch, dass beim Trust-Region-Teilproblem nicht über den ganzen Raum
, sondern nur über einen Teilraum des
minimiert wird.
Es sei also
ein weiter unten noch genauer spezifizierter Teilraum des
und es sei
. Wir betrachten dann die folgende Modifikation von Algorithmus 8.5:
Algorithmus 8.12 (Teilraum-Trust-Region-Newton-Verfahren)
[Bearbeiten]
- (0) Wähle
und
und setze
.
- (1) Falls
ist, stop! (
ist kritische Lösung von Problem
.)
- (2) Bestimme eine globale Lösung
des Problems

- (3) Berechne

- und setze

- sowie

- (4) Setze
und gehe nach (1).
Man überlege sich als Übung, warum das Trust-Region-Teilproblem
unter der Voraussetzung (V5) für jedes
eine eindeutige Lösung besitzt.
Wir zeigen nun, dass das Teilproblem
in ein Problem vom Typ des ursprünglichen Teilproblems
in (8.1) umgeschrieben werden kann. Da der Raum
häufig so gewählt wird, dass er nur die Dimension 1, 2 oder 3 hat, ist dieses dann aber sehr viel schneller lösbar als ein Teilproblem, bei dem über dem ganzen Raum
minimiert wird.
Es sei also
ein Teilraum des
mit Dimension
und es mögen
eine Orthonormalbasis von
bilden. Die Bedingung
ist dann äquivalent damit, dass
existieren mit

Die Orthonormalität der
impliziert dabei die Beziehungen

Das Problem
kann demnach auch folgendermaßen formuliert werden:

Mit den Setzungen



schreiben wir dieses Problem in der Form
- (8.27)

wobei über
zu minimieren ist. Unsere Herleitung zeigt:
ist genau dann Lösung von Problem
, wenn
- (8.28)

- gilt, wobei
Lösung von Problem (8.27) ist.
Wie bereits gesagt wurde, wählt man
typischerweise so, dass
und damit (8.27) ein Problem in maximal 3 Variablen ist. Eine einfache Wahl von
ist die Wahl
- (8.29)

wobei
die Richtung steilsten Abstiegs für
in
bezeichnet. In diesem Fall nennt man die zugehörige Lösung
von
auch Cauchy-Punkt. Diesen Punkt kann man explizit angeben (Beweis: Übung!):
- (8.30)

mit
- (8.31)

Die Richtung (8.30) ist die mit einer speziellen „Schrittweite“ versehene Richtung steilsten Abstiegs für
in
, so dass Algorithmus 8.12 für die Wahl (8.29) als Gradientenverfahren mit einer speziellen Schrittweitenstrategie aufgefasst werden kann, wobei diese „Strategie“ in nicht erfolgreichen Iterationen nicht einmal einen Abstieg hinsichtlich des Funktionswertes von
liefert. Wie in Kapitel 4 gezeigt wurde, konvergiert das Gradientenverfahren zwar unter schwachen Voraussetzungen global, aber es kann dies selbst mit exakten Schrittweiten extrem langsam tun.
Daher wählt man den Raum
in Algorithmus 8.12 zumeist nicht wie in (8.29), sondern als
- (8.32)

wobei
![{\displaystyle d_{G}^{k}:=-g^{k},\quad d_{N}^{k}:=-\left[\nabla ^{2}f(x^{k})\right]^{-1}g^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a0f86b332ab484d41266935d57affd6ea71413a)
die Gradienten- und die Newton-Richtung für
in
sind und vorausgesetzt wird, dass die Matrix
für alle
invertierbar ist. Letzteres ist ja unter der Voraussetzung (V5) gewährleistet. Sind
und
linear unabhängig, so ist in diesem Fall
.
Gelegentlich setzt man auch
- (8.33)

wobei
ein Eigenvektor oder eine geeignete Näherung für einen Eigenvektor zum kleinsten Eigenwert
der Matrix
ist. (Den Eigenwert und Eigenvektor muss man allerdings erstmal berechnen). Die Hinzunahme von
in die Basis von
ist dadurch begründet, dass für eine hinreichend kleine Norm
, d. h. bei einer geeigneten Skalierung des gefundenen Eigenvektors zu
gilt:

- (8.34)

Im Fall

wobei man die zweite Ungleichung gegebenenfalls durch Übergang zu
erreichen kann, kann man also den Funktionswert von
bei
in Richtung
„stark“ verringern und ist für den kleinsten Eigenwert unter allen negativen Eigenwerten die größtmögliche Verringerung zu erwarten. Insbesondere ist
im Fall
eine Abstiegsrichtung für
in
und wird die „geeignete Skalierung“ von
im Verfahren durch die Wahl des Trust-Region-Radius
erzielt.
Ein Sattelpunkt
von
ist ja ein kritischer Punkt von
, der weder ein lokaler Minimalpunkt noch ein lokaler Maximalpunkt ist (vgl. Abschnitt 1.3). Hat man nun z. B. mit einem Abstiegsverfahren einen Punkt ermittelt, der entweder ein lokaler Minimalpunkt oder ein Sattelpunkt ist und will man möglichst weitgehend Letzteres ausschließen, so ermitttle man - zweimal stetige Differenzierbarkeit von
vorausgesetzt - die Eigenwerte von
(vgl. Beispiel 1.16). Sind diese alle nichtnegativ und ist mindestens einer von ihnen Null, so kann man offenbar nach wie vor keine Aussage darüber machen, ob es sich bei
um einen lokalen Minimalpunkt handelt. Gibt es jedoch unter den Eigenwerten mindestens einen negativen, so ist
ein Sattelpunkt und stellt offenbar jeder zugehörige Eigenvektor eine Richtung dar, in die fortschreitend man dem kritischen Punkt „entkommen“ und gleichzeitig den Funktionswert von
reduzieren kann (ersetze
durch
in der obigen Argumentation).
Da für den Cauchy-Punkt in (8.30)
gilt und somit bei einer Wahl von
wie in (8.32) oder (8.33) für eine Lösung
von Problem
die Abschätzung

gültig ist, ist anzunehmen, dass man in diesen Fällen einen größeren Abstieg bezüglich des aktuellen Funktionswertes von
als für die Wahl
erreichen kann. Man beachte aber, dass man noch die Vektoren
und gegebenenfalls
orthonormalisieren muss. Letzteres macht man mit dem Gram-Schmidt-Orthogonalisierungsverfahren (Satz 5.4, zuzüglich einer Normierung der Vektoren).
Die Konvergenzaussagen für das Trust-Region-Newton-Verfahren können auf das Teilraum-Trust-Region-Newton-Verfahren übertragen werden, sofern der Teilraum
die Gradientenrichtung
bzw. sowohl die Gradientenrichtung
als auch die Newton-Richtung
enthält. So hat man in Analogie zu Lemma 8.6 zunächst das folgende Ergebnis.
- Sei
. Dann gilt für jede Lösung
von Problem

- wobei
für
gesetzt werde.
Da anderenfalls Algorithmus 8.12 in Schritt (1) abbrechen würde, ist
. Ferner sind wegen
auch alle Vielfachen von
Elemente von
. Da die beiden im Beweis von Lemma 8.6 verwendeten Vergleichsvektoren
Vielfache von
sind, lässt sich der Beweis jenes Lemmas unmittelbar auf die Situation von Problem
übertragen.
q.e.d.
Lemma 8.14 garantiert die Durchführbarkeit von Algorithmus 8.12, da der Nenner in
nur im Fall
identisch Null sein kann und dieser Fall durch die Abfrage in Schritt (1) von Algorithmus 8.12 ausgeschlossen ist. Wir erhalten weiter:
- Sei
und
für alle
. Weiter sei (V2) erfüllt. Bricht Algorithmus 8.12 nicht ab, dann besitzt die durch ihn erzeugte Folge
einen Häufungspunkt und jeder solche Häufungspunkt ist ein kritischer Punkt von
.
Man sieht leicht ein, dass Lemma 8.7 analog für Algorithmus 8.12 bewiesen und somit der Beweis von Satz 8.8 auch auf die Situation von Algorithmus 8.12 übertragen werden kann. Statt Lemma 8.6 ist dabei das Lemma 8.14 anzuwenden.
q.e.d.
Ähnlich wie Satz 8.10 kann ferner der folgende Satz unter Verwendung von Lemma 8.14 bewiesen werden.
- Es sei (V5) erfüllt und
sei die dann existierende eindeutige Lösung von
. Weiter sei
für alle
. Dann bricht Algorithmus 8.12 entweder ab oder er erzeugt eine Folge
, für welche gilt:
- (i)

- (ii) Es ist
für alle
mit einem
.
- (iii) Es ist
für alle
mit einem
.
Der Beweis von Satz 8.11 über die Konvergenzgeschwindigkeit des Trust-Region-Newton-Verfahrens lief darauf hinaus zu zeigen, dass die Newton-Richtung
für alle hinreichend großen
das Teilproblem
löst und dass das Verfahren somit lokal in das klassische Newton-Verfahren übergeht. Wenn wir also zusätzlich zu
auch
fordern, so ist
auch eine Lösung von Problem
für alle hinreichend großen
. Folglich haben wir abschließend:
- Es sei (V5) erfüllt und
sei die dann existierende eindeutige Lösung von
. Ferner seien
für alle
. Dann bricht Algorithmus 8.12 entweder ab oder er erzeugt eine Folge
, für welche gilt:
- (i)
konvergiert superlinear gegen
.
- (ii) Hat man mit einem
und einem

- dann konvergiert
quadratisch gegen
.