Verwirrung über die Armijo-Herrschaft

13

Ich habe diese Verwirrung über die Armijo-Regel, die bei der Zeilensuche verwendet wird. Ich habe die Suche nach Verfolgungslinien zurückgelesen, aber nicht verstanden, worum es bei dieser Armijo-Regel geht. Kann jemand erläutern, was die Armijo-Regel ist? Die Wikipedia scheint nicht gut zu erklären. Vielen Dank

user34790
quelle
Was ist, wenn die Variable x in der Gleichung kein Vektor, sondern eine Matrix ist? Wie soll die Armijo-Regel aktualisiert werden?
Frank Puk
Nichts verändert sich. Sie sollten einfach Ihre -Matrix in einen (Spalten-) Vektor x k umformen . Xkxk
GoHokies
Dort steckte ich fest. Wenn eine Matrix wird, ist der Wert auf der linken Seite ( f ( x k + α p k ) ) immer noch ein Skalar. Aber der Wert auf der rechten Seite ist nicht - stattdessen ist es eine Matrix ( f ( x k ) ist ein Skalar und β α f ( x k ) T p k ist eine Matrix.)xkf(xk+αpk)f(xk)βαf(xk)Tpk
Frank Puk
Sie müssen mit einem Vektor arbeiten, nicht mit einer Matrix. Sie formen also Ihre Matrix von Steuervariablen (ich habe sie mit X k bezeichnet ) in einen Vektor x k mit N 2 Elementen um. Die Suchrichtung und der Gradient werden auch Vektoren mit N 2 Elementen sein. Auf diese Weise sind sowohl die rechte als auch die rechte Seite des Armijo-Zustands Skalare und können verglichen werden. N×NXkxkN2N2
GoHokies

Antworten:

19

Sobald Sie eine Abstiegsrichtung für Ihre Zielfunktion f ( x ) erhalten , müssen Sie eine "gute" Schrittlänge wählen. Sie möchten keinen zu großen Schritt ausführen, sodass die Funktion an Ihrem neuen Punkt größer ist als der aktuelle Punkt. Gleichzeitig möchten Sie Ihren Schritt nicht so klein machen, dass die Konvergenz ewig dauert.pf(x)

Armijos Zustand legt im Grunde nahe, dass eine "gute" Schrittlänge so ist, dass Sie an Ihrem neuen Punkt eine "ausreichende Abnahme" von haben. Die Bedingung wird mathematisch wie gesagt f ( x k + α p k ) f ( x k ) + & bgr; α weiterempfehlen f ( x k ) T p k wobei p k ist eine Abstiegsrichtung in x k und & bgr; ( 0 , 1 ) . f

f(xk+αpk)f(xk)+βαf(xk)Tpk
pkxkβ(0,1)

Die Intuition dahinter ist, dass der Funktionswert am neuen Punkt unter der reduzierten "Tangente" bei x k in Richtung von p k liegen sollte . Siehe Nocedal & Wrights Buch "Numerical Optimization". In Kapitel 3 finden Sie eine hervorragende grafische Beschreibung des ausreichenden Abnahmezustands von armijo.f(xk+αpk)xkpk

Paul
quelle
1
Anstatt es als tangentiale Linie zu betrachten, können Sie es auch als Taylor-Expansion erster Ordnung betrachten. In diesem Fall stellt das lediglich sicher, dass eine solche Schrittweite α existiert. βα
cjordan1
Der Grund, warum dies überhaupt wichtig ist, dh warum ein "guter" Schritt notwendig ist, ist, dass viele Optimierungsschemata langsamer konvergieren, wie Paul sagt, oder möglicherweise gar nicht konvergieren. Liniensuchen - die es in verschiedenen Varianten gibt, wobei Armijo die beliebteste ist - können verwendet werden, um Algorithmen robustere Konvergenzeigenschaften zu verleihen.
cjordan1
1
Paul: Ihre Erklärung ist unvollständig. Diese Ungleichheit allein garantiert nicht die "ausreichende" Abnahme. In der Tat können Sie alpha = 0 haben und trotzdem die von Ihnen geschriebene Ungleichung erfüllen. Ein wichtiges Merkmal der Armijo-Regel besteht darin, die Schrittweite von Null weg zu begrenzen, was durch eine andere Ungleichung bewirkt wird: f (gamma * x_neu) -f (x_alt)> beta * (gamma * x_neu-x_alt) ^ T * grad (f (x_old))
f(x)=x2xk=1pk=2αf(xk+αpk)α=1/2β>1/2f(xk+1/2pk)=0>12β=f(xk)+βαf(xk)pkβ
β>1/2β=104β
0

Fünf Jahre später ist diese Frage immer noch gültig.

Hier (Seiten 16 und 17) finden Sie eine großartige Erklärung, einschließlich eines Algorithmus.

Bojan Hrnkas
quelle