Die Trust-Region-Verfahren sind eine Klasse von robusten und effizienten Globalisierungsstrategien zur numerischen Berechnung eines lokalen Minimums einer möglicherweise nicht-konvexen, einmal stetig differenzierbaren Funktion. Die Trust-Region-Verfahren sind eng verwandt mit dem Levenberg-Marquardt-Algorithmus, besitzen jedoch signifikante Unterschiede in den zu lösenden quadratischen Teilproblemen und sind deterministisch in der Wahl der Schrittweitenbeschränkung. Unter bestimmten Umständen kann man zudem zeigen, dass Liniensuchverfahren spezielle Varianten von Trust-Region-Verfahren sind.

Übersicht

Bearbeiten

Trust-Region-Verfahren werden verwendet um Nichtlineare Programmierungsprobleme (NLP) der Art

 

zu lösen.

Hierbei nimmt man an, dass   einmal stetig differenzierbar auf   ist. Das bedeutet aber nicht, dass   eine konvexe Funktion ist. Da man zudem mit geringsten Änderungen am Algorithmus das folgende, nichtglatte Nichtlineare Programmierungsproblem

 

lösen kann, werden wir das Trust-Region-Verfahren für diese Problemklasse betrachten. Hierbei ist   mit  , sowie   ein Hilbertraum.

Ein Trust-Region-Verfahren ist ein iteratives Verfahren, welches aus einzelnen, sogenannten Trust-Region-Schritten besteht. Ein solcher Trust-Region-Schritt verläuft in zwei logischen Einheiten: Zunächst errechnet man eine Korrektur. Die Art und Weise, wie eine solche Korrektur errechnet wird, ist im Prinzip frei wählbar, solange die Korrektur eine sogenannte „Sufficient Decrease Condition“ erfüllt. Aus Performancegründen errechnet man jedoch oftmals die Korrektur, indem man ein quadratisches Minimierungsproblem unter Nebenbedingungen löst. Die mit dieser Sequential Quadratic Programming (SQP) Variante errechneten Korrekturen sind unter bestimmten Umständen die Korrekturen, die man in einem (Quasi-)Newtonschritt errechnet. Da diese Korrektur, im Sinne der Aufgabenstellung des Minimierungsproblems jedoch beliebig schlecht sein kann, misst man die Brauchbarkeit der Korrektur und verändert anhand dessen die Nebenbedingungen des quadratischen Problems.

Ein Trust-Region-Schritt im Detail

Bearbeiten

Errechnen der Korrektur

Bearbeiten

Wir nehmen an, dass eine zulässige Iterierte,   gegeben ist. So errechnet man eine Korrektur, indem man das folgende Quadratische Programmierungs-Problem (QP) löst:

 

mit der quadratischen Funktion

 

Hierbei bezeichnet   den Trust-Regionradius und   eine symmetrische Approximation an die möglicherweise nicht existierende Hesse-Matrix an  . Für den Fall   ist die Funktion   eine Taylorapproximation zweiter Ordnung an  .

Wir nehmen kurz an, dass die Matrix   symmetrisch positiv (semi-)definit ist und dass keine Nebenbedingungen in obigen QP Problem vorkommen. So sind die notwendigen und auch hinreichenden Bedingungen für ein Minimum gerade

 

welches ein Quasi-Newtonschritt ist.

Bemerkung zur Lösung des quadratischen Problems

Bearbeiten

Dieses Minimierungsproblem kann gemeinhin approximativ gelöst werden. Das heißt, dass die Lösung lediglich eine bessere Lösung des QP Problems sein muss als der sogenannte Cauchypunkt. Genauer gesagt heißt das, dass   folgende Ungleichung erfüllen muss

 

wobei   eine Coleman-Li-Skalierungsmatrix[1] ist, die auf der Hauptdiagonalen den Abstand zum Hindernis speichert.

Ohne weitere Annahmen muss man eine Formulierung mit Penaltyfunktion für die Lösung des quadratischen Minimierungsproblems verwenden, um   in die Lösung mit einzubeziehen. Jedoch kann für einen endlich dimensionalen Raum  ,   durch   ersetzt werden und ein abgeschnittenes Konjugierte Gradientenverfahren (truncated CG) oder ein nichtlineares Gauss-Seidelverfahren zur Lösung verwendet werden.

Wie erwähnt, kann   eine beliebig schlechte Korrektur sein, daher errechnet man zur Bestimmung der Qualität einer Korrektur ein Skalar, die sogenannte Kontraktionsrate

 

Der Wert   misst die Abweichung der durch die quadratischen Funktion   vorhergesagten Reduktion von   (predicted reduction) von der tatsächlichen (actual reduction). In der Literatur findet man daher auch oft

 

Bemerkung zu  : De facto misst die Kontraktionsrate die Linearität des Gradienten von  . Wenn   eine quadratische Funktion ist, wird die Kontraktionsrate immer 1 sein, sofern  . In der Praxis sollte man daher auch testen, ob   gilt.

Updateschritt

Bearbeiten

Schließlich wird anhand von   bestimmt, ob die Korrektur akzeptiert wird und wie der nächste Trust-Regionradius   gewählt wird.

Gilt  , so wird   und   gewählt. Andernfalls ist   und  

Hierbei sind   und   a priori zu wählen. In der Literatur werden gerne noch weitere Konstanten verwendet, um die Wahl des neuen Trust-Regionradius feiner zu justieren, jedoch kommt das Verfahren mit diesen Konstanten aus.

Konvergenzeigenschaften

Bearbeiten

Man kann unter bestimmten, aber sehr schwachen Annahmen[1][2] zeigen, dass die so errechneten Iterierten gegen Lösungen der notwendigen Bedingungen erster Ordnung konvergieren.

Grundsätzlich geht man hierbei wie folgt vor:

  • die Lösung des QP Problems erfüllt immer die sufficient decrease condition (wenn nicht wählt man den Cauchy Punkt). Das heißt: Sind Korrekturen erfolgreich, also gilt  , dann erhält man folgende Ungleichung
 

Man kann also den tatsächlichen Abstieg in   durch die Norm des Gradienten und den Trust-Regionradius nach unten hin begrenzen.

  • Nimmt man nun an, dass die Norm des Gradienten durch   nach unten beschränkt ist, so erhält man Folgendes: Angenommen es gibt unendlich viele erfolgreiche Schritte, dann konvergiert   nach   oder   und man löst das Problem (zumindest dessen notwendigen Bedingungen erster Ordnung). Andernfalls muss aufgrund der obigen Ungleichung der Trust-Regionradius gegen 0 konvergieren. In dem Fall würde aber die quadratische Funktion eine immer bessere Approximation an   und die Decrease ratio   würde gegen 1 gehen. Das würde aber der Annahme, dass es nicht unendlich viele erfolgreiche Schritte gibt widersprechen.

Unterschiede zu anderen Verfahren

Bearbeiten
  • Die Levenberg-Marquardt-Methode führt ein nichtdeterministisches Update der Schrittweitenbeschränkung durch.
  • Das Trust-Region-Verfahren ist Newton-ähnlich, d. h. die Korrekturen werden anhand einer Taylorentwicklung zweiter Ordnung errechnet, bei der Levenberg-Marquardt-Methode wird ein quadratisches Hilfsproblem gelöst, basierend auf einer Taylorentwicklung erster Ordnung.
  • Im Gegensatz zu Liniensuchverfahren wird im Trust-Region-Verfahren vor dem Errechnen einer Korrektur die Schrittweitenbeschränkung gewählt. Aufgrund der zusätzlichen Constraints im Minimierungsproblem zu  , wird daher eine andere und bessere Lösung errechnet, als sie die gleiche Schrittweitenbeschränkung im Linesearchalgorithmus liefern würde.

Erweiterungen zu Trust-Region Verfahren

Bearbeiten
  • Um Nichtlineare Programmierungsprobleme mit noch allgemeineren Nebenbedingungen der Art
 
wobei   kann man sogenannte filter Trust-Region Verfahren verwenden.
  • Es gibt Erweiterungen von Trust-Region-Verfahren, die auch Konvergenz zu kritischen Punkten zweiter Ordnung errechnen, also Punkte   für die gilt
  und  .

Methoden basierend auf Trust-Region Verfahren

Bearbeiten

Literatur

Bearbeiten
  • Thomas F. Coleman, Yuying Li: On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds. In: Math. Programming. 67(2, Ser. A) 1994, ISSN 0025-5610, S. 189–224.
  • A. R. Conn, N. I. M. Gould, Ph. L. Toint: Trust-region methods. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

Einzelnachweise

Bearbeiten
  1. a b Thomas F. Coleman, Yuying Li: On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds.
  2. A. R. Conn, N. I. M. Gould, Ph. L. Toint: Trust-region methods.