Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematik-Online lexicon:

Steepest Descent for a Quadratic Function

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview
For a quadratic function

$\displaystyle f(x) = \frac{1}{2} x^{\text{t}} A x - b^{\text{t}} x $

with a symmetric positive definite matrix $ A$, one step $ x\to y$ of the method of steepest decent has the form

$\displaystyle y = x + t d,\ d = -$grad$\displaystyle f(x) = b - Ax \,. $

In this special case, the minimum of

\begin{displaymath} \begin{array}{rcl} f(x+td) &=& \frac{1}{2} (x+td)^{\text{t}}... ...A d\,t^2 + (x^{\text{t}}Ad - b^{\text{t}}d)\,t + c \end{array}\end{displaymath}

can be determined explicitly. Setting the derivative with respect to $ t$ to zero, we obtain

$\displaystyle 0=d^{\text{t}}Ad\, t - (\underbrace{b-Ax}_{d})^{\text{t}}d \,, $

which yields the formula

$\displaystyle t = \frac{d^{\text{t}} d}{d^{\text{t}}Ad} \,. $

The figure illustrates that steepest decent can lead to unwanted oscillations if $ A$ has eigenvalues of different magnitude. An extreme example is provided by choosing

$\displaystyle A = \left(\begin{array}{cc} 1&0 \\ 0&100 \end{array}\right),\quad b = \left(\begin{array}{c} 0 \\ 0 \end{array}\right) \,. $

Then, for $ x=(\begin{array}{cc} c & 1 \end{array})^{\text{t}}$, we have

$\displaystyle d = -\,\left(\begin{array}{c} c \\ 100 \end{array}\right),\quad Ad = -\, \left(\begin{array}{c} c \\ 10^4 \end{array}\right) $

and

$\displaystyle d^{\text{t}}d = c^2 + 10^4,\quad d^{\text{t}}Ad = c^2 + 10^6,\quad t = \frac{c^2 + 10^4}{c^2 + 10^6} \,. $

This yields

$\displaystyle y= \left(\begin{array}{c} c \\ 1 \end{array}\right) - \frac{c^2... ...9c^2}{c^2 + 10^6} \left(\begin{array}{c} 10^4/c \\ -1 \end{array}\right) \,. $

In particular, for $ c=100$,

$\displaystyle y = \frac{99}{101} \left(\begin{array}{c} x_1 \\ -x_2 \end{array}\right) \,. $

We see that the distance to the minimum at the origin is reduced by less than $ 1\%$ in each iteration step.
[Links]
  automatisch erstellt am 22.  6. 2016