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

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.

8.1 Das Trust-Region-Teilproblem

Bearbeiten

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.

Satz 8.1

Bearbeiten
  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).

Korollar 8.2

Bearbeiten
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.

Korollar 8.3

Bearbeiten
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]).

Satz 8.4

Bearbeiten
Das Problem   besitzt höchstens einen lokalen Minimalpunkt, der kein globaler Minimalpunkt von   ist.

8.2 Das Trust-Region-Newton-Verfahren

Bearbeiten

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.

Lemma 8.6

Bearbeiten
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.

Lemma 8.7

Bearbeiten
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  

 
(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.

Lemma 8.9

Bearbeiten
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.

Satz 8.10

Bearbeiten
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

 

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:

Satz 8.11

Bearbeiten
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

 

für jedes   der eindeutige globale Minimalpunkt von   bezüglich des ganzen Raumes   ist.

Weiter impliziert die Eigenschaft von   in (8.26), dass

 

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:

Satz 8.13

Bearbeiten
  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

 

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.

Lemma 8.14

Bearbeiten
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:

Satz 8.15

Bearbeiten
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.

Satz 8.16

Bearbeiten
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:

Satz 8.17

Bearbeiten
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  .