Empfindlichkeit von BFGS gegenüber anfänglichen hessischen Näherungen

Ich versuche, die Broyden-Fletcher-Goldfarb-Shanno-Methode zu implementieren, um das Minimum einer Funktion zu finden. Ich brauche zwei anfängliche Vermutungen & und eine anfängliche hessische Matrixnäherung . Die einzigen Anforderungen, die ich für finde, sind, dass wenn der Hessische symmetrisch positiv definit ist, auch . Wenn ich auf Wikipedia schaue, sehe ich, dass eine typische anfängliche Annäherung (die Identitätsmatrix) ist. Ist das immer eine gute Initiale ? Gibt es einen Grund, warum ich etwas anderes als wählen möchte ? Würden andere Entscheidungen von B, die dieselben Matrixeigenschaften erfüllen, die Konvergenz der Methode stark beeinflussen? $x_{-1}$ $x_0$ $B_0$ $B_0$ $B_0$ $B_0=I$ $B_0$ $I$

optimization algorithms Paul
quelle

Wenn Sie eine berechtigte hessische Annäherung haben, ist es besser , es zu verwenden , anstatt die willkürliche . $B_0=I$

Bearbeiten: Das Grundprinzip ist, dass, wenn Sie in der Nähe der Lösung , die anfängliche Konvergenzrate (für jedes ) Schritt linear mit einem Schritt-Konvergenzfaktor vonwenn dies für eine Rang- Korrektur der Identitätsmatrix ist. Daher ist es sehr wertvoll, dies klein zu machen. (Dies entspricht einer Vorkonditionierung des Systems.) Der Konvergenzfaktor verbessert sich mit der Zeit und nähert sich schließlich Null (superlineare Konvergenz), aber bei vielen realen Problemen (insbesondere hochdimensionalen) werden nie genug Iterationen durchgeführt, um das superlineare Regime zu erreichen. Daher ist die Anfangsgeschwindigkeit sehr wichtig. $x^*$ $r>0$ $r+1$ $r+1$ $q=\|B_0^{-1}f''(x^*)-G\|$ $<1$ $r$ $G$

Ein wichtiger Fall ist die Lösung nichtlinearer Probleme der kleinsten Quadrate (Minimierung von ), wobei die Gauß-Newton-Näherung des anfänglichen Hessischen sein kann berechnet ohne die Notwendigkeit für zweite Ableitungen. Die Verwendung dieser Methode macht die BFGS-Methode affin invariant, dh invariant unter linearen Transformationen von wie die Newton-Methode, was normalerweise sehr vorteilhaft ist. $\|F(x)\|_2^2$ $B_0=F'(x_0)^TF'(x_0)$ $x$

Ein weiterer wichtiger Fall ist, wenn Sie eine Folge verwandter Probleme lösen. Durch einen Neustart des Lösers mit der endgültigen hessischen Näherung des vorherigen Problems wird häufig die Anzahl der erforderlichen Iterationen erheblich reduziert.

Arnold Neumaier
quelle

Wenn erwartet wird, dass der Hessische symmetrisch positiv definit ist, führt jede symmetrische positiv definierte Matrix immer noch zur Konvergenz, aber die Konvergenzrate hängt davon ab, wie stark dem Hessischen ähnelt.

B_{0}

$B_0$

B_{0}

$B_0$

Paul

Nein, schließlich vergisst BFGS die Startmatrix, sodass die Konvergenz als immer dieselbe Reihenfolge hat. Aber das ist natürlich nicht interessant, weil Sie nie unendlich viele Schritte machen.

k \to \infty

$k\rightarrow \infty$

Wolfgang Bangerth

@ Paul: Siehe meine Bearbeitung.

Arnold Neumaier

Empfindlichkeit von BFGS gegenüber anfänglichen hessischen Näherungen

Antworten: