Next: About this document ... Up: Lecture 8 Previous: Conjugate Direction Methods

Conjugate Gradient Method

The CG method is realy a family of methods. At each step we choose a new search direction.

essentially in the negative gradient direction
but also Q-orthogonal to all previous search directions.

CG Algorithm

Choose a starting point $x_0 \in {\cal R}^n$ and define
d₀ = - g₀ = b - Qx₀
In each step
$\begin{displaymath} \begin{array} {l} x_{k+1} = x_k + \alpha_k d_k \\ \\ \alp... ...eta_k = \frac{g_{k+1}^T Q d_k}{d_k^T Q d_k}\\ \\ \end{array} \end{displaymath}$

Can be shown that the CG algorithm is a conjugate direction method, by proving that the search directions are Q-orthogonal.

CG Algorithm for Nonquadratic Problems
The idea behind using the CG method on nonquadratic problems is that functions can be well approximated locally by a quadratic function.

A natural approximation is

$\begin{displaymath} g_k \leftrightarrow \nabla f(x_k)^T \qquad \mathrm{och} \qquad Q \leftrightarrow F(x_k)\end{displaymath}$

A drawback is that F(x_k) is needed.

Fletcher-Reeve's Method

1.: Given x₀, compute $g_0 = \nabla f(x_0)^T$ and set d₀ = - g₀
2.: Set $x_{k+1} = x _k + \alpha_k d_k \quad$
where $\alpha_k$ minimizes $f(x_k + \alpha_k d_k)$
3.: Compute g_k as above
4.: If no restart ( k=n-1 ), set $d_{k+1} = g_{k+1} + \beta_k d_k \quad$ with
$\begin{displaymath} \beta_k = \frac{g_{k+1}^T g_{k+1}}{g_{k}^T g_{k}} \end{displaymath}$
Otherwise (if restart) set x₀ = x_n and goto 1. above.

Polak-Ribiere's Method Replace the formula for $\beta_k$ with

$\begin{displaymath} \beta_k = \frac{(g_{k+1}-g_k)^T g_{k+1}}{g_{k}^T g_{k}}\end{displaymath}$

Mats Holmstr|m
10/31/1997