Optimierungsproblem : Steilster Abstieg

Neue Frage »

Informatik_Student Auf diesen Beitrag antworten »
Optimierungsproblem : Steilster Abstieg
Meine Frage:
Hallo liebes Matheboard,

Ich habe ein Problem im Bereich, der im Titel angeben ist.
Zuvor: Bei uns wird die Nummer des Schrittes im Exponenten und nicht im Index angegeben. Fragt mich nicht warum.
Gegeben ist eine Funktion [latex]f(x) = x_{1}^{2} + 2x_{2}^{2} + 2x_{1}x_{2}+2x_{1}[/latex].
Diese habe ich schon umgestellt zu einer Funktion der Form:
[latex]<br />
f(x) = \frac{1}{2} \cdot x^{T} * A * x - b^{T} * x + c<br />
[/latex]
mit
[latex]<br />
A=\begin{pmatrix} 2 & 2 \\ 2 & 4 \end{pmatrix}<br />
b=\begin{pmatrix} -2 \\ 0 \end{pmatrix} <br />
[/latex]
Jetzt ist hier in der Aufgabenstellung diese Iteration angeben:
[latex]<br />
x^{k+1} = x^{k} - \alpha^{k} grad(f(x^{k})) \\<br />
\alpha ^{k} = arg min (\alpha \geq 0) f(x^{k} -\alpha * grad(f(x^{k})))<br />
[/latex]

Mein Problem heißt:
Zeigen sie dass:
[latex]<br />
\frac{df}{d\alpha } | x^{k}  = 0 <=> (-r^{k})^{T}\cdot d^{k-1} = 0 \\<br />
mit \\<br />
r^{k} = b-Ax^{k} \\<br />
x^{k} = x^{k-1} + \alpha^{k-1}d^{k-1}<br />
[/latex]

Meine Ideen:
Ich habe das Problem bei der Ableitung. f enthält kein alpha nach dem ich ableiten könnte. f enthält nur x nach dem ich ableiten könnte. Dieses x kann ich durch die Iteration ersetzen. Und das könnte ich dann auch nach alpha ableiten. Aber wie soll ich dann ein [latex]x^{k}[/latex] da drin einsetzen? und wofür genau? Für alpha geht nicht, da alpha ja in |R ist und x in |R^2 und das x ist ja durch die Ableitung kaputt gegangen.
Informatik_Student Auf diesen Beitrag antworten »
Nächste Schritte
Gehe ich denn schonmal dahingehend richtig, dass:
[latex]\frac{df}{d\alpha } = \frac{df}{dx} * \frac{dx}{d\alpha } [/latex]
korrekt ist?
Und gehe ich weiterhin richtig in der Annahme, dass
[latex]\frac{df}{dx} = Ax-b[/latex]?
 
 
Informatik_Student Auf diesen Beitrag antworten »

Ich habe mir jetzt überlegt:
[latex]<br />
g(x^{k}) = x^{k} + a^{k}*d^{k} = x^{k+1} \\<br />
\frac{df}{d\alpha } | x^{k} = 0 \\<br />
<=> (\frac{df}{dx} \cdot  \frac{dg}{d\alpha})| x^{k} = 0 \\<br />
<=> (Ax-b)^{T} | g(x) \cdot d^{k} = 0 \\<br />
<=> (Ax^{k+1}-b)^{T} \cdot d^{k} = 0 \\<br />
<=> (-r^{k+1})^{T} \cdot d^{k} = 0<br />
[/latex]
Wie zu sehen ist, passen die Schritte aber nicht. es soll ja k und k-1 in der letzten Zeile sein. Brauche DRINGEND Hilfe.
Mystic Auf diesen Beitrag antworten »
RE: Optimierungsproblem : Steilster Abstieg
Soweit ich das hier überblicke, solltest du ja

[latex]g(\alpha):=f(x -\alpha * \nabla f(x)) [/latex]

als Funktion von [latex]\alpha[/latex] minimieren, also nach Einsetzen von

[latex]\nabla f(x)=Ax -b[/latex]

und unter Berücksichtigung von

[latex]f(x) = \frac12 \cdot x^{T} A x - b^{T} x + c [/latex]

dann eigentlich

[latex]g(\alpha)= \frac12 \cdot (x-\alpha(Ax-b))^{T} A (x-\alpha(Ax-b)) - b^{T} (x-\alpha(Ax-b)) + c [/latex]

Man müsste also jetzt nur nur noch [latex]g'(\alpha)[/latex] mit der Kettenregel bilden und nullsetzen, oder bin ich da total auf dem falschen Dampfer? verwirrt
RavenOnJ Auf diesen Beitrag antworten »

Ich schreibe die Indizes in der normalen Schreibweise, musst du dann zurückübersetzen.

Mit d/dx meinst du vermutlich den Gradienten (Zeichen ). Dann wäre

[latex]\nabla  f(x_k) = Ax_k -b = -r_k[/latex]

da symmetrisch ist. Du hast nicht definiert, allerdings anhand der Defintionen ist anscheinend

[latex] d_k = -\nabla f(x_k) = r_k[/latex]

Warum derselbe Ausdruck zwei verschiedene Namen bekommt, ist mir nicht klar.

Dann zur Frage des [l]\frac{\partial f}{\partial \alpha}  [/l]. In dem Ausdruck taucht auf, der soll wohl abgeleitet werden. In der Tat ist

[l]\frac{\partial }{\partial \alpha}f(x_{k-1}-\alpha\nabla f(x_{k-1})) = -\nabla^T f(x_{k-1})\nabla f(s)\Big\lvert_{s = x_{k-1}-\alpha\nabla f(x_{k-1})}  [/l]

Wenn man von dieser Gleichung jetzt nimmt, dann erhält man



d.h.



Das muss dann nur noch Null gesetzt werden und du hast die Äquivalenz.
Informatik_Student Auf diesen Beitrag antworten »

Ja diese Definition von [latex]d_{k}[/latex] ist Korrekt.
Zu der Ableitung: Da meinte der Tutor, dass
[latex]\frac{df}{d\alpha } = \frac{df}{dx} \frac{dx}{d\alpha}[/latex]
bedeutet und verwies damit auf die Kettenregel.

Deine (RavenOnJ) letzte Zeile hat mir wahnsinnig geholfen. Ich weiß immernoch nicht warum mein Weg nicht klappte, aber das hilft mir ungemein!
RavenOnJ Auf diesen Beitrag antworten »

klär mal auf, warum und unterschieden wird.
Informatik_Student Auf diesen Beitrag antworten »

Das weiß ich ja selber nicht
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »