U 01.3 – Eindeutig bestimmtes Minimum und Gradientenverfahren

 

Es sei

f:{\mathbb{R}^n} \to \mathbb{R},\quad f\left( {\vec x} \right) = \frac{1}{2}{\vec x^T}A\vec x-{\vec b^T}\vec x+c,

und seien 0 \ne \vec v,\vec x \in {\mathbb{R}^n} beliebig, aber fest gewählt und A symmetrisch. Weiter sei

\varphi :\mathbb{R} \to \mathbb{R},\quad \varphi \left( t \right) = f\left( {\vec x-t\vec v} \right).

  1. Zeigen Sie, dass die Funktion \varphi ein eindeutig bestimmtes Minimum an der Stelle

    \hat t = \frac{{\nabla f{{\left( {\vec x} \right)}^T}\vec v}}{{{{\vec v}^T}Av}}

    annimmt. An der Minimalstelle ist

    \varphi \left( {\hat t} \right) = f\left( {\vec x} \right)-\frac{1}{2}\frac{{{{\left( {\nabla f{{\left( {\vec x} \right)}^T}\vec v} \right)}^2}}}{{{{\vec v}^T}A\vec v}}

  2. In der Vorlesung wurde für das Gradientenverfahren die Iterationsvorschrift

    {\vec x^{i+1}} = {\vec x^i}-\lambda \nabla f\left( {{{\vec x}^i}} \right)

    angegeben. Wie ist \lambda nach a) optimal zu wählen?

Lösung

a)

Wir haben gegeben:

\varphi \left( t \right): = f\left( {\vec x-t\vec v} \right), wobei \vec x,\vec v \in {\mathbb{R}^n},\:\vec v \ne 0 fest.

Dies schreiben wir nun aus:

\varphi \left( t \right) = \frac{1}{2}{\left( {\vec x-t\vec v} \right)^T}A\left( {\vec x-t\vec v} \right)-{{\vec b}^T}\left( {\vec x-t\vec v} \right)+c

\quad \Rightarrow \quad \varphi \left( t \right) = \frac{1}{2}{{\vec x}^T}A\vec x-\frac{t}{2}{{\vec x}^T}A\vec v-\frac{t}{2}{{\vec v}^T}A\vec x+\frac{{{t^2}}}{2}{{\vec v}^T}A\vec v-{{\vec b}^T}\vec x+t{{\vec b}^T}\vec v+c

\quad \Rightarrow \quad \varphi \left( t \right) = \frac{{{t^2}}}{2}{{\vec v}^T}A\vec v-t\left( {\frac{1}{2}{{\vec x}^T}A\vec v+\frac{1}{2}{{\vec v}^T}A\vec x-{{\vec b}^T}\vec v} \right)+\underbrace {\frac{1}{2}{{\vec x}^T}A\vec x-{b^T}\vec x+c}_{ = f\left( {\vec x} \right)}

Aufgrund der Symmetrie von A gilt: {\vec v^T}A\vec x = {\vec x^T}A\vec v.

Damit folgt:

\varphi \left( t \right) = \frac{{{t^2}}}{2}{{\vec v}^T}A\vec v-t\left( {{{\vec x}^T}A-{{\vec b}^T}} \right)\vec v+f\left( {\vec x} \right)

\quad \Rightarrow \quad \varphi \left( t \right) = \frac{{{t^2}}}{2}{{\vec v}^T}A\vec v-t{\left( {A\vec x-\vec b} \right)^T}\vec v+f\left( {\vec x} \right)

\quad \Rightarrow \quad \varphi \left( t \right) = \frac{{{t^2}}}{2}{{\vec v}^T}A\vec v-t\nabla f{\left( {\vec x} \right)^T}\vec v+f\left( {\vec x} \right)

Durch quadratisches Ergänzen erhalten wir:

\varphi \left( t \right) = \frac{1}{2}\left( {{{\vec v}^T}A\vec v} \right){\left( {t-\frac{{\nabla f{{\left( {\vec x} \right)}^T}\vec v}}{{{{\vec v}^T}A\vec v}}} \right)^2}+f\left( {\vec x} \right)-\frac{1}{2}\frac{{{{\left( {\nabla f{{\left( {\vec x} \right)}^T}\vec v} \right)}^2}}}{{{{\vec v}^T}A\vec v}}

Da nur der erste Term von t abhängt, ist \varphi \left( t \right) genau dann minimal, wenn

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

In diesem Falle ist dann

\varphi \left( {\hat t} \right) = f\left( {\vec x} \right)-\frac{1}{2}\frac{{{{\left( {\nabla f{{\left( {\vec x} \right)}^T}\vec v} \right)}^2}}}{{{{\vec v}^T}A\vec v}}

b)

Beim Gradientenverfahren

{\vec x^{i+1}} = {\vec x^i}-\lambda \nabla f\left( {{{\vec x}^i}} \right)

sollte \lambda so gewählt werden, dass \varphi \left( \lambda \right) = f\left( {{{\vec x}^i}-\lambda \nabla f\left( {{{\vec x}^i}} \right)} \right) minimal wird.

Nach a) also:

\lambda = \hat t = \frac{{\nabla f{{\left( {\vec x} \right)}^T}\nabla f\left( {\vec x} \right)}}{{\nabla f{{\left( {\vec x} \right)}^T}A\nabla f\left( {\vec x} \right)}}