Ich führe eine Zeilensuche als Teil eines Quasi-Newton-BFGS-Algorithmus durch. In einem Schritt der Zeilensuche verwende ich eine kubische Interpolation, um näher an den lokalen Minimierer heranzukommen.
Sei die interessierende Funktion. Ich möchte ein so dass .x ≤ f ' ( x ≤ ) ≤ 0
Sei , , und bekannt. Nehmen Sie auch . Ich passe ein kubisches Polynom so dass , , und .f ' ( x k ) f ( x k + 1 ) f ' ( x k + 1 ) 0 ≤ x k < x ∗ < x k + 1 Q ( x ) = a x 3 + b x 2 + c x + d Q ( 0 ) = fQ ' ( 0 ) = f ' ( x k ) Q ( x k + 1 - x k ) = f ( x k + 1 ) Q ' ( x k + 1 - x k ) = f ' ( x k + 1 )
Ich löse die quadratische Gleichung: für mein gesuchtes Verwendung der Lösung in geschlossener Form.x ∗
Das Obige funktioniert in den meisten Fällen gut, außer wenn als Lösung für geschlossener Form durch dividiert wird, das sehr nahe an oder genau .( 1 ) a 0
Meine Lösung ist zu sehen , und wenn es für die Minimierer des quadratischen Polynom „zu klein“ einfach nehmen Sie die geschlossene Lösung ist , für die ich habe bereits die Koeffizienten aus der früheren Anpassung an .Q 2 ( x ) = b x 2 + c x + d b , c , d Q ( x )
Meine Frage ist: Wie kann ich einen guten Test entwickeln, wann die quadratische Interpolation über die kubische Interpolation erfolgen soll? Der naive Ansatz, auf zu testen, ist aus numerischen Gründen schlecht, daher schaue ich auf wobei die Maschinengenauigkeit ist, aber ich kann mich nicht für ein gutes , das skalierungsinvariant von .| a | < ϵ τ ϵ τ f
Bonusfrage: Gibt es numerische Probleme bei der Verwendung der Koeffizienten aus der fehlgeschlagenen kubischen Anpassung oder sollte ich eine neue quadratische Anpassung mit geeigneter Methode zur Berechnung der Koeffizienten durchführen?
Zur Verdeutlichung bearbeiten: In meiner Frage ist tatsächlich das, was in der Literatur allgemein als . Ich habe nur die Frageformulierung vereinfacht. Das Optimierungsproblem, das ich löse, ist in 6 Dimensionen nicht linear. Und mir ist klar, dass Wolfe-Bedingungen für die BFGS-Zeilensuche ausreichen, was besagt, dass ich an interessiert war ; Ich bin auf der Suche nach etwas, das starke Wolfe-Bedingungen erfüllt, und der Minimierer der kubischen Näherung ist ein guter Schritt auf dem Weg.ϕ ( α ) = f ( ˉ x k + α ¯ p k ) f ' ( x ∗ ) ≈ 0
Es ging nicht um BFGS, sondern darum, wie zu bestimmen ist, wann der kubische Koeffizient klein genug ist, dass eine quadratische Näherung angemessener ist.
Edit 2: Notation aktualisieren, Gleichungen bleiben unverändert.
Es gibt ein Papier von Moré, das von Nocedal umgesetzt wurde:
quelle