Berechnen Sie einen Iterationsschritt der Gradient Descent Methode (Verfahren des steilsten Abstiegs) mit dem …

Question

Aufgabe:

Text erkannt:

Betrachten Sie das Minimierungsproblem
$\min _{x \in \mathbb{R}^{3}}\left(\left(x_{3}^{2}-1\right)^{2}+\left(x_{1}^{2}-x_{2}\right)^{2}+\left(2-x_{1}\right)^{2}\right)=: \min _{x \in \mathbb{R}^{3}} f(x) .$

Text erkannt:

c) Untersuchen Sie jeweils, ob es sich bei den Vektoren
$d_{1}=\left[\begin{array}{l} 1 \\ 1 \\ 0 \end{array}\right] \quad \text { und } \quad d_{2}=\left[\begin{array}{c} 3 \\ 2 \\ -1 \end{array}\right]$
um valide Abstiegsrichtungen im Punkt
$x=\left[\begin{array}{l} 1 \\ 1 \\ 2 \end{array}\right]$
handelt.
d) Berechnen Sie einen Iterationsschritt der Gradient Descent Methode (Verfahren des steilsten Abstiegs) mit dem Startvektor
$x^{(0)}=\left[\begin{array}{l} 2 \\ 4 \\ 2 \end{array}\right]$
und der optimalen Schrittweite $\alpha_{0}$, die durch klassische Liniensuche bestimmt wird.

c) Untersuchen sie jeweils ob es sich bei den Vektoren d₁ =[1, 1, 0]^T  d₂ =[3, 2, -1]^T

^{um valide abstiegsrichtugnen im punkt x= [1, 1, 2]}

d) Berechnen sie einen iterationsschritt des verfahren des steilsten Abstiegs mit x⁽⁰⁾ = [2, 4, 2]^T

und der optimalen schrittweite α₀ durch klassiche liniensuche.

Problem/Ansatz:
Ich weiß nicht wie ich die c und d machen soll.

Answer 1

Beim Gradientenabstiegsverfahren handelt es sich um ein Verfahren, dass in Richtung des steilsten Abstiegs einer Raumkurve ein Minimum sucht. Wenn $f(x) \in \mathbb{R}$ mit $x \in \mathbb{R}^3$ die Funktion ist, die minimiert werden soll, dann sieht das rekursive Verfahren zum finden des Minimums so aus

$$(1) \quad x^{(k+1)} = x^{(k)} - \alpha_k \nabla f \left( x^{(k)} \right)$$

mit einer in jedem Iterationsschritt noch zu bestimmenden Schrittweit $\alpha_k$.

In Deinem Fall soll $\alpha_k$ wie folgt bestimmt

Sei $$(2) \quad \Phi(\alpha_k) = f \left[ x - \alpha_k \nabla f \left( x^{(k)} \right) \right]$$ dann sucht man das kleinste $\alpha_k$ das die Funktion $\Phi(\alpha_k)$ minimiert.

Das bedeutet, man sucht das Minimum der Nullstellen von $\phi'(\alpha_k)$ für die $\phi''(\alpha_k) > 0$ gilt.

Soweit das Allgemeine.

Nun zu den Aufgaben. Zuerst

Fall c

Zuerst muss man den Gradienten an der Stelle $x=\left[\begin{array}{l} 1 \\ 1 \\ 2 \end{array}\right]$ finden und überprüfen ob der Gradient ein Vielfaches der Richtungsvektoren $d_i$ mit $i= 1,2$ ist.

Zu d

Hier muss aus (2) $\alpha_0$ bestimmt werden und dann aus (1)  $x^{(1) }$

Comments

vielen dank. genau was ich brauchte.

möge Gott über dich wachen mein freund.

---

Vielleicht noch ein Hinweis:

Die Lösung des Minimierungsproblem ist ja klar. Weil alle Summanden größer gleich Null sind, wird das Minimum genau da angenommen, wo jeder Summand für sich schon Null wird.

D.h. die Lösung ist $$\begin{pmatrix} 2 \\ 4 \\ \pm1 \end{pmatrix}$$

Jetzt kann man sich fragen ob es ein $\alpha$ gibt mit

$$x^{(1)} = \begin{pmatrix} 2 \\ 4 \\ 2 \end{pmatrix} - \alpha \cdot \nabla f\left( x^{(0)} \right) = \begin{pmatrix} 2 \\ 4 \\ \pm1 \end{pmatrix}$$

Da $$\nabla f\left( x^{(0)} \right) = \begin{pmatrix} 0 \\ 0 \\ 24 \end{pmatrix}$$ gilt, folgt $$\alpha = \frac{1}{24}$$ oder $$\alpha = \frac{1}{8}$$ sind mögliche Kandidaten für die Schrittweite.

Das sind auch genau die Werte, die bei der formalen Durchführung des Algortihmus herauskommen. Der zusätzliche Wert $\alpha = \frac{1}{12}$ der aus dem Algortithmus folgt, entspricht nicht einem Minimum der Funktion $\Phi(\alpha)$

D.h. für dieses Beispiel hat man in der Tat das Minimum mit einem Schritt gefunden. Denn es folgt für beide zulässigen Werte von $\alpha$ immer, $f(x^{(1)}) = 0$