Trust-Region-Verfahren

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

${\displaystyle 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

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

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

Wir nehmen kurz an, dass die Matrix ${\displaystyle 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

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

welches ein Quasi-Newtonschritt ist.

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

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

wobei ${\displaystyle D(u)}$ 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 ${\displaystyle \|s\|_{H}}$ in die Lösung mit einzubeziehen. Jedoch kann für einen endlich dimensionalen Raum ${\displaystyle H}$, ${\displaystyle \|s\|_{H}}$ durch ${\displaystyle \|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 ${\displaystyle s}$ eine beliebig schlechte Korrektur sein, daher errechnet man zur Bestimmung der Qualität einer Korrektur ein Skalar, die sogenannte Kontraktionsrate

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

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

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

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

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

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

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