U 01.4 – Gradientenverfahren, optimale Schrittweitenwahl

 

Es sei

f:{\mathbb{R}^n} \to \mathbb{R},\quad f\left( {\vec x} \right) = \frac{1}{2}{\vec x^T}D\vec x

mit der Diagonalmatrix

D = \operatorname{diag} \left( {{d_1}, \ldots ,{d_n}} \right),\quad 0 < {d_1} \leq {d_2} \leq \ldots \leq {d_n}

Ausgehend von einem beliebigen Startwert 0 \ne {\vec x^0} \in {\mathbb{R}^n} wird ein Schritt des Gradientenverfahrens zur Minimierung von f ausgeführt:

{\vec x^1} = {\vec x^0}-t\nabla f\left( {{{\vec x}^0}} \right)

  1. Zeigen Sie: Mit der optimalen Schrittweitenwahl t = \hat t aus der vorhergehenden Aufgabe gilt:

    {\left\| {{{\vec x}^1}} \right\|_2} \leq \left( {1-\frac{{{d_1}}}{{{d_n}}}} \right) \cdot {\left\| {{{\vec x}^0}} \right\|_2}

    Hinweise: Definieren Sie die Funktion q\left( t \right) = \left\| {{{\vec x}^0}-t\nabla f\left( {{{\vec x}^0}} \right)} \right\|_2^2 = \left\| {{{\vec x}^0}-tD{{\vec x}^0}} \right\|_2^2.
    Gemäß Definition ist dann q\left( {\hat t} \right) = \left\| {{{\vec x}^1}} \right\|_2^2.
    Zeigen Sie nun, dass q\left( {\frac{1}{{{d_n}}}} \right) \leq {\left( {1-\frac{{{d_1}}}{{{d_n}}}} \right)^2}\left\| {{{\vec x}^0}} \right\|_2^2 gilt.
    Die Aussage folgt also, wenn man q\left( {\hat t} \right) \leq q\left( {\frac{1}{{{d_n}}}} \right) hat.
    Dies wiederum ergibt sich, wenn man Folgendes zeigen kann: q ist eine streng konvexe Funktion und \frac{1}{{{d_n}}} \leq \hat t \leq {t^*}, wobei {t^*} die globale Minimalstelle von q ist.

  2. Interpretieren Sie dieses Ergebnis: Wie gut ist die Konvergenz des Gradientenverfahrens?

Lösung

Gradientenverfahren:

Hier ist die Matrix diagonal, also A = D. Als Beispiel betrachten wir die folgende Matrix:

D = \left( {\begin{array}{*{20}{c}} 2&0 \\ 0&{50} \end{array}} \right)

Die Zielfunktion lautet damit:

f\left( {{x_1},{x_2}} \right) = \frac{1}{2}{\vec x^T}D\vec x = \frac{1}{2}\left( {\begin{array}{*{20}{c}}{{x_1}}&{{x_2}} \end{array}} \right)\left( {\begin{array}{*{20}{c}} 2&0 \\ 0&{50} \end{array}} \right)\left( {\begin{array}{*{20}{c}}{{x_1}} \\ {{x_2}} \end{array}} \right) = x_1^2+25x_2^2

Um Höhenlinien zu bestimmen, prüfen wir, wo diese Funktion konstant ist:

f\left( {{x_1},{x_2}} \right) = \operatorname{const} = {c^2}\quad \Rightarrow \quad x_1^2+25x_2^2 = {c^2}\quad \Rightarrow \quad \frac{{x_1^2}}{{{c^2}}}+\frac{{x_2^2}}{{{{\left( {\frac{c}{5}} \right)}^2}}} = 1

Dies ist eine Ellipsengleichung. Wir wählen einen Startpunkt {\vec x^0} auf einer der Höhenlinien:

u01-ellipse-mit-startpunkt

Als Suchrichtung für den nächsten Punkt benutzen wir nun den Gradienten. Zur Bestimmung der Schrittweite können unterschiedliche Algorithmen implementiert werden.

Zum einen könnte man solange dem Gradienten folgen, bis sich die Funktionswerte wieder vergrößern. Dies geschieht genau dann, wenn man eine andere Höhenlinie tangiert:

u01-ellipse-mit-gradient

Es gilt:

{\vec x^1} = {\vec x^0}-\hat t\nabla f\left( {{{\vec x}^0}} \right)

Dabei wird t so gewählt, dass \varphi \left( t \right) = f\left( {{{\vec x}^0}-t\nabla f\left( {{{\vec x}^0}} \right)} \right) minimal wird.

Dies ist aber nicht optimal, da z.B. der Punkt {\vec x^*} besser wäre, weil er näher am Minimum liegt:

u01-ellipse-mit-optimalem-punkt

a)

Es ist

f\left( {\vec x} \right) = \frac{1}{2}{\vec x^T}D\vec x,\quad D = \left( {\begin{array}{*{20}{c}}{{d_1}}&{}&0 \\ {}& \ddots &{} \\ 0&{}&{{d_n}} \end{array}} \right)

Hier gilt nun:

\vec v = \nabla f\left( {{{\vec x}^0}} \right)

Die optimale Schrittweitenwahl aus der letzten Aufgabe lautete:

t = \hat t = \frac{{\nabla f{{\left( {\vec x} \right)}^T}\vec v}}{{{{\vec v}^T}A\vec v}}\quad \Rightarrow \quad \hat t = \frac{{\nabla f{{\left( {{{\vec x}^0}} \right)}^T}\nabla f\left( {{{\vec x}^0}} \right)}}{{\nabla f{{\left( {{{\vec x}^0}} \right)}^T}D\nabla f\left( {{{\vec x}^0}} \right)}}

Im Folgenden schreiben wir \vec x statt {\vec x^0}. Wir erhalten

\hat t = \frac{{\sum\limits_{i = 1}^n {d_i^2x_i^2} }}{{\sum\limits_{i = 1}^n {d_i^3x_i^2} }}

Als Ziel soll nun gezeigt werden: {\left\| {{{\vec x}^1}} \right\|_2} \leq \left( {1-\frac{{{d_1}}}{{{d_n}}}} \right)\left\| {{{\vec x}^0}} \right\|_2

Die Behauptung \hat t \geq \frac{1}{{{d_n}}} gilt, weil \sum\limits_{i = 1}^n {d_i^3x_i^2} \leq \sum\limits_{i = 1}^n {{d_n}d_i^2x_i^2} , da 0 < {d_1} \leq {d_2} \leq \ldots \leq {d_n}

Wir definieren nun wie im Hinweis vorgegeben q\left( t \right): = \left\| {\vec x-t\nabla f\left( {\vec x} \right)} \right\|_2^2

Von dieser quadratischen Funktion wollen wir nun das Minimum bestimmen:

q\left( t \right): = \left\| {\vec x-t\nabla f\left( {\vec x} \right)} \right\|_2^2 = \left\| {\vec x} \right\|_2^2-2{\vec x^T}t\nabla f\left( {\vec x} \right)+{t^2}\left\| {\nabla f\left( x \right)} \right\|_2^2

Durch quadratisches Ergänzen und g = \nabla f\left( {\vec x} \right) erhalten wir:

q\left( t \right) = \left\| g \right\|_2^2{\left( {t-\frac{{{g^T}x}}{{\left\| g \right\|_2^2}}} \right)^2}+\left\| {\vec x} \right\|_2^2-\frac{{{{\left( {{g^T}\vec x} \right)}^2}}}{{\left\| g \right\|_2^2}}

Hier können wir nun wie bei Aufgabe 3 wieder ablesen, wo die von t abhängige Funktion minimal wird:

q\left( t \right) = \min bei t = {t^*} = \frac{{{g^T}\vec x}}{{\left\| g \right\|_2^2}}

Qualitativer Verlauf von q\left( t \right):

u01-qualitativer-verlauf-von-q

Zu zeigen ist nun noch \hat t \leq {t^*}:

\hat t \leq {t^*}\quad \Leftrightarrow \quad \frac{{\sum\limits_{i = 1}^n {d_i^2x_i^2} }}{{\sum\limits_{i = 1}^n {d_i^3x_i^2} }} \leq \frac{{\sum\limits_{i = 1}^n {{d_i}x_i^2} }}{{\sum\limits_{i = 1}^n {d_i^2x_i^2} }}\quad

\Leftrightarrow \quad {\left( {\sum\limits_{i = 1}^n {d_i^2x_i^2} } \right)^2} \leq \left( {\sum\limits_{i = 1}^n {{d_i}x_i^2} } \right)\left( {\sum\limits_{i = 1}^n {d_i^3x_i^2} } \right)

Dies können wir mit der Ungleichung von Cauchy-Schwarz zeigen:

{\left( {{a^T}b} \right)^2} \leq {\left\| a \right\|^2}{\left\| b \right\|^2}

Dazu wählen wir {a_i} = d_i^{\frac{1}{2}}{x_i} und {b_i} = d_i^{\frac{3}{2}}{x_i}. Es folgt direkt die geforderte Ungleichung:

{\left( {{{\left( {d_i^{\frac{1}{2}}{x_i}} \right)}^T}d_i^{\frac{3}{2}}{x_i}} \right)^2} \leq {\left\| {d_i^{\frac{1}{2}}{x_i}} \right\|^2}{\left\| {d_i^{\frac{3}{2}}{x_i}} \right\|^2}

\quad \Rightarrow \quad {\left( {\sum\limits_{i = 1}^n {d_i^2x_i^2} } \right)^2} \leq \left( {\sum\limits_{i = 1}^n {{d_i}x_i^2} } \right)\left( {\sum\limits_{i = 1}^n {d_i^3x_i^2} } \right)

Es folgt weiterhin:

q\left( {\frac{1}{{{d_n}}}} \right): = \left\| {\vec x-\frac{1}{{{d_n}}}\nabla f\left( {\vec x} \right)} \right\|_2^2 = \left\| {\left( {\begin{array}{*{20}{c}}{{x_1}} \\ \vdots \\ {{x_n}} \end{array}} \right)-\frac{1}{{{d_n}}}\left( {\begin{array}{*{20}{c}}{{d_1}{x_1}} \\ \vdots \\ {{d_n}{x_n}} \end{array}} \right)} \right\|_2^2

\Rightarrow \quad q\left( {\frac{1}{{{d_n}}}} \right) = \sum\limits_{i = 1}^n {{{\underbrace {\left( {1-\frac{{{d_i}}}{{{d_n}}}} \right)}_{ \leq 1-\frac{{{d_1}}}{{{d_n}}}}}^2}x_i^2} \leq {\left( {1-\frac{{{d_1}}}{{{d_n}}}} \right)^2}\left\| {\vec x} \right\|_2^2

Mit der bereits bewiesenen Behauptung \hat t \geq \frac{1}{{{d_n}}} folgt:

\left\| {{{\vec x}^1}} \right\|_2^2 = q\left( {\hat t} \right) \leq {\left( {1-\hat t{d_1}} \right)^2}\left\| {{{\vec x}^0}} \right\|_2^2 \leq {\left( {1-\frac{{{d_1}}}{{{d_n}}}} \right)^2}\left\| {{{\vec x}^0}} \right\|_2^2

\quad \Rightarrow \quad \left\| {{{\vec x}^1}} \right\| \leq \left( {1-\frac{{{d_1}}}{{{d_n}}}} \right){\left\| {{{\vec x}^0}} \right\|_2}

\quad \Rightarrow \quad \left\| {{{\vec x}^k}} \right\| \leq {\left( {1-\frac{{{d_1}}}{{{d_n}}}} \right)^k}{\left\| {{{\vec x}^0}} \right\|_2}

b)

Wir haben hier eine lineare Konvergenzordnung. Die Konvergenz kann also auch langsam sein, falls \frac{{{d_1}}}{{{d_n}}} \approx 0. Daher wird das Gradientenverfahren heute kaum noch verwendet.