www.wikidata.de-de.nina.az

Trust Region Verfahren Die sind eine Klasse von robusten und effizienten Globalisierungsstrategien zur numerischen Berec

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 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 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 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
  • Es gibt Erweiterungen von Trust-Region-Verfahren, die auch Konvergenz zu kritischen Punkten zweiter Ordnung errechnen, also Punkte für die gilt

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. ↑ 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Trust Region Verfahren sind eine Klasse von robusten und effizienten Globalisierungsstrategien zur numerischen Berechnung eines lokalen Minimums einer moglicherweise 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 losenden quadratischen Teilproblemen und sind deterministisch in der Wahl der Schrittweitenbeschrankung Unter bestimmten Umstanden kann man zudem zeigen dass Liniensuchverfahren spezielle Varianten von Trust Region Verfahren sind Inhaltsverzeichnis 1 Ubersicht 2 Ein Trust Region Schritt im Detail 2 1 Errechnen der Korrektur 2 2 Bemerkung zur Losung des quadratischen Problems 2 3 Updateschritt 3 Konvergenzeigenschaften 4 Unterschiede zu anderen Verfahren 5 Erweiterungen zu Trust Region Verfahren 6 Methoden basierend auf Trust Region Verfahren 7 Literatur 8 EinzelnachweiseUbersicht BearbeitenTrust Region Verfahren werden verwendet um Nichtlineare Programmierungsprobleme NLP der Art u H J u min displaystyle u in H J u min nbsp zu losen Hierbei nimmt man an dass J displaystyle J nbsp einmal stetig differenzierbar auf K displaystyle mathcal K nbsp ist Das bedeutet aber nicht dass J displaystyle J nbsp eine konvexe Funktion ist Da man zudem mit geringsten Anderungen am Algorithmus das folgende nichtglatte Nichtlineare Programmierungsproblem u K H J u min displaystyle u in mathcal K subset H J u min nbsp losen kann werden wir das Trust Region Verfahren fur diese Problemklasse betrachten Hierbei ist K v H ϕ v ϕ fast ueberall displaystyle mathcal K v in H underline phi leq v leq overline phi text fast ueberall nbsp mit ϕ ϕ H displaystyle underline phi overline phi in H nbsp sowie H displaystyle H nbsp ein Hilbertraum Ein Trust Region Verfahren ist ein iteratives Verfahren welches aus einzelnen sogenannten Trust Region Schritten besteht Ein solcher Trust Region Schritt verlauft in zwei logischen Einheiten Zunachst errechnet man eine Korrektur Die Art und Weise wie eine solche Korrektur errechnet wird ist im Prinzip frei wahlbar solange die Korrektur eine sogenannte Sufficient Decrease Condition erfullt Aus Performancegrunden errechnet man jedoch oftmals die Korrektur indem man ein quadratisches Minimierungsproblem unter Nebenbedingungen lost Die mit dieser Sequential Quadratic Programming SQP Variante errechneten Korrekturen sind unter bestimmten Umstanden 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 verandert anhand dessen die Nebenbedingungen des quadratischen Problems Ein Trust Region Schritt im Detail BearbeitenErrechnen der Korrektur Bearbeiten Wir nehmen an dass eine zulassige Iterierte u k K displaystyle u k in mathcal K nbsp gegeben ist So errechnet man eine Korrektur indem man das folgende Quadratische Programmierungs Problem QP lost s H ps k s min s H s u k K s H D k displaystyle s in H psi k s min tilde s in H tilde s u k in mathcal K s H leq Delta k nbsp mit der quadratischen Funktion ps k s J u k s 1 2 M k s s displaystyle psi k s langle nabla J u k s rangle frac 1 2 langle M k s s rangle nbsp Hierbei bezeichnet D k R displaystyle Delta k in mathbb R nbsp den Trust Regionradius und M k H H displaystyle M k colon H to H nbsp eine symmetrische Approximation an die moglicherweise nicht existierende Hesse Matrix an u k displaystyle u k nbsp Fur den Fall M k 2 J u k displaystyle M k nabla 2 J u k nbsp ist die Funktion ps k s displaystyle psi k s nbsp eine Taylorapproximation zweiter Ordnung an J u k s J u k displaystyle J u k s J u k nbsp Wir nehmen kurz an dass die Matrix M k displaystyle M k nbsp symmetrisch positiv semi definit ist und dass keine Nebenbedingungen in obigen QP Problem vorkommen So sind die notwendigen und auch hinreichenden Bedingungen fur ein Minimum gerade s H M k s J u k displaystyle s in H M k s nabla J u k nbsp welches ein Quasi Newtonschritt ist Bemerkung zur Losung des quadratischen Problems Bearbeiten Dieses Minimierungsproblem kann gemeinhin approximativ gelost werden Das heisst dass die Losung lediglich eine bessere Losung des QP Problems sein muss als der sogenannte Cauchypunkt Genauer gesagt heisst das dass s displaystyle s nbsp folgende Ungleichung erfullen muss ps k s b D u k J u k min D u k J u k D k displaystyle psi k s geq beta D u k nabla J u k min D u k nabla J u k Delta k nbsp wobei D u displaystyle D u nbsp eine Coleman Li Skalierungsmatrix 1 ist die auf der Hauptdiagonalen den Abstand zum Hindernis speichert Ohne weitere Annahmen muss man eine Formulierung mit Penaltyfunktion fur die Losung des quadratischen Minimierungsproblems verwenden um s H displaystyle s H nbsp in die Losung mit einzubeziehen Jedoch kann fur einen endlich dimensionalen Raum H displaystyle H nbsp s H displaystyle s H nbsp durch s displaystyle s infty nbsp ersetzt werden und ein abgeschnittenes Konjugierte Gradientenverfahren truncated CG oder ein nichtlineares Gauss Seidelverfahren zur Losung verwendet werden Wie erwahnt kann s displaystyle s nbsp eine beliebig schlechte Korrektur sein daher errechnet man zur Bestimmung der Qualitat einer Korrektur ein Skalar die sogenannte Kontraktionsrate r k J u k J u k s ps k s displaystyle rho k frac J u k J u k s psi k s nbsp Der Wert r k displaystyle rho k nbsp misst die Abweichung der durch die quadratischen Funktion ps k s displaystyle psi k s nbsp vorhergesagten Reduktion von J displaystyle J nbsp predicted reduction von der tatsachlichen actual reduction In der Literatur findet man daher auch oft r k ared k s pred k s displaystyle rho k frac text ared k s text pred k s nbsp Bemerkung zu r k displaystyle rho k nbsp De facto misst die Kontraktionsrate die Linearitat des Gradienten von J displaystyle J nbsp Wenn J displaystyle J nbsp eine quadratische Funktion ist wird die Kontraktionsrate immer 1 sein sofern M k 2 J u k displaystyle M k nabla 2 J u k nbsp In der Praxis sollte man daher auch testen ob J u k J u k s gt 0 displaystyle J u k J u k s gt 0 nbsp gilt Updateschritt Bearbeiten Schliesslich wird anhand von r k displaystyle rho k nbsp bestimmt ob die Korrektur akzeptiert wird und wie der nachste Trust Regionradius D k 1 displaystyle Delta k 1 nbsp gewahlt wird Gilt r k h displaystyle rho k geq eta nbsp so wird u k 1 u k s displaystyle u k 1 u k s nbsp und D k 1 g 2 D k displaystyle Delta k 1 gamma 2 Delta k nbsp gewahlt Andernfalls ist u k 1 u k displaystyle u k 1 u k nbsp und D k 1 g 1 D k displaystyle Delta k 1 gamma 1 Delta k nbsp Hierbei sind h 0 1 displaystyle eta in 0 1 nbsp und g 2 gt 1 gt g 1 gt 0 displaystyle gamma 2 gt 1 gt gamma 1 gt 0 nbsp a priori zu wahlen 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 BearbeitenMan kann unter bestimmten aber sehr schwachen Annahmen 1 2 zeigen dass die so errechneten Iterierten gegen Losungen der notwendigen Bedingungen erster Ordnung konvergieren Grundsatzlich geht man hierbei wie folgt vor die Losung des QP Problems erfullt immer die sufficient decrease condition wenn nicht wahlt man den Cauchy Punkt Das heisst Sind Korrekturen erfolgreich also gilt r k h displaystyle rho k geq eta nbsp dann erhalt man folgende UngleichungJ u k J u k s h ps k s h b D u k J u k min D u k J u k D k displaystyle 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 nbsp Man kann also den tatsachlichen Abstieg in J displaystyle J nbsp durch die Norm des Gradienten und den Trust Regionradius nach unten hin begrenzen Nimmt man nun an dass die Norm des Gradienten durch e gt 0 displaystyle varepsilon gt 0 nbsp nach unten beschrankt ist so erhalt man Folgendes Angenommen es gibt unendlich viele erfolgreiche Schritte dann konvergiert J u k displaystyle J u k nbsp nach displaystyle infty nbsp oder D u k J u k 0 displaystyle D u k nabla J u k to 0 nbsp und man lost das Problem zumindest dessen notwendigen Bedingungen erster Ordnung Andernfalls muss aufgrund der obigen Ungleichung der Trust Regionradius gegen 0 konvergieren In dem Fall wurde aber die quadratische Funktion eine immer bessere Approximation an J u k J u k s displaystyle J u k J u k s nbsp und die Decrease ratio r k displaystyle rho k nbsp wurde gegen 1 gehen Das wurde aber der Annahme dass es nicht unendlich viele erfolgreiche Schritte gibt widersprechen Unterschiede zu anderen Verfahren BearbeitenDie Levenberg Marquardt Methode fuhrt ein nichtdeterministisches Update der Schrittweitenbeschrankung durch Das Trust Region Verfahren ist Newton ahnlich d h die Korrekturen werden anhand einer Taylorentwicklung zweiter Ordnung errechnet bei der Levenberg Marquardt Methode wird ein quadratisches Hilfsproblem gelost basierend auf einer Taylorentwicklung erster Ordnung Im Gegensatz zu Liniensuchverfahren wird im Trust Region Verfahren vor dem Errechnen einer Korrektur die Schrittweitenbeschrankung gewahlt Aufgrund der zusatzlichen Constraints im Minimierungsproblem zu ps k s displaystyle psi k s nbsp wird daher eine andere und bessere Losung errechnet als sie die gleiche Schrittweitenbeschrankung im Linesearchalgorithmus liefern wurde Erweiterungen zu Trust Region Verfahren BearbeitenUm Nichtlineare Programmierungsprobleme mit noch allgemeineren Nebenbedingungen der Artu K H J u min displaystyle u in mathcal K subset H J u min nbsp wobei K u H g I u 0 und g E u 0 displaystyle mathcal K u in H g I u leq 0 text und g E u 0 nbsp 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 displaystyle u nbsp fur die gilt D u J u 0 displaystyle D u nabla J u 0 nbsp und s H u s K s 2 J u s 0 displaystyle forall s in H u s in mathcal K Rightarrow langle s nabla 2 J u s rangle geq 0 nbsp Methoden basierend auf Trust Region Verfahren BearbeitenPDFO Michael J D Powell LANCELOT Andrew Conn Nick Gould und Philippe Toint Literatur BearbeitenThomas 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 a b Thomas F Coleman Yuying Li On the convergence of interior reflective Newton methods for nonlinear minimization subject to bounds A R Conn N I M Gould Ph L Toint Trust region methods Abgerufen von https de wikipedia org w index php title Trust Region Verfahren amp oldid 237496230