Trust-Region-Verfahren

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

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

$u\in H:J(u)=\min !$

zu lösen.

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

$u\in {\mathcal {K}}\subset H:J(u)=\min !$

lösen kann, werden wir das Trust-Region-Verfahren für diese Problemklasse betrachten. Hierbei ist ${\mathcal {K}}=\{v\in H:{\underline {\phi }}\leq v\leq {\overline {\phi }},{\text{ fast ueberall}}\}$ mit ${\underline {\phi }},{\overline {\phi }}\in H$, sowie $H$ 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

Errechnen der Korrektur

Wir nehmen an, dass eine zulässige Iterierte, $u^{k}\in {\mathcal {K}}$ gegeben ist. So errechnet man eine Korrektur, indem man das folgende Quadratische Programmierungs-Problem (QP) löst:

$s\in H:\psi ^{k}(s)=\min !\{{\tilde {s}}\in H:{\tilde {s}}+u^{k}\in {\mathcal {K}},\|s\|_{H}\leq \Delta ^{k}\}$

mit der quadratischen Funktion

$\psi ^{k}(s)=\langle \nabla J(u^{k}),s\rangle +{\frac {1}{2}}\langle M^{k}s,s\rangle$

Hierbei bezeichnet $\Delta ^{k}\in \mathbb {R} ^{+}$ den Trust-Regionradius und $M^{k}\colon H\to H'$ eine symmetrische Approximation an die möglicherweise nicht existierende Hesse-Matrix an $u^{k}$. Für den Fall $M^{k}=\nabla ^{2}J(u^{k})$ ist die Funktion $\psi ^{k}(s)$ eine Taylorapproximation zweiter Ordnung an $J(u^{k}+s)-J(u^{k})$.

Wir nehmen kurz an, dass die Matrix $M^{k}$ 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

$s\in H:M^{k}s=-\nabla J(u^{k})$

welches ein Quasi-Newtonschritt ist.

Bemerkung zur Lösung des quadratischen Problems

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 $s$ folgende Ungleichung erfüllen muss

$-\psi ^{k}(s)\geq \beta \|D(u^{k})\nabla J(u^{k})\|\min\{\|D(u^{k})\nabla J(u^{k}),\Delta ^{k}\}$

wobei $D(u)$ eine Coleman-Li-Skalierungsmatrix 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 $\|s\|_{H}$ in die Lösung mit einzubeziehen. Jedoch kann für einen endlich dimensionalen Raum $H$, $\|s\|_{H}$ durch $\|s\|_{\infty }$ ersetzt werden und ein abgeschnittenes Konjugierte Gradientenverfahren (truncated CG) oder ein nichtlineares Gauss-Seidelverfahren zur Lösung verwendet werden.

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

$\rho ^{k}={\frac {J(u^{k})-J(u^{k}+s)}{-\psi ^{k}(s)}}$

Der Wert $\rho ^{k}$ misst die Abweichung der durch die quadratischen Funktion $\psi ^{k}(s)$ vorhergesagten Reduktion von $J$ (predicted reduction) von der tatsächlichen (actual reduction). In der Literatur findet man daher auch oft

$\rho ^{k}={\frac {{\text{ared}}_{k}(s)}{{\text{pred}}_{k}(s)}}$

Bemerkung zu $\rho ^{k}$: De facto misst die Kontraktionsrate die Linearität des Gradienten von $J$. Wenn $J$ eine quadratische Funktion ist, wird die Kontraktionsrate immer 1 sein, sofern $M^{k}=\nabla ^{2}J(u^{k})$. In der Praxis sollte man daher auch testen, ob $J(u^{k})-J(u^{k}+s)>0$ gilt.

Updateschritt

Schließlich wird anhand von $\rho ^{k}$ bestimmt, ob die Korrektur akzeptiert wird und wie der nächste Trust-Regionradius $\Delta ^{k+1}$ gewählt wird.

Gilt $\rho ^{k}\geq \eta$, so wird $u^{k+1}=u^{k}+s$ und $\Delta ^{k+1}=\gamma _{2}\Delta ^{k}$ gewählt. Andernfalls ist $u^{k+1}=u^{k}$ und $\Delta ^{k+1}=\gamma _{1}\Delta ^{k}$

Hierbei sind $\eta \in (0,1)$ und $\gamma _{2}>1>\gamma _{1}>0$ 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

Man kann unter bestimmten, aber sehr schwachen Annahmen 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 $\rho ^{k}\geq \eta$, dann erhält man folgende Ungleichung

$J(u^{k})-J(u^{k}+s)\geq -\eta \psi ^{k}(s)\geq -\eta \beta \|D(u^{k})\nabla J(u^{k})\|\min\{\|D(u^{k})\nabla J(u^{k})\|,\Delta ^{k}\}$

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

• Nimmt man nun an, dass die Norm des Gradienten durch $\varepsilon >0$ nach unten beschränkt ist, so erhält man Folgendes: Angenommen es gibt unendlich viele erfolgreiche Schritte, dann konvergiert $J(u^{k})$ nach $-\infty$ oder $\|D(u^{k})\nabla J(u^{k})\|\to 0$ 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 $J(u^{k})-J(u^{k}+s)$ und die Decrease ratio $\rho ^{k}$ würde gegen 1 gehen. Das würde aber der Annahme, dass es nicht unendlich viele erfolgreiche Schritte gibt widersprechen.

Unterschiede zu anderen Verfahren

• 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 $\psi ^{k}(s)$, 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

• Um Nichtlineare Programmierungsprobleme mit noch allgemeineren Nebenbedingungen der Art

$u\in {\mathcal {K}}\subset H:J(u)=\min !$

wobei ${\mathcal {K}}=\{u\in H:g^{I}(u)\leq 0{\text{ und }}g^{E}(u)=0\}$ 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 $u^{*}$ für die gilt

$\|D(u^{*})\nabla J(u^{*})\|=0$ und $\forall s\in H:u^{*}+s\in {\mathcal {K}}\Rightarrow \langle s,\nabla ^{2}J(u^{*})s\rangle \geq 0$.

Methoden basierend auf Trust-Region Verfahren

• PDFO (Michael J. D. Powell)
• LANCELOT (Andrew Conn, Nick Gould, und Philippe Toint)

Literatur

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