Verwirrung über die Armijo-Herrschaft

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

optimization 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

umformen .

X_{k}

$X_k$

x_{k}

$x_k$

GoHokies

Dort steckte ich fest. Wenn

eine Matrix wird, ist der Wert auf der linken Seite (

) immer noch ein Skalar. Aber der Wert auf der rechten Seite ist nicht - stattdessen ist es eine Matrix (

ist ein Skalar und

ist eine Matrix.)

x_{k}

$x_k$

f (x_{k} + α p_{k})

$f(x_k+\alpha p_k)$

f (x_{k})

$f(x_k)$

β α \nabla f (x_{k})^{T} p_{k}

$\beta\alpha∇f(x_k)^Tp_k$

Frank Puk

Sie müssen mit einem Vektor arbeiten, nicht mit einer Matrix. Sie formen also Ihre

Matrix von Steuervariablen (ich habe sie mit

) in einen Vektor

mit

Elementen um. Die Suchrichtung und der Gradient werden auch Vektoren mit

Elementen sein. Auf diese Weise sind sowohl die rechte als auch die rechte Seite des Armijo-Zustands Skalare und können verglichen werden.

N \times N

$N \times N$

X_{k}

$X_k$

x_{k}

$x_k$

N^{2}

$N^2$

N^{2}

$N^2$

GoHokies

Antworten:

Sobald Sie eine Abstiegsrichtung für Ihre Zielfunktion , 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. $p$ $f(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 wobei ist eine Abstiegsrichtung in und . $f$

f (x_{k} + α p_{k}) \leq f (x_{k}) + β α \nabla f (x_{k})^{T} p_{k}

$f(x_k+\alpha p_k)\leq f(x_k)+\beta\alpha\nabla f(x_k)^Tp_k$

p_{k}

$p_k$

x_{k}

$x_k$

β \in (0, 1)

$\beta\in(0,1)$

Die Intuition dahinter ist, dass der Funktionswert am neuen Punkt unter der reduzierten "Tangente" bei in Richtung von . Siehe Nocedal & Wrights Buch "Numerical Optimization". In Kapitel 3 finden Sie eine hervorragende grafische Beschreibung des ausreichenden Abnahmezustands von armijo. $f(x_k+\alpha p_k)$ $x_k$ $p_k$

Paul
quelle

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.

β

$\beta$

α

$\alpha$

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

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) = x^{2}

$f(x) = x^2$

x_{k} = - 1

$x_k = -1$

p_{k} = - 2

$p_k = -2$

α

$\alpha$

f (x_{k} + α p_{k})

$f(x_k + \alpha p_k)$

α = 1 / 2

$\alpha = 1/2$

β > 1 / 2

$\beta > 1/2$

f (x_{k} + 1 / 2 p_{k}) = 0 > 1 - 2 β = f (x_{k}) + β α f^{'} (x_{k}) p_{k}

$f(x_k + 1/2 p_k) = 0 > 1 - 2 \beta = f(x_k) + \beta \alpha f'(x_k) p_k$

β

$\beta$

β > 1 / 2

$\beta > 1/2$

β = 10^{- 4}

$\beta = 10^{-4}$

β

$\beta$

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