Trust-Region-Verfahren

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.

Inhaltsverzeichnis

Ü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 uk. Für den Fall M^k=\nabla^2 J(u^k) ist die Funktion ψk(s) eine Taylorapproximation zweiter Ordnung an J(uk + s) − J(uk).

Wir nehmen kurz an, dass die Matrix Mk 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(uk) − J(uk + 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 uk + 1 = uk + s und Δk + 1 = γ2Δk gewählt. Andernfalls ist uk + 1 = uk und Δk + 1 = γ1Δk

Hierbei sind \eta\in (0,1) und γ2 > 1 > γ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(uk) 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(uk) − J(uk + 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.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Liste numerischer Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • Globale Optimierung — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Optimierungsalgorithmus — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Optimierungstheorie — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Optimierungsverfahren — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Zielfunktion — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Optimierung (Mathematik) — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines – meist komplexen – Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme… …   Deutsch Wikipedia

  • Sexueller Missbrauch in der römisch-katholischen Kirche — ist ein Phänomen, das seit Mitte der neunziger Jahre weltweit größere öffentliche Aufmerksamkeit erhalten hat. Die Sensibilisierung für das frühere Tabuthema hat viele Opfer ermutigt, 30 oder 40 Jahre nach den Vorfällen an die Öffentlichkeit zu… …   Deutsch Wikipedia

  • Linoleum — Moderne Farbkollektion und Rückseite von Linoleum …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”