Hilfe bei der Entscheidung zwischen kubischer und quadratischer Interpolation bei der Zeilensuche

9

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 ) 0f:RR,fC1xf(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 ) = ff(xk)f(xk)f(xk+1)f(xk+1)0xk<x<xk+1Q(x)=ax3+bx2+cx+dQ ' ( 0 ) = f ' ( x k ) Q ( x k + 1 - x k ) = f ( x k + 1 ) Q ' ( x k + 1 - x k ) = f ' ( x k + 1 )Q(0)=f(xk)Q(0)=f(xk)Q(xk+1xk)=f(xk+1)Q(xk+1xk)=f(xk+1)

Ich löse die quadratische Gleichung: für mein gesuchtes Verwendung der Lösung in geschlossener Form.x (1):Q(xxk)=0x

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 0f(x)=O(x2)(1)a0

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 )aQ2(x)=bx2+cx+db,c,dQ(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 | < ϵ τ ϵ τ fa0|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?b,c,d

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 ) 0fϕ(α)=f(x¯k+αpk¯)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.

Emily L.
quelle

Antworten:

4

Hmm ... kubische Interpolation ist für die Zeilensuche nicht ungewöhnlich, aber normalerweise übertrieben.

Wenn ich Ihr Problem richtig lese, ist nur ein Skalar? In diesem Fall ist BFGS wahrscheinlich nicht die effizienteste Methode zur Lösung Ihres Problems. Skalare Optimierungsalgorithmen wie die Brenth-Methode lösen Ihr Problem wahrscheinlich schneller.x

Es gibt eine Reihe von Zeilensuchalgorithmen für BFGS. Für meine eigenen Anwendungen mit dieser speicherbeschränkten BFGS (L-BFGS) funktioniert diese Liniensuche sehr gut. Denken Sie daran, dass Sie nur die Wolfe-Bedingungen erfüllen müssen und wahrscheinlich nicht viel gewinnen, wenn Sie den genauen Minimierer finden.

Um Ihre Frage tatsächlich zu beantworten: Ich würde in Betracht ziehen, einfach zum quadratischen Polynom zu wechseln, wenn die Lösung des kubischen Polynoms "schlechte" Werte wie NaN oder Inf ergibt (wie hier ).

Ich bin mir nicht ganz sicher, was du mit meinst . Diese Koeffizienten für die kubische Anpassung sind nicht dieselben wie für die quadratische Anpassung, sodass Sie sie nicht wiederverwenden können.b,c,d

Schließlich können Sie verwenden möchten statt , wie Ihre Funktion wird (wahrscheinlich) nur lokal etwa kubisch oder quadratisch sein, und und sollte näher beieinander (und die Lösung) als .f ( x 0 ) x k x k - 1 x 0f(xk1)f(x0)xkxk1x0

Hoffe das hilft.

LKlevin
quelle
b,c,dQ(x)=ax3+bx2+cx+da0Q(x)=bx2+cx+db,c,dDie für diese Anpassung erhaltenen Werte sind sinnvoll, um eine Interpolation durchzuführen oder wenn ich neue Koeffizienten für eine typische quadratische Anpassung neu berechnen sollte.
Emily L.
Ahh, natürlich. Ich sehe kein Problem darin, die Koeffizienten aus numerischer Sicht zu verwenden. Der einzige Punkt, an dem ich denke, dass es wichtig wäre, ist sehr nahe an der Lösung, bei der Sie sowieso kündigen würden.
LKlevin
a<<ba0
a0b,cd
4

Es gibt ein Papier von Moré, das von Nocedal umgesetzt wurde:

Jorge J. Moré und David J. Thuente. 1994. Zeilensuchalgorithmen mit garantierter ausreichender Abnahme. ACM Trans. Mathematik. Softw. 20, 3 (September 1994), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 ( Preprint ).

Juan Pablo Frias
quelle
Willkommen bei SciComp.SE! Ich habe Ihren Beitrag formatiert, um das Auffinden des Papiers zu erleichtern. Wenn Sie einen Link zur Implementierung von Nocedal finden, wäre dies hilfreich.
Christian Clason