Benutzer:Stepri2005/Kurs:Optimierung II/Trust-Region-Verfahren

Wir haben bisher Verfahren zur Lösung des Problems

$(P):{\text{ Minimiere }}f(x){\mbox{ über alle }}x\in \mathbb {R} ^{n}$

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

$f_{k}(x):=f(x^{k})+\nabla f(x^{k})^{T}\left(x-x^{k}\right)+{\frac {1}{2}}\left(x-x^{k}\right)^{T}H_{k}\left(x-x^{k}\right)$

für die Zielfunktion $f$ bei $x^{k}$ herleiten, wobei $H_{k}\in \mathbb {R} ^{n\times n}$ eine symmetrische, positiv definite Matrix ist. Wählt man nämlich den Minimalpunkt $x^{k+1}$ dieser Funktion, welcher sich aus der Gleichung

$0=\nabla f_{k}(x^{k+1})=\nabla f(x^{k})+H_{k}\left(x^{k+1}-x^{k}\right)$

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

$p^{k}:=x^{k+1}-x^{k}=-H_{k}^{-1}\nabla f(x^{k}).$

Insbesondere ist beim Gradientenverfahren $H_{k}:=I$, beim Newton-Verfahren $H_{k}:=\nabla ^{2}f(x^{k})$ und bei den Quasi-Newton-Verfahren $H_{k}:=B_{k}^{-1}$, wobei $B_{k}^{-1}$ 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 $f$ 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 $k$-ten Iteration für die durch eine symmetrische, aber nicht notwendig positiv definite (!) Matrix $H_{k}:=B_{k}$ bestimmte quadratische Näherung von $f(x^{k}+d)$

$q_{k}(d):={\frac {1}{2}}d^{T}B_{k}d+\nabla f(x^{k})^{T}d+f(x^{k})$

und für ein $\Delta _{k}>0$, welches möglicherweise noch geeignet anzupassen ist, eine globale Lösung des sog. Trust-Region-Teilproblems

(8.1) ${\begin{array}{lll}(T)_{k}:&{\text{Minimiere}}&q_{k}(d)\\&{\text{u. d. N.}}&\|d\|\leq \Delta _{k},\end{array}}$

bei dem über $d\in \mathbb {R} ^{n}$ zu minimieren ist. Da $q_{k}$ auf $\mathbb {R} ^{n}$ stetig und der zulässige Bereich von $(T)_{k}$ wegen $\|0\|\leq \Delta _{k}$ nichtleer ist, hat dieses Problem nach dem Satz von Weierstraß eine (globale) Lösung, die aber nicht notwendig eindeutig und eine Abstiegsrichtung für $f$ in $x^{k}$ sein muss. (Deshalb bezeichnen wir in diesem Abschnitt Richtungen, engl. „directions“, auch mit „$d$“, um keine Verwechslungen aufkommen zu lassen.)

Die Konstante $\Delta _{k}>0$ ist dabei eine in jeder Iteration geeignet zu wählende Konstante, welche den Radius des Trust-Regions, des Vertrauensbereichs, festlegt. Wenn der Schritt von $x^{k}$ in Richtung der ermittelten Lösung $d^{k}$ von $(T)_{k}$ nach einem noch festzulegenden Kriterium als akzeptabel oder erfolgreich interpretiert werden kann, wird

$x^{k+1}:=x^{k}+d^{k}$

gesetzt und $\Delta _{k}$ für die nächste Iteration beibehalten bzw. vergrößert. Im anderen Fall setzt man $x^{k+1}:=x^{k}$, verkleinert man $\Delta _{k}$ und löst man $(T)_{k}$ erneut. Wie wir bereits in Abschnitt 2.1 diskutiert hatten, wird man dann normalerweise eine andere Richtung erhalten.

Eventuell hat man also das Problem $(T)_{k}$ 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

$\|d\|_{\infty }\leq \Delta _{k}\Leftrightarrow \max _{1\leq i\leq n}|d_{i}|\leq \Delta _{k}\Leftrightarrow \pm d_{i}\leq \Delta _{k}\quad (i=1,\ldots ,n)$

mit $d:=(d_{1},\ldots ,d_{n})^{T}$ äquivalent durch $2n$ 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 $\mathbb {R} ^{n}$ zu lösen ist.

8.1 Das Trust-Region-Teilproblem

Wir wollen uns nun zunächst mit dem Trust-Region-Teilproblem beschäftigen. Der Einfachheit halber betrachten wir das von $k$ unabhängige Problem

${\begin{array}{lll}(T):&{\text{Minimiere}}&q(d):={\frac {1}{2}}d^{T}Bd+g^{T}d+\delta \\&{\text{u. d. N.}}&\|d\|\leq \Delta \end{array}}$

mit einer symmetrischen Matrix $B\in \mathbb {R} ^{n\times n},g\in \mathbb {R} ^{n},\delta \in \mathbb {R}$ und einer Konstanten $\Delta >0$, wobei über $d\in \mathbb {R} ^{n}$ zu minimieren ist. Die Funktion $q$ bezeichnen wir als Zielfunktion und die Ungleichung $\|d\|\leq \Delta$ als (Ungleichungs-) Nebenbedingung. Einen Vektor $d$ mit $\|d\|\leq \Delta$ nennen wir zulässig. Letztere Nebenbedingung in Problem $(T)$ können wir auch quadrieren und äquivalent durch

$d^{T}d\leq \Delta ^{2}$

ersetzen. Die Menge aller für $(T)$ zulässigen Vektoren, der zulässige Bereich von $(T)$, ist offenbar konvex und wegen $\|0\|\leq \Delta$ nichtleer.

Wie bereits gesagt wurde, hat das Problem $(T)$ eine Lösung. Im Fall, dass $B$ positiv definit ist, ist $q$ gleichmäßig konvex und besitzt $(T)$ somit eine eindeutige Lösung $d^{*}$ (vgl. Satz 1.9). Da $B$ aber hier nicht positiv definit sein muss, kann $(T)$ auch lokale, nichtglobale Lösungen und mehr als eine globale Lösung besitzen. Erstaunlicherweise kann man jedoch globale Lösungen von $(T)$ vollständig charakterisieren, wie der folgende Satz angibt.

Satz 8.1

$d^{*}$ ist genau dann eine globale Lösung von Problem $(T)$, wenn es ein $\mu ^{*}\in \mathbb {R}$ gibt, so dass die folgenden Bedingungen erfüllt sind:

(a) $\mu ^{*}\geq 0,\|d^{*}\|\leq \Delta ,\mu ^{*}(\|d^{*}\|-\Delta )=0,$

(b) $(B+2\mu ^{*}I)d^{*}=-g,$

(c) $B+2\mu ^{*}I$ ist positiv semidefinit.

Beweis.

Es sei $d^{*}$ eine globale Lösung von $(T)$. Dann ist $d^{*}$ auch globale Lösung des zu $(T)$ äquivalenten Problems, das man erhält, wenn man die Ungleichung in $(T)$ gegen die Ungleichung $c(d)\leq 0$ mit

$c(d):=\|d\|^{2}-\Delta ^{2}$

austauscht. Ist nun diese Nebenbedingung inaktiv, d. h. $c(d^{*})<0$ bzw. $\|d^{*}\|<\Delta$, dann ist $d^{*}$ lokaler Minimalpunkt des unrestringierten Problems $\min _{d\in \mathbb {R} ^{n}}q(d)$ und sind nach Satz 1.14 die Bedingungen (a), (b) und (c) mit $\mu ^{*}:=0$ und wegen der dritten Bedingung in (a) nur für dieses $\mu ^{*}$ erfüllt.

Also nehmen wir an, die Nebenbedingung sei aktiv, d. h. es gelte $c(d^{*})=0$ und damit $d^{*}\neq 0$ und $\nabla c(d^{*})=2d^{*}$. Sei nun $v\in \mathbb {R} ^{n}$ ein Vektor mit $v^{T}d^{*}<0$. Dann ist

(8.2) ${\hat {t}}:=-2{\frac {v^{T}d^{*}}{\|v\|^{2}}}>0$

und es gilt

$\left\|d^{*}+{\hat {t}}v\right\|^{2}=\left(d^{*}+{\hat {t}}v\right)^{T}\left(d^{*}+{\hat {t}}v\right)=\|d^{*}\|^{2}+2{\hat {t}}v^{T}d^{*}+{\hat {t}}^{2}\|v\|^{2}=\|d^{*}\|^{2}.$

Folglich liegen alle Vektoren

$\tau (d^{*}+{\hat {t}}v)+(1-\tau )d^{*}=d^{*}+\tau {\hat {t}}v$

mit $\tau \in (0,1]$ bzw. alle Vektoren $d^{*}+tv$ mit $t\in (0,{\hat {t}}]$ in der Kugel um 0 mit Radius $\Delta$ und sind damit zulässig für $(T)$. Da $d^{*}$ globaler Minimalpunkt von $(T)$ ist, gilt demnach weiter für alle $t\in (0,{\hat {t}}]$

(8.3) $0\leq q(d^{*}+tv)-q(d^{*})=t(g+Bd^{*})^{T}v+{\frac {1}{2}}t^{2}v^{T}Bv,$

was nach Division durch $t>0$ und Grenzübergang für $t\to 0+$

$(g+Bd^{*})^{T}v\geq 0$

liefert. Also gibt es keinen Vektor, der beiden Ungleichungen

$(g+Bd^{*})^{T}v<0,\quad (d^{*})^{T}v<0$

gleichzeitig genügt.

Nun stellt man fest: gibt es keinen Vektor $v\in \mathbb {R} ^{n}$ mit $v\neq 0$, welcher für zwei Vektoren $y,z\in \mathbb {R} ^{n}$ die Ungleichungen

$y^{T}v<0,\quad z^{T}v<0$

gleichzeitig erfüllt, so muss $y=-\mu z$ mit einem $\mu \in \mathbb {R}$ sein. Denn anderenfalls wäre die Cauchy-Schwarz-Ungleichung strikt erfüllt, d. h. wäre

$y^{T}z\leq \left|y^{T}z\right|<\|y\|\|z\|$

und erhielte man dagegen für $v:=-\|z\|y-\|y\|z$

$y^{T}v=y^{T}(-\|z\|y-\|y\|z)=-\|z\|\|y\|^{2}-\|y\|y^{T}z=\|y\|\left(-\|z\|\|y\|-y^{T}z\right)<0,$

$y^{T}v=z^{T}(-\|z\|y-\|y\|z)=-\|z\|z^{T}y-\|y\|\|z\|^{2}=\|z\|\left(-\|z\|\|y\|-y^{T}z\right)<0.$

Also besitzen die beiden Ungleichungen $-\mu z^{T}v<0$ und $z^{T}v<0$ keine Lösung. Damit ist $\mu \geq 0$, da anderenfalls $v:=-z$ eine Lösung dieser Ungleichungen wäre.

Folglich ist mit einem eindeutig bestimmten $\mu ^{*}\geq 0$

(8.4) $g+Bd^{*}=-2\mu ^{*}d^{*},$

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) $t:={\hat {t}}$ und folgern wir unter Verwendung von (8.4) und (8.2)

$0\leq {\hat {t}}(g+Bd^{*})Tv+{\frac {1}{2}}{\hat {t}}^{2}v^{T}Bv=-2{\hat {t}}\mu ^{*}(d^{*})^{T}v+{\frac {1}{2}}{\hat {t}}^{2}v^{T}Bv={\frac {1}{2}}{\hat {t}}^{2}v^{T}(B+2\mu ^{*}I)v.$

Demzufolge hat man $v^{T}(B+2\mu ^{*}I)v\geq 0$ für alle $v\in \mathbb {R} ^{n}$ mit $v^{T}d^{*}<0$ und damit für alle $v\in \mathbb {R} ^{n}$ mit $v^{T}d^{*}\neq 0$, wie man mittels Ersetzung von $v$ durch $-v$ ersieht. Somit ist

$v^{T}(B+2\mu ^{*}I)v\geq 0,\quad v\in \mathbb {R} ^{n}.$

Denn anderenfalls gäbe es ein ${\hat {v}}$ mit ${\hat {v}}^{T}(B+2\mu ^{*}I){\hat {v}}<0$ und ${\hat {v}}^{T}d^{*}=0$ und könnte man eine Folge $\left\{v^{j}\right\}$ mit $(v^{j})^{T}d^{*}\neq 0$ sowie $\lim _{j\to \infty }v^{j}={\hat {v}}$ konstruieren, was aber $(v^{j})^{T}(B+2\mu ^{*}I)v^{j}\geq 0$ und damit ${\hat {v}}^{T}(B+2\mu ^{*}I){\hat {v}}\geq 0$ zur Folge hätte. Also ist auch (c) erfüllt.

Umgekehrt seien nun die Bedingungen (a) - (c) für $d^{*}$ und $\mu ^{*}$ erfüllt. Insbesondere ist somit $\|d^{*}\|\leq \Delta$. Dann folgt unter Verwendung von (a), (b) und (c) für alle Vektoren $d$ mit $\|d\|\leq \Delta$

$q(d)-q(d^{*})={\frac {1}{2}}(d-d^{*})^{T}B(d-d^{*})+(Bd^{*}+g)^{T}(d-d^{*})$

$={\frac {1}{2}}(d-d^{*})^{T}(B+2\mu ^{*}I)(d-d^{*})-\mu ^{*}\|d-d^{*}\|^{2}-2\mu ^{*}(d-d^{*})^{T}d^{*}$

(8.5) $\geq -\mu ^{*}\|d-d^{*}\|^{2}-2\mu ^{*}d^{T}d^{*}+2\mu ^{*}\|d^{*}\|^{2}=\mu ^{*}\left(\|d^{*}\|^{2}-\|d\|^{2}\right)$

$=\mu ^{*}\left(\|d^{*}\|^{2}-\Delta ^{2}\right)+\mu ^{*}\left(\Delta ^{2}-\|d\|^{2}\right)\geq 0.$

Also ist $d^{*}$ globaler Minimalpunkt von $(T)$.

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 $B$ hinreichend dafür ist, dass das Problem $(T)$ eine eindeutige Lösung besitzt. Das erste Korollar besagt, dass es für die Existenz einer eindeutigen Lösung genügt, dass die Matrix $B+\mu ^{*}I$ positiv definit ist (was eine stärkere Annahme als die der positiven Definitheit von $B+2\mu ^{*}I$ ist).

Korollar 8.2

Sei $d^{*}$ globaler Minimalpunkt von $(T)$ und $\mu ^{*}$ eine Zahl, welche zusammen mit $d^{*}$ den Bedingungen (a), (b) und (c) von Satz 8.1 genügt. Ist die Matrix $B+\mu ^{*}I$ positiv definit, so ist $d^{*}$ einziger globaler Minimalpunkt von $(T)$.

Beweis.

Sei $d$ ein Vektor mit $d\neq d^{*}$ und $\|d\|\leq \Delta$. Da nach Voraussetzung $B+\mu ^{*}I$ positiv definit ist, hat man

$(d-d^{*})^{T}(B+2\mu ^{*}I)(d-d^{*})>0.$

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

$q(d)-q(d^{*})>0.$

q.e.d.

Bei dem nächsten Resultat beachte man, dass z. B. in der $k$-ten Iteration des Trust-Region-Newton-Verfahrens, welches im nächsten Abschnitt behandelt wird, $g:=\nabla f(x^{k})$ und $B:=\nabla ^{2}f(x^{k})$ ist.

Korollar 8.3

Sei $d^{*}$ globaler Minimalpunkt von $(T)$. Dann sind die folgenden Aussagen äquivalent:

(a) $q(d^{*})=\delta ,$

(b) $g=0$ und $B$ ist positiv semidefinit.

Beweis.

Ü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 $(P)$ in dem aktuellen $x^{k}$ erfüllt sind oder nicht.

Bisher haben wir nur globale Minimalpunkte für Problem $(T)$ diskutiert. Ein interessantes Ergebnis in diesem Zusammenhang ist das folgende (s. [Mar94]).

Satz 8.4

Das Problem $(T)$ besitzt höchstens einen lokalen Minimalpunkt, der kein globaler Minimalpunkt von $(T)$ ist.

8.2 Das Trust-Region-Newton-Verfahren

In diesem Abschnitt wollen wir eine Trust-Region-Variante des Newton-Verfahrens vorstellen. Dazu sei $f\in C^{2}(\mathbb {R} ^{n})$ und mit einer symmetrischen Matrix $B_{k}\in \mathbb {R} ^{n\times n}$ durch

(8.6) $q_{k}(d):={\frac {1}{2}}d^{T}B_{k}d+\nabla f(x^{k})^{T}d+f(x^{k})$

eine quadratische Näherung für $f(x^{k}+d)$ definiert. Da wir an einem Newton-ähnlichen Verfahren interessiert sind, setzen wir hier speziell

$B_{k}:=\nabla ^{2}f(x^{k})$

(vgl. Kapitel 6). Damit ist die Zielfunktion des Trust-Region-Teilproblems in der $k$-ten Iteration wohldefiniert. Wie zuvor bezeichne $d^{k}$ eine globale Lösung dieses Problems.

Die entscheidende Frage ist nun, wie man den Radius $\Delta _{k}$ des Vertrauensbereichs steuert. Die Entscheidung, ob $\Delta _{k+1}$ gegenüber $\Delta _{k}$ vergrößert oder verkleinert werden sollte, macht man im Allgemeinen von dem Wert der Zahl

$r_{k}:={\frac {f(x^{k})-f(x^{k}+d^{k})}{f(x^{k})-q_{k}(d^{k})}}$

abhängig. Der Zähler von $r_{k}$ gibt offenbar die tatsächliche Reduktion des Funktionswertes von $f$ an, die man bei einem Übergang von $x^{k}$ zu $x^{k+1}:=x^{k}+d^{k}$ erreicht, während der Nenner die durch das quadratische Modell vorausgesagte Reduktion beschreibt. Da 0 zulässiger Punkt von $(T)$ ist und somit

(8.7) $f(x^{k})=q_{k}(0)-q_{k}(d^{k})$

gilt, ist der Nenner von $r_{k}$ nichtnegativ.

Ist also $r_{k}\approx 1$ oder $r_{k}>1$, so scheint $q_{k}$ eine gute oder eher pessimistische quadratische Approximation von $f$ bei $x^{k}$ zu sein. Daher kann man in einem solchen Fall $x^{k+1}:=x^{k}+d^{k}$ setzen und den Radius $\Delta _{k+1}$ entweder gleich $\Delta _{k}$ oder größer als $\Delta _{k}$ wählen. Ist dagegen $r_{k}$ klein oder sogar negativ, also die durch das quadratische Modell vorausgesagte Reduktion des Funktionswertes von $f$ größer als die reale, so sollte man $x^{k+1}:=x^{k}$ und $\Delta _{k+1}<\Delta _{k}$ wählen. Diese Überlegungen spiegeln sich in dem folgenden Verfahren wieder. Dabei sei wieder

$g^{k}:=\nabla f(x^{k}).$

Algorithmus 8.5 (Trust-Region-Newton-Verfahren)

(0) Wähle $x^{0}\in \mathbb {R} ^{n},\Delta _{0}>0,\Delta _{\min }>0,0<\varrho _{1}<\varrho _{2}<1$ und $0<\sigma _{1}<1<\sigma _{2}$ und setze $k:=0$.

(1) Falls $g^{k}=0$ ist, stop! ($x^{k}$ ist kritische Lösung von Problem $(P)$.)

(2) Bestimme eine globale Lösung $d^{k}$ des Problems

${\begin{array}{lll}(TN)_{k}:&{\text{Minimiere}}&q_{k}(d):={\frac {1}{2}}d^{T}\nabla ^{2}f(x^{k})d+(g^{k})^{T}d+f(x^{k})\\&{\text{u. d. N.}}&\|d\|\leq \Delta _{k}.\end{array}}$

(3) Berechne

(8.8) $r_{k}:={\frac {f(x^{k})-f(x^{k}+d^{k})}{f(x^{k})-q_{k}(d^{k})}}$

und setze

(8.9) $\Delta _{k+1}:={\begin{cases}\sigma _{1}\Delta _{k},&{\text{falls }}r_{k}<\varrho _{1},\\\max(\Delta _{\min },\Delta _{k}),&{\text{falls }}r_{k}\in [\varrho _{1},\varrho _{2}),\\\max(\Delta _{\min },\sigma _{2}\Delta _{k}),&{\text{falls }}r_{k}\geq \varrho _{2}\end{cases}}$

sowie

(8.10) $x^{k+1}:={\begin{cases}x^{k},&{\text{falls }}r_{k}<\varrho _{1},\\x^{k}+d^{k},{\text{falls }}r_{k}\geq \varrho _{1}.\end{cases}}$

(4) Setze $k:=k+1$ und gehe nach (1).

Dass der Nenner von $r_{k}$ 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.

$\Delta _{0}:=1,\quad \Delta _{\min }:=10^{-2},\quad \varrho _{1}:=0.1,\quad \varrho _{2}:=0.75,\quad \sigma _{1}:=0.5,\quad \sigma _{2}:=2.$

Die Abfrage $r_{k}\approx 1$ oder $r_{k}>1$ 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) $f(x^{k})\geq f(x^{k+1})$

hat. Denn für festes $k$ ist entweder $r_{k}<\varrho _{1}$ und damit

$x^{k+1}=x^{k},\quad f(x^{k+1})=f(x^{k})$

oder es ist $r_{k}\geq \varrho _{1}>0$ und folglich wegen (8.7) der Zähler $f(x^{k})-f(x^{k+1})$ von $r_{k}$ positiv. Eine Iteration, für die $r_{k}\geq \varrho _{1}>0$ 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 $\Delta _{\min }$ 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 $B_{k}$ statt $\nabla ^{2}f(x^{k})$, wenn ein Ergebnis für eine beliebige symmetrische Matrix $B_{k}$ gültig ist. Zunächst leiten wir eine untere Abschätzung für den Nenner in der Konstanten $r_{k}$ her, welche ja für die Größe des Trust-Regions bestimmend ist.

Lemma 8.6

Sei $d^{k}$ eine Lösung von Problem $(TN)_{k}$. Dann ist

$f(x^{k})-q_{k}(d^{k})\geq {\frac {1}{2}}\left\|g^{k}\right\|\min \left\{\Delta _{k},{\frac {\left\|g^{k}\right\|}{\left\|B_{k}\right\|}}\right\},$

wobei $\left\|g^{k}\right\|/\left\|B_{k}\right\|=+\infty$ für $B_{k}=0$ gesetzt werde.

Beweis.

Da $d^{k}$ globale Lösung des Teilproblems $(TN)_{k}$ ist, gilt für jedes $d$ mit $\|d\|\leq \Delta _{k}$, also für jedes für das Problem $(TN)_{k}$ zulässige $d$:

(8.12) $f(x^{k})-q_{k}(d^{k})\geq f(x^{k})-q_{k}(d)=-{\frac {1}{2}}d^{T}B_{k}d-(g^{k})^{T}d\geq -{\frac {1}{2}}\left\|B_{k}\right\|\left\|d\right\|^{2}-(g^{k})^{T}d.$

Im Fall $\Delta _{k}\left\|B_{k}\right\|\leq \left\|g^{k}\right\|$ ergibt sich damit für den Vektor $d:=-(\Delta _{k}\left\|g^{k}\right\|)g^{k}$, der offenbar für $(TN)_{k}$ zulässig ist,

$f(x^{k})-q_{k}(d^{k})\geq -{\frac {1}{2}}\Delta _{k}^{2}\left\|B_{k}\right\|+\Delta _{k}\left\|g^{k}\right\|\geq {\frac {1}{2}}\Delta _{k}\left\|g^{k}\right\|$

Ist andererseits $\Delta _{k}\left\|B_{k}\right\|>\left\|g^{k}\right\|$ und damit insbesondere $B_{k}\neq 0$, so ergibt sich für den Vektor $d:=-(1/\left\|B_{k}\right\|)g^{k}$

$\|d\|={\frac {\left\|g^{k}\right\|}{\left\|B_{k}\right\|}}<\Delta _{k}$

und folgt somit aus (8.12)

$f(x^{k})-q_{k}(d^{k})\geq -{\frac {\left\|g^{k}\right\|^{2}}{2\left\|B_{k}\right\|}}+{\frac {\left\|g^{k}\right\|^{2}}{\left\|B_{k}\right\|}}={\frac {1}{2}}{\frac {\left\|g^{k}\right\|^{2}}{\left\|B_{k}\right\|}}.$

Kombination der gewonnenen Ungleichungen liefert das gewünschte Ergebnis.

q.e.d.

Aus dem letzten Lemma schließt man, dass der Nenner von $r_{k}$ in (8.8) nur im Fall $g^{k}=0$ 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 $f$ konvergieren.

Lemma 8.7

Sei $f\in C^{2}(\mathbb {R} ^{n})$ und Algorithmus 8.5 breche nicht nach endlich vielen Iterationen ab. Ist $\left\{x^{k_{i}}\right\}$ eine Teilfolge der dann von ihm erzeugten Folge $\left\{x^{k}\right\}$, welche gegen ein $x^{*}$ mit $\nabla f(x^{*})\neq 0$ konvergiert, so folgt

$\liminf _{i\to \infty }\Delta _{k_{i}}>0.$

Beweis.

Sei $j_{i}:=k_{i}-1$. Dann konvergiert nach Voraussetzung $\left\{x^{j_{i}+1}\right\}$ gegen $x^{*}$ und ist

$\ell :=\liminf _{i\to \infty }\Delta _{j_{i}+1}>0$

zu zeigen.

Angenommen, es wäre $\ell =0$. Da wir gleich zu einer geeigneten Teilfolge von $\left\{x^{k}\right\}$ hätten übergehen können, können wir dafür ohne Beschränkung der Allgemeinheit annehmen, dass gilt:

$\lim _{i\to \infty }\Delta _{j_{i}+1}=0.$

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

(8.13) $\Delta _{j_{i}+1}<\Delta _{\min },\quad r_{j_{i}}<\varrho _{1},\quad \Delta _{j_{i}+1}:=\sigma _{1}\Delta _{j_{i}},\quad x^{j_{i}+1}:=x^{j_{i}}.$

Aus der vorausgesetzten Konvergenz der Folge $\left\{x^{j_{i}+1}\right\}$ gegen $x^{*}$ erschließt man damit die Konvergenz von $\left\{x^{j_{i}}\right\}$ gegen $x^{*}$ und wegen $\sigma _{1}>0$ folgert man $\lim _{i\to \infty }\Delta _{j_{i}}=0$ und somit

(8.14) $\lim _{i\to \infty }\left\|d^{j_{i}}\right\|=0.$

Aufgrund der Voraussetzung $\nabla f(x^{*})\neq 0$ gilt nun weiter - ohne Beschränkung der Allgemeinheit für die ganze Folge $\left\{x^{j_{i}}\right\}$ - mit einer Konstanten $\beta _{1}>0$

(8.15) $\left\|g^{j_{i}}\right\|=\left\|\nabla f(x^{j_{i}})\right\|\geq \beta _{1},\quad i\in \mathbb {N} .$

Ferner ist $\left\{x^{j_{i}}\right\}$ als konvergente Folge beschränkt, so dass es wegen $f\in C^{2}(\mathbb {R} ^{n})$ eine Konstante $\beta _{2}>0$ gibt mit

(8.16) $\left\|B_{j_{i}}\right\|=\left\|\nabla ^{2}f(x^{j_{i}})\right\|\leq \beta _{2},\quad i\in \mathbb {N}$

und damit

$\lim _{k\to \infty }\Delta _{k+1}=0,\quad \lim _{k\to \infty }x^{k+1}=x^{k_{0}}.$

Weiter wäre dann $\nabla f(x^{k_{0}})\neq 0$, da der Algorithmus anderenfalls in Schritt (1)abgebrochen wäre. Dies widerspräche aber Lemma 8.7 bezogen auf die Teilfolge $\left\{x^{k+1}\right\}$ von $\left\{x^{k}\right\}$.

Es sei nun $\left\{x^{k_{i}}\right\}$ eine Teilfolge von $\left\{x^{k}\right\}$ mit

(8.19) $\lim _{i\to \infty }x^{k_{i}}=x^{*}.$

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

$x^{k_{i}+\ell (i)}=x^{k_{i}+\ell (i)-1}=\ldots =x^{k_{i}+1}=x^{k_{i}}$

für ein $\ell (i)\geq 1$ gilt, wobei die Iterationen $k_{i}+1,\ldots ,k_{i}+\ell (i)-1$ nicht erfolgreich sind und die Iteration $k_{i}+\ell (i)$ erfolgreich ist. Da es insgesamt unendlich viele erfolgreiche Iterationen gibt, können wir auf diese Weise jedem $x^{k_{i}}$, das zu einer nicht erfolgreichen Iteration gehört, (gegebenenfalls auch mehreren $x^{k_{i}}$ hintereinander gleichzeitig) ein mit diesem identisches Folgenglied $x^{k_{i}+\ell (i)}$ von $\left\{x^{k}\right\}$ aus einer erfolgreichen Iteration zuordnen und so eine gegen $x^{*}$ konvergierende Teilfolge von $\left\{x^{k}\right\}$ erzeugen, deren Glieder ausschließlich zu erfolgreichen Iterationen gehören. Ohne Beschränkung der Allgemeinheit sei dies die Folge $\left\{x^{k_{i}}\right\}$ selbst, sei also $r_{k_{i}}\geq \varrho _{1},i\in \mathbb {N}$.

Es sei nun $\nabla f(x^{*})\neq 0$ angenommen. Dann existieren - ohne Beschränkung der Allgemeinheit für die ganze Folge $\left\{x^{k_{i}}\right\}$ - Konstanten $\beta _{1}>0$ und $\beta _{2}>0$ mit

(8.20) $\left\|g^{k_{i}}\right\|=\left\|\nabla f(x^{k_{i}})\right\|\geq \beta _{1},\quad \left\|B_{k_{i}}\right\|=\left\|\nabla ^{2}f(x^{k_{i}})\right\|\leq \beta _{2},\quad i\in \mathbb {N} .$

Lemma 8.6 impliziert demzufolge zusammen mit (8.20) für alle $i\in \mathbb {N}$

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

(8.21) $\geq {\frac {1}{2}}\varrho _{1}\beta _{1}\min \left\{\Delta _{k_{i}},{\frac {\beta _{1}}{\beta _{2}}}\right\}.$

Nun kann man aber wegen (8.19)

$\lim _{i\to \infty }f(x^{k_{i}})=f(x^{*})$

schließen, was mit (8.11)

$\lim _{i\to \infty }f(x^{k_{i}+1})=f(x^{*})$

nach sich zieht. Also implizieren die Abschätzungen in (8.21) die Konvergenz $\Delta _{k_{i}}\to 0$ $(i\to \infty )$. Letzteres steht aber im Widerspruch zu Lemma 8.7. Folglich ist $\nabla f(x^{*})=0$ und ist alles gezeigt.

q.e.d.

Wir betrachten nun die Situation, dass $f$ eine gleichmäßig konvexe Funktion ist, wobei wir auch hier wieder die Voraussetzung (V5) verwenden.

Lemma 8.9

Das Teilproblem $(TN)_{k}$ besitzt für jedes $k$ eine globale Lösung. Unter der Voraussetzung (V5) ist diese eindeutig.

Beweis.

Übung!

Unter der Voraussetzung (V5), welche gemäß Bemerkung 6.8 die Bedingungen (V1) - (V4) impliziert, hat man nun weiter das folgende Resultat.

Satz 8.10

Es sei (V5) erfüllt und es sei $x^{*}$ die somit existierende eindeutige Lösung von $(P)$. Dann bricht Algorithmus 8.5 entweder ab oder er erzeugt eine Folge $\left\{x^{k}\right\}$, für welche gilt:

(i) $\lim _{k\to \infty }x^{k}=x^{*}.$

(ii) Es ist $r_{k}\geq \varrho _{1}$ für alle $k\geq k_{0}$ mit einem $k_{0}\in \mathbb {N}$.

(iii) Es ist $\Delta _{k}\geq {\bar {\Delta }}$ für alle $k\in \mathbb {N}$ mit einem ${\bar {\Delta }}>0$.

Beweis.

(i) Sei $\left\{x^{k_{i}}\right\}$ eine konvergente Teilfolge von $\left\{x^{k}\right\}$. Nach Korollar 1.18 und Satz 8.8 gilt dann

(8.22) $\lim _{i\to \infty }x^{k_{i}}=x^{*}.$

Aufgrund der Stetigkeit von $f$ folgt damit

$\lim _{i\to \infty }f(x^{k_{i}})=f(x^{*})$

und dies wiederum impliziert wegen der Monotonie der Folge $\left\{f(x^{k})\right\}$ (siehe (8.11)) die Konvergenz der ganzen Folge $\left\{f(x^{k})\right\}$ gegen $f(x^{*})$. Die Konvergenz von $\left\{x^{k}\right\}$ gegen $x^{*}$ erschließt man nun mit Hilfe von Lemma 2.9 (iii).

(ii) Da $x^{k}$ wegen (8.11) für alle $k$ in $N_{0}$ liegt, folgt aus (V5) für $\beta :=1/M>0$

(8.23) $(d^{k})^{T}\nabla ^{2}f(x^{k})d^{k}\geq \beta \left\|d^{k}\right\|,\quad k\in \mathbb {N} .$

Weil der Vektor 0 für das Problem $(TN)_{k}$ zulässig ist, erhält man ferner

$q_{k}(d^{k})={\frac {1}{2}}(d^{k})^{T}\nabla ^{2}f(x^{k})d^{k}+(g^{k})^{T}d^{k}+f(x^{k})\leq f(x^{k}),$

so dass

${\frac {1}{2}}\beta \left\|d^{k}\right\|^{2}\leq {\frac {1}{2}}(d^{k})^{T}\nabla ^{2}f(x^{k})d^{k}\leq -(g^{k})^{T}d^{k}\leq \left\|g^{k}\right\|\left\|d^{k}\right\|$

und daher

(8.24) $\left\|d^{k}\right\|\leq {\frac {2}{\beta }}\left\|g^{k}\right\|,\quad k\in \mathbb {N}$

folgt. Weiter schließt man aus der Konvergenz $x^{k}\to x^{*}$ $(k\to \infty )$ und aufgrund der Stetigkeit von $\nabla ^{2}f$ die Existenz eines $c>0$ mit

$\left\|\nabla ^{2}f(x^{k})\right\|\leq c,\quad k\in \mathbb {N} .$

Daher ergibt sich mit $\left\|d^{k}\right\|\leq \Delta _{k}$, der Abschätzung (8.24) und Lemma 8.6

$f(x^{k})-q_{k}(d^{k})\geq {\frac {1}{2}}\left\|g^{k}\right\|\min \left\{\Delta _{k},{\frac {\left\|g^{k}\right\|}{\left\|\nabla ^{2}f(x^{k})\right\|}}\right\}\geq {\frac {1}{4}}\beta \left\|d^{k}\right\|\min \left\{\left\|d^{k}\right\|,{\frac {\beta }{2c}}\left\|d^{k}\right\|\right\}:=\kappa \left\|d^{k}\right\|^{2}$

für

$\kappa :={\frac {1}{4}}\beta \min \left\{1,{\frac {\beta }{2c}}\right\}.$

Nach dem Satz von Taylor gilt nun für ein $\xi ^{k}$ auf der Verbindungsstrecke von $x^{k}$ und $x^{k}+d^{k}$

$f(x^{k}+d^{k})=f(x^{k})+\nabla f(x^{k})^{T}d^{k}+{\frac {1}{2}}(d^{k})^{T}\nabla ^{2}f(\xi ^{k})d^{k}.$

Daher ergibt sich

$\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\|.$

Also schließt man unter Verwendung der Abschätzung in (8.25):

$|r_{k}-1|=\left|{\frac {f(x^{k}+d^{k})-q_{k}(d^{k})}{f(x^{k})-q_{k}(d^{k})}}\right|\leq {\frac {1}{2\kappa }}\left\|\nabla ^{2}f(\xi ^{k})-\nabla ^{2}f(x^{k})\right\|.$

Nun gilt $\lim _{k\to \infty }x^{k}=x^{*},\lim _{k\to \infty }d^{k}=0$ (wegen Aussage (i) und (8.24)) und damit auch $\lim _{k\to \infty }\xi ^{k}=x^{*}$. Demzufolge erhält man $\lim _{k\to \infty }r_{k}=1$ und somit $r_{k}\geq \varrho _{1}$ für alle hinreichend großen $k$.

(iii) Aus dem letzten Resultat und den Vorschriften in Schritt (3) von Algorithmus 8.5 folgt $\Delta _{k}\geq \Delta _{\min }$ für alle hinreichend großen $k$. 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:

Satz 8.11

Es sei (V5) erfüllt und es sei $x^{*}$ die dann existierende eindeutige Lösung von $(P)$. Dann bricht Algorithmus 8.5 entweder ab oder er erzeugt eine Folge $\left\{x^{k}\right\}$, für welche gilt:

(i) $\left\{x^{k}\right\}$ konvergiert superlinear gegen $x^{*}$.

(ii) Hat man mit einem $L>0$ und einem $\varepsilon >0$

$\left\|\nabla ^{2}f(x)-\nabla ^{2}f(x^{*})\right\|\leq L\left\|x-x^{*}\right\|,\quad x\in {\mathcal {U}}_{\varepsilon }(x^{*}),$

dann konvergiert $\left\{x^{k}\right\}$ quadratisch gegen $x^{*}$.

Beweis.

Unter der Voraussetzung (V5) gilt für $\beta :=1/M>0$ und für die Menge $N_{0}$ aus (2.9)

(8.26) $d^{T}\nabla ^{2}f(x)d\geq \beta \|d\|^{2},\qquad d\in \mathbb {R} ^{n},\quad x\in N_{0}.$

Da alle $x^{k}$ wegen der Monotonie der Folge $\left\{f(x^{k})\right\}$ in $N_{0}$ liegen, impliziert dies, dass $\nabla ^{2}f(x^{k})$ und somit $\left[\nabla ^{2}f(x^{k})\right]^{-1}$ für alle $k$ positiv definit ist. Daraus schließt man, dass die Newton-Richtung

$d_{N}^{k}:=-\left[\nabla ^{2}f(x^{k})\right]^{-1}g^{k}$

für jedes $k$ der eindeutige globale Minimalpunkt von $q_{k}$ bezüglich des ganzen Raumes $\mathbb {R} ^{n}$ ist.

Weiter impliziert die Eigenschaft von $f$ in (8.26), dass

$\left\|\left[\nabla ^{2}f(x^{k})\right]^{-1}\right\|\leq {\frac {1}{\beta }},\quad k\in \mathbb {N}$

gilt (vgl. Bemerkung 6.8). Demzufolge ergibt sich

$\left\|d_{N}^{k}\right\|\leq {\frac {1}{\beta }}\left\|g^{k}\right\|,\quad k\in \mathbb {N} .$

Aus Aussage (i) von Satz 8.10 folgt die Konvergenz $g^{k}\to 0$ $(k\to \infty )$, so dass letztere Ungleichung die Konvergenz $d_{N}^{k}\to 0$ $(k\to \infty )$ liefert. Da weiter nach Satz 8.10 $\Delta _{k}\geq {\bar {\Delta }}$ für ein ${\bar {\Delta }}>0$ und alle $k$ ist, hat man also $\left\|d_{N}^{k}\right\|\leq \Delta _{k}$ für alle hinreichend großen $k$. Für diese $k$ folgt

$q_{k}(d^{k})\leq q_{k}(d_{N}^{k})=\min _{d\in \mathbb {R} ^{n}}q_{k}(d)\leq q_{k}(d^{k})$

und ist demnach $d^{k}=d_{N}^{k}$ die Lösung von Problem $(TN)_{k}$. 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 $k$-ten Trust-Region-Teilproblems mit einer symmetrischen Matrix $B_{k}$ durch

$q_{k}(d):={\frac {1}{2}}d^{T}B_{k}d+(g^{k})^{T}d+f(x^{k})$

bestimmt, wobei $B_{k}$ 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 $B_{k}$ aber nicht mehr positiv definit sein und muss sich im Fall, dass $B_{k}$ positiv definit ist, diese Eigenschaft nicht auf $B_{k+1}$ übertragen. Letzteres ist ja beispielsweise für das BFGS-Verfahren gesichert, wenn $f$ gleichmäßig konvex ist (siehe Satz 7.14).

Für die Iterierten des BFGS-Verfahrens gilt im Fall der gleichmäßigen Konvexität von $f$ gemäß Satz 7.14 insbesondere die für den Nachweis der positiven Definitheit von $B_{k+1}$ benötigte Bedingung

$\sigma _{k}:=(s^{k})^{T}y^{k}=(x^{k+1}-x^{k})^{T}(g^{k+1}-g^{k})>0.$

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 $B_{k}$ positiv definit sind. Deshalb geht man gelegentlich so vor, dass man auch bei erfolgreichen Iterationen $B_{k+1}:=B_{k}$ wählt, wenn $\sigma _{k}\leq 0$ 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 $\{B_{k}\}$ voraussetzt. (Damit ist nämlich auch in diesem Fall die Abschätzung für die $B_{k_{i}}$ wie in (8.20) gesichert und lässt sich der Beweis ganz ähnlich führen.) Die Beschränktheit der Folge $\{B_{k}\}$ kann man dann in der Praxis künstlich erzwingen, indem man beispielsweise $B_{k}$ nicht aufdatiert, wenn $\|B_{k}\|$ eine vorgegebene Schranke überschreitet. Für Details verweisen wir auf die angegebene Literatur und insbesondere auf [GeiKa99].

8.3 Teilraum-Trust-Region-Newton-Verfahren

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 $\mathbb {R} ^{n}$, sondern nur über einen Teilraum des $\mathbb {R} ^{n}$ minimiert wird.

Es sei also $V_{k}$ ein weiter unten noch genauer spezifizierter Teilraum des $\mathbb {R} ^{n}$ und es sei $f\in C^{2}(\mathbb {R} ^{n})$. Wir betrachten dann die folgende Modifikation von Algorithmus 8.5:

Algorithmus 8.12 (Teilraum-Trust-Region-Newton-Verfahren)

(0) Wähle $x^{0}\in \mathbb {R} ^{n},\Delta _{0}>0,\Delta _{\min }>0,0<\varrho _{1}<\varrho _{2}<1$ und $0<\sigma _{1}<1<\sigma _{2}$ und setze $k:=0$.

(1) Falls $g^{k}=0$ ist, stop! ($x^{k}$ ist kritische Lösung von Problem $(P)$.)

(2) Bestimme eine globale Lösung $d^{k}$ des Problems

${\begin{array}{lll}(TT)_{k}:&{\text{Minimiere}}&q_{k}(d):={\frac {1}{2}}d^{T}\nabla ^{2}f(x^{k})d+(g^{k})^{T}d+f(x^{k})\\&{\text{u. d. N.}}&\|d\|\leq \Delta _{k},\\&&d\in V_{k}.\end{array}}$

(3) Berechne

$r_{k}:={\frac {f(x^{k})-f(x^{k}+d^{k})}{f(x^{k})-q_{k}(d^{k})}}$

und setze

$\Delta _{k+1}:={\begin{cases}\sigma _{1}\Delta _{k},&{\text{falls }}r_{k}<\varrho _{1},\\\max(\Delta _{\min },\Delta _{k}),&{\text{falls }}r_{k}\in [\varrho _{1},\varrho _{2}),\\\max(\Delta _{\min },\sigma _{2}\Delta _{k}),&{\text{falls }}r_{k}\geq \varrho _{2}\end{cases}}$

sowie

$x^{k+1}:={\begin{cases}x^{k},&{\text{falls }}r_{k}<\varrho _{1},\\x^{k}+d^{k},{\text{falls }}r_{k}\geq \varrho _{1}.\end{cases}}$

(4) Setze $k:=k+1$ und gehe nach (1).

Man überlege sich als Übung, warum das Trust-Region-Teilproblem $(TT)_{k}$ unter der Voraussetzung (V5) für jedes $k$ eine eindeutige Lösung besitzt.

Wir zeigen nun, dass das Teilproblem $(TT)_{k}$ in ein Problem vom Typ des ursprünglichen Teilproblems $(T)_{k}$ in (8.1) umgeschrieben werden kann. Da der Raum $V_{k}$ 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 $\mathbb {R} ^{n}$ minimiert wird.

Es sei also $V_{k}$ ein Teilraum des $\mathbb {R} ^{n}$ mit Dimension $s_{k}:=\dim(V_{k})$ und es mögen $v^{k,1},\ldots ,v^{k,s_{k}}\in \mathbb {R} ^{n}$ eine Orthonormalbasis von $V_{k}$ bilden. Die Bedingung $d\in V_{k}$ ist dann äquivalent damit, dass $\alpha _{i}\in \mathbb {R}$ $(i=1,\ldots ,s_{k})$ existieren mit

$d=\sum _{i=1}^{s_{k}}\alpha _{i}v^{k,i}.$

Die Orthonormalität der $v^{k,i}$ impliziert dabei die Beziehungen

$d^{T}d=\left(\sum _{i=1}^{s_{k}}\alpha _{i}v^{k,i}\right)^{T}\left(\sum _{j=1}^{s_{k}}\alpha _{j}v^{k,j}\right)=\sum _{i=1}^{s_{k}}\alpha _{i}^{2}.$

Das Problem $(TT)_{k}$ kann demnach auch folgendermaßen formuliert werden:

${\begin{array}{ll}{\text{Minimiere}}&{\frac {1}{2}}\left(\sum \limits _{i=1}^{s_{k}}\alpha _{i}v^{k,i}\right)^{T}\nabla ^{2}f(x^{k})\left(\sum \limits _{j=1}^{s_{k}}\alpha _{j}v^{k,j}\right)+\sum \limits _{i=1}^{s_{k}}\alpha _{i}(g^{k})^{T}v^{k,i}+f(x^{k})\\{\text{u. d. N.}}&{\sqrt {\sum \limits _{i=1}^{s_{k}}\alpha _{i}^{2}}}\leq \Delta _{k},\\&\alpha _{1},\ldots ,\alpha _{s_{k}}\in \mathbb {R} .\end{array}}$

Mit den Setzungen

$\alpha :=(\alpha _{1},\ldots ,\alpha _{s_{k}})^{T}\in \mathbb {R} ^{s_{k}},$

$a^{k}:=\left((g^{k})^{T}v^{k,1},\ldots ,(g^{k})^{T}v^{k,s_{k}}\right)^{T}\in \mathbb {R} ^{s_{k}},$

$A_{k}:=\left((v^{k,i})^{T}\nabla ^{2}f(x^{k})v^{k,j}\right)_{i,j=1,\ldots ,s_{k}}\in \mathbb {R} ^{s_{k}\times s_{k}}$

schreiben wir dieses Problem in der Form

(8.27) ${\begin{array}{ll}{\text{Minimiere}}&{\tilde {q}}_{k}(\alpha ):={\frac {1}{2}}\alpha ^{T}A_{k}\alpha +(a^{k})^{T}\alpha +f(x^{k})\\{\text{u. d. N.}}&\|\alpha \|\leq \Delta _{k},\end{array}}$

wobei über $\alpha \in \mathbb {R} ^{s_{k}}$ zu minimieren ist. Unsere Herleitung zeigt:

Satz 8.13

$d^{k}$ ist genau dann Lösung von Problem $(TT)_{k}$, wenn

(8.28) $d^{k}=\sum _{i=1}^{s_{k}}\alpha _{i}^{k}v^{k,i}$

gilt, wobei $\alpha ^{k}\in \mathbb {R} ^{s_{k}}$ Lösung von Problem (8.27) ist.

Wie bereits gesagt wurde, wählt man $V_{k}$ typischerweise so, dass $s_{k}\leq 3$ und damit (8.27) ein Problem in maximal 3 Variablen ist. Eine einfache Wahl von $V_{k}$ ist die Wahl

(8.29) $V_{k}:=\operatorname {span} \left\{d_{G}^{k}\right\},$

wobei $d_{G}^{k}:=-g^{k}\neq 0$ die Richtung steilsten Abstiegs für $f$ in $x^{k}$ bezeichnet. In diesem Fall nennt man die zugehörige Lösung $d_{C}^{k}:=d^{k}$ von $(TT)_{k}$ auch Cauchy-Punkt. Diesen Punkt kann man explizit angeben (Beweis: Übung!):

(8.30) $d_{C}^{k}:=d^{k}=-\tau _{k}{\frac {\Delta _{k}}{\left\|g^{k}\right\|}}g^{k}$

mit

(8.31) $\tau _{k}:={\begin{cases}1,&{\text{falls }}(g^{k})^{T}\nabla ^{2}f(x^{k})g^{k}\leq 0,\\\min \left\{{\frac {\left\|g^{k}\right\|^{3}}{\Delta _{k}(g^{k})^{T}\nabla ^{2}f(x^{k})g^{k}}},1\right\},&{\text{falls }}(g^{k})^{T}\nabla ^{2}f(x^{k})g^{k}>0.\end{cases}}$

Die Richtung (8.30) ist die mit einer speziellen „Schrittweite“ versehene Richtung steilsten Abstiegs für $f$ in $x^{k}$, 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 $f$ 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 $V_{k}$ in Algorithmus 8.12 zumeist nicht wie in (8.29), sondern als

(8.32) $V_{k}:=\operatorname {span} \left\{d_{G}^{k},d_{N}^{k}\right\},$

wobei

$d_{G}^{k}:=-g^{k},\quad d_{N}^{k}:=-\left[\nabla ^{2}f(x^{k})\right]^{-1}g^{k}$

die Gradienten- und die Newton-Richtung für $f$ in $x^{k}$ sind und vorausgesetzt wird, dass die Matrix $\nabla ^{2}f(x^{k})$ für alle $k$ invertierbar ist. Letzteres ist ja unter der Voraussetzung (V5) gewährleistet. Sind $d_{G}^{k}$ und $d_{N}^{k}$ linear unabhängig, so ist in diesem Fall $s_{k}=\dim(V_{k})=2$.

Gelegentlich setzt man auch

(8.33) $V_{k}:=\operatorname {span} \left\{d_{G}^{k},d_{N}^{k},d_{\min }^{k}\right\},$

wobei $d_{\min }^{k}$ ein Eigenvektor oder eine geeignete Näherung für einen Eigenvektor zum kleinsten Eigenwert $\lambda _{\min ,k}$ der Matrix $\nabla ^{2}f(x^{k})$ ist. (Den Eigenwert und Eigenvektor muss man allerdings erstmal berechnen). Die Hinzunahme von $d_{\min }^{k}$ in die Basis von $V_{k}$ ist dadurch begründet, dass für eine hinreichend kleine Norm $\left\|d_{\min }^{k}\right\|$, d. h. bei einer geeigneten Skalierung des gefundenen Eigenvektors zu $\lambda _{\min ,k}$ gilt:

$f(x^{k}+d_{\min }^{k})\approx f(x^{k})+\nabla f(x^{k})^{T}d_{\min }^{k}+{\frac {1}{2}}(d_{\min }^{k})^{T}\nabla ^{2}f(x^{k})d_{\min }^{k}$

(8.34) $=f(x^{k})+\nabla f(x^{k})^{T}d_{\min }^{k}+{\frac {1}{2}}\lambda _{\min ,k}\left\|d_{\min }^{k}\right\|^{2}$

Im Fall

$\lambda _{\min ,k}<0,\quad \nabla f(x^{k})^{T}d_{\min }^{k}\leq 0,$

wobei man die zweite Ungleichung gegebenenfalls durch Übergang zu $-d_{\min }^{k}$ erreichen kann, kann man also den Funktionswert von $f$ bei $x^{k}$ in Richtung $d_{\min }^{k}$ „stark“ verringern und ist für den kleinsten Eigenwert unter allen negativen Eigenwerten die größtmögliche Verringerung zu erwarten. Insbesondere ist $d_{\min }^{k}$ im Fall $\nabla f(x^{k})^{T}d_{\min }^{k}<0$ eine Abstiegsrichtung für $f$ in $x^{k}$ und wird die „geeignete Skalierung“ von $d_{\min }^{k}$ im Verfahren durch die Wahl des Trust-Region-Radius $\Delta _{k}$ erzielt.

Ein Sattelpunkt $x^{*}$ von $f$ ist ja ein kritischer Punkt von $f$, 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 $f$ vorausgesetzt - die Eigenwerte von $\nabla ^{2}f(x^{*})$ (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 $x^{*}$ um einen lokalen Minimalpunkt handelt. Gibt es jedoch unter den Eigenwerten mindestens einen negativen, so ist $x^{*}$ 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 $f$ reduzieren kann (ersetze $x^{k}$ durch $x^{*}$ in der obigen Argumentation).

Da für den Cauchy-Punkt in (8.30) $\left\|d_{C}^{k}\right\|\leq \Delta _{k}$ gilt und somit bei einer Wahl von $V_{k}$ wie in (8.32) oder (8.33) für eine Lösung $d^{k}$ von Problem $(TT)_{k}$ die Abschätzung

$q_{k}(d^{k})\leq q_{k}(d_{C}^{k})$

gültig ist, ist anzunehmen, dass man in diesen Fällen einen größeren Abstieg bezüglich des aktuellen Funktionswertes von $f$ als für die Wahl $V_{k}:=\operatorname {span} \left\{d_{G}^{k}\right\}$ erreichen kann. Man beachte aber, dass man noch die Vektoren $d_{G}^{k},d_{N}^{k}$ und gegebenenfalls $d_{\min }^{k}$ 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 $V_{k}$ die Gradientenrichtung $d_{G}^{k}$ bzw. sowohl die Gradientenrichtung $d_{G}^{k}$ als auch die Newton-Richtung $d_{N}^{k}$ enthält. So hat man in Analogie zu Lemma 8.6 zunächst das folgende Ergebnis.

Lemma 8.14

Sei $d_{G}^{k}\in V_{k}$. Dann gilt für jede Lösung $d^{k}\in V_{k}$ von Problem $(TT)_{k}$

$f(x^{k})-q_{k}(d^{k})\geq {\frac {1}{2}}\left\|g^{k}\right\|\min \left\{\Delta _{k},{\frac {\left\|g^{k}\right\|}{\left\|B_{k}\right\|}}\right\},$

wobei $\left\|g^{k}\right\|/\left\|B_{k}\right\|=+\infty$ für $B_{k}=0$ gesetzt werde.

Beweis.

Da anderenfalls Algorithmus 8.12 in Schritt (1) abbrechen würde, ist $g^{k}\neq 0$. Ferner sind wegen $d_{G}^{k}\in V_{k}$ auch alle Vielfachen von $g^{k}$ Elemente von $V_{k}$. Da die beiden im Beweis von Lemma 8.6 verwendeten Vergleichsvektoren $d$ Vielfache von $g^{k}$ sind, lässt sich der Beweis jenes Lemmas unmittelbar auf die Situation von Problem $(TT)_{k}$ übertragen.

q.e.d.

Lemma 8.14 garantiert die Durchführbarkeit von Algorithmus 8.12, da der Nenner in $r_{k}$ nur im Fall $g^{k}=0$ identisch Null sein kann und dieser Fall durch die Abfrage in Schritt (1) von Algorithmus 8.12 ausgeschlossen ist. Wir erhalten weiter:

Satz 8.15

Sei $f\in C^{2}(\mathbb {R} ^{n})$ und $d_{G}^{k}\in V_{k}$ für alle $k$. Weiter sei (V2) erfüllt. Bricht Algorithmus 8.12 nicht ab, dann besitzt die durch ihn erzeugte Folge $\left\{x^{k}\right\}$ einen Häufungspunkt und jeder solche Häufungspunkt ist ein kritischer Punkt von $f$.

Beweis.

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.

Satz 8.16

Es sei (V5) erfüllt und $x^{*}$ sei die dann existierende eindeutige Lösung von $(P)$. Weiter sei $d_{G}^{k}\in V_{k}$ für alle $k$. Dann bricht Algorithmus 8.12 entweder ab oder er erzeugt eine Folge $\left\{x^{k}\right\}$, für welche gilt:

(i) $\lim _{k\to \infty }x^{k}=x^{*}.$

(ii) Es ist $r_{k}\geq \varrho _{1}$ für alle $k\geq k_{0}$ mit einem $k_{0}\in \mathbb {N}$.

(iii) Es ist $\Delta _{k}\geq {\bar {\Delta }}$ für alle $k\in \mathbb {N}$ mit einem ${\bar {\Delta }}>0$.

Der Beweis von Satz 8.11 über die Konvergenzgeschwindigkeit des Trust-Region-Newton-Verfahrens lief darauf hinaus zu zeigen, dass die Newton-Richtung $d_{N}^{k}$ für alle hinreichend großen $k$ das Teilproblem $(TN)_{k}$ löst und dass das Verfahren somit lokal in das klassische Newton-Verfahren übergeht. Wenn wir also zusätzlich zu $d_{G}^{k}\in V_{k}$ auch $d_{N}^{k}\in V_{k}$ fordern, so ist $d_{N}^{k}$ auch eine Lösung von Problem $(TT)_{k}$ für alle hinreichend großen $k$. Folglich haben wir abschließend:

Satz 8.17

Es sei (V5) erfüllt und $x^{*}$ sei die dann existierende eindeutige Lösung von $(P)$. Ferner seien $d_{G}^{k},d_{N}^{k}\in V_{k}$ für alle $k$. Dann bricht Algorithmus 8.12 entweder ab oder er erzeugt eine Folge $\left\{x^{k}\right\}$, für welche gilt:

(i) $\left\{x^{k}\right\}$ konvergiert superlinear gegen $x^{*}$.

(ii) Hat man mit einem $L>0$ und einem $\varepsilon >0$

$\left\|\nabla ^{2}f(x)-\nabla ^{2}f(x^{*})\right\|\leq L\left\|x-x^{*}\right\|,\quad x\in {\mathcal {U}}_{\varepsilon }(x^{*}),$

dann konvergiert $\left\{x^{k}\right\}$ quadratisch gegen $x^{*}$.