Trust-Region-Verfahren

Das Trust-Region-Verfahren ist eine Klasse von robusten und effizienten Globalisierungsstrategien zur Errechnung 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 Linesearch-Verfahren spezielle Varianten von Trust-Regionverfahren sind.

Übersicht

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

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

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-Regionverfahren für diese Problemklasse betrachten. Hierbei ist $\mathcal K = \{v\in H: \underline \phi \le v \le \overline \phi, \text{ fast ueberall}\}$ mit $\underline\phi, \overline \phi \in H$, sowie H ein Hilbertraum.

Ein Trust-Regionverfahren ist ein iteratives Verfahren, welches aus einzelnen, sogenannten Trust-Regionschritten besteht. Ein solcher Trust-Regionschritt 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-Regionschritt 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\le \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:H\to H'$ eine symmetrische Approximation an die möglicherweise nicht existierende Hessematrix an u^k. Für den Fall $M^k=\nabla^2 J(u^k)$ ist die Funktion ψ^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 Unlgleichung erfüllen muss

$-\psi^k(s) \ge \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^[1] ist, die auf der Diagonalen 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 ρ^k misst die Abweichung der durch die quadratischen Funktion ψ^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 ρ^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 ρ^k bestimmt, ob die Korrektur akzeptiert wird und wie der nächste Trust-Regionradius Δ^{k + 1} gewählt wird.

Gilt $\rho^k\ge \eta$, so wird u^{k + 1} = u^k + s und Δ^{k + 1} = γ₂Δ^k gewählt. Andernfalls ist u^{k + 1} = u^k und Δ^{k + 1} = γ₁Δ^k

Hierbei sind $\eta\in (0,1)$ und γ₂ > 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^[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 $\rho^k \ge \eta$, dann erhält man folgende Ungleichung

$J(u^k)-J(u^k+s)\ge -\eta\psi^k(s) \ge -\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 ε > 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 ρ^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-Regionverfahren ist newton-ähnlich, d.h. die Korrekturen werden anhand einer Taylorentwicklung zweiter Ordnung errechnet, beim Levenberg-Marquardt-Methode wird ein quadratisches Hilfsproblem gelöst, basierend auf einer Taylorentwicklung erster Ordnung.
• Im Gegensatz zu Linesearchalgorithmen wird im Trust-Regionverfahren vor dem Errechnen einer Korrektur die Schrittweitenbeschränkung gewählt. Aufgrund der zusätzlichen Constraints im Minimierungsproblem zu ψ^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) \le 0 \text{ und } g^E(u) = 0\}$ kann man sogenannte filter Trust-Region Verfahren verwenden.

• Es gibt Erweiterungen von Trust-Regionverfahren, 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 \ge 0$

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.

Einzelnachweise

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.