Wolfe Bedingung für Quasi Newton Verfahren

20.04.2012, 09:35	eey	Auf diesen Beitrag antworten »
Wolfe Bedingung für Quasi Newton Verfahren Hallo zusammen, ich bin gerade dabei ein Quasi Newton Verfahren zu programmieren und bin auch schon fast fertig damit. Das einzige was mir noch fehlt ist quasi die Schrittweite meiner Hesse Matrix Approximation. Laut Wikipedia lautet die Update Formel für mein x ja: $\begin{eqnarray} x_{k+1}=x_k + \Delta x_k \end{eqnarray}$ wobei gilt: $\begin{eqnarray} \Delta x_k = -\alpha_k \cdot B_k^{-1} \nabla f(x_k) \end{eqnarray}$ Soweit so gut, mein B_k krieg ich ja mit dem BFGS Algorithmus ganz gut raus, aber wie bestimme ich mein alpha? Bei Wikipedia steht dass es die Wolfe Bedingung erfüllen muss, aber die verstehe ich leider nicht ganz... Könnte mir da jemand auf die Sprünge helfen? Schöne Grüße, eey
20.04.2012, 10:26	Cel	Auf diesen Beitrag antworten »
Hallo, eine Schrittweite $\begin{eqnarray} \alpha_k \end{eqnarray}$ erfüllt die Wolfe-Bedingung, wenn gilt: $\begin{eqnarray} \nabla f(x_k + \alpha_k s_k)^T s_k \geq \theta \nabla f(x_k)^T s_k \end{eqnarray}$ In dem Powell-Wolfe-Verfahren, der dir eine Schrittweite ausspuckt, muss auch die Armijo-Bedingung $\begin{eqnarray} f(x_k) - f(x_k + \alpha_k s_k) \geq - \gamma \alpha_k \nabla f(x_k)^T s_k \end{eqnarray}$ erfüllt sein (sichert die Zulässigkeit). Dabei gilt $\begin{eqnarray} 0 < \gamma < \theta < 1 \end{eqnarray}$ und $\begin{eqnarray} s_k \end{eqnarray}$ ist die Suchrichtung, bei dir ist das $\begin{eqnarray} -B_k^{-1} \nabla f(x_k) \end{eqnarray}$ . Die muss natürlich zulässig sein. Wie gesagt, es gibt das Powell-Wolfe-Verfahren, das dir die PW-Schrittweite ausspuckt, das ist aber ziemlich kompliziert. Vielleicht nimmst du das mal als gegeben hin. Oder was ist der Hintergrund deiner Frage? Worum geht es eigentlich?
20.04.2012, 10:37	eey	Auf diesen Beitrag antworten »
Hallo Cel, vielen Dank schonmal für die schnelle Antwort. Also es geht darum dass ich mit dem BFGS Algorithmus eine Approximation für die Hesse Matrix bestimmen will. Die brauch ich für mein Quasi Newton Verfahren, womit ich ein Gütefunktional, welches von mehreren zu variierenden Parametern abhängt, minimieren möchte. Der BFGS Algorithmus wird ja standardmäßig mit der Einheitsmatrix initialisiert (also die erste Approximation für die Hessematrix ist die Einheitsmatrix), das ist bei vielen von mir untersuchten Funktionen allerdings schon so krass daneben dass mein Verfahren divergiert. Wenn ich die Einheitsmatrix mit einem genügend kleinen Skalar (eben alpha) multipliziere, etwa 0.0001, dann konvergiert mein Verfahren, braucht aber sehr lange, da die Hessematrix nur sehr langsam angenähert wird. Daher will ich dieses alpha gerne steuern, so dass das Verfahren so schnell wie möglich konvergiert. Die Wolfe Bedingung die du gepostet hast, hab ich mir schonmal durchgelesen und wohl auch einigermaßen verstanden, aber wie kann man das umsetzen? Also wie findet man effektiv ein alpha, dass diese Bedinungen erfüllt? Einfach in einer großen Schleife alle möglichen alphas durchzutesten wäre ja sehr ineffektiv. Schöne Grüße, eey
20.04.2012, 10:48	Cel	Auf diesen Beitrag antworten »
Eine Beschreibung ist zum Beispiel hier (Algorithmus 3.16) zu finden. Wie gesagt, nicht sehr eingängig, finde ich - aber immer noch bedeutend besser als die exakte Schrittweite. Was ich noch sagen muss: Ich habe eine reine Optimierungsvorlesung besucht, Numerik kam da nicht besonders stark vor. Mehr theoretisch alles. Ich hoffe aber, ich konnte dir helfen. Wenn es noch etwas gibt, kann ja vielleicht sonst jemand was schreiben - oder ich weiß tatsächlich noch etwas.
20.04.2012, 10:55	eey	Auf diesen Beitrag antworten »
Ok, vielen Dank, das hilft mir auf jeden Fall schonmal ein bisschen weiter, werd mal versuchen das so einzubauen. Schöne Grüße, eey

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »