Next: Conjugate Gradient Method Up: Lecture 8 Previous: Inexact Line Search

Conjugate Direction Methods

We now look at another type of methods that only use gradient information. Remember that the Steepest Descent Method had problems with ill-conditioned problems.

We start by examining the quadratic problem

$\begin{displaymath} \min_x \frac{1}{2} x^T Q x - b^T x, \end{displaymath}$

with the solution Q x^* = b.

Conjugate Directions Definition. Two vectors, d₁ and d₂, are Q-orthogonal (or conjugate with respect to Q) if d₁^T Q d₂ = 0.

Proposition. If Q is positive definite, and a set of nonzero vectors, $d_0, d_1, \ldots , d_k$ , are Q-orthogonal, then these vectors are linearly independent.

Proof. By contradiction. If linearly dependent, then there exists $\alpha_i$ such that $\alpha_0 d_0 + \ldots + \alpha_k d_k = 0$
Then we have that $\alpha_i d_i^T Q d_i = 0$
Contradiction, since Q is positive definite $\Rightarrow \quad d_i^T Q d_i \gt 0 \quad \Rightarrow \quad \alpha_i = 0$

Why Q-orthogonality?

Assume n Q-orthogonal vectors, $d_0, \ldots , d_{n-1}$ , corresponding to the positive definite $n \times n$ matrix Q
They are linearly independent (see above).
We can write the solution to the quadratic minimization problem, x^*, as a linear combination of the d_is
$\begin{displaymath} x^* = \alpha_0 d_0 + \ldots + \alpha_{n-1} d_{n-1} \end{displaymath}$
We can compute the $\alpha_i$ s as
$\begin{displaymath} \alpha_i = \frac{d_i^T Q x^*}{d_i^T Q d_i} = \frac{d_i^T b }{d_i^T Q d_i} \end{displaymath}$
Then the solution is
$\begin{displaymath} x^* = \sum_{i=0}^{n-1} \frac{d_i^T b}{d_i^T Q d_i} d_i \end{displaymath}$
By the orthogonality of the (d_i:s) the expression for the $\alpha_i$ s is particulary simple
$\alpha_i$ is expressed in terms of the known vector b (not the solution x^* )
We can also note that the solution is improved for each basis vector that we add.

Now it remains to find the d_is.

Conjugate Direction Theorem
Let $\left\lbrace d_i \right\rbrace_{i=0}^{n-1}$ be a set of nonzero Q-orthogonal vectors. For any x₀ the sequence $\left\lbrace x_k \right\rbrace$ generated by

$\begin{displaymath} x_{k+1} = x_k + \alpha_k d_k\end{displaymath}$

with

$\begin{displaymath} \alpha_k = - \frac{ g_k^T d_k}{d_k^T Q d_k}\end{displaymath}$

and

g_k = Qx_k - b

we have that it converges to the unique solution x^* of Qx=b after n steps, i.e. x_n=x^*

Proof.

Write $x^*-x_0 = \alpha_0 d_0 + \ldots + \alpha_{n-1}d_{n-1}$
Multiply with Q and take the dot-product with d_k
$\begin{displaymath} \alpha_k = \frac{d_k^TQ(x^*-x_0)}{d^T_k Q d_k} \end{displaymath}$
From the iterative process leading to x_k we have
$\begin{displaymath} x_k-x_0 = \alpha_0 d_0 + \ldots + \alpha_{k-1}d_{k-1} \end{displaymath}$
From Q-orthogonality we have
d_k^TQ(x_k - x₀) = 0
Then
$\begin{displaymath} \alpha_k = \frac{d_k^TQ(x^*-x_k)}{d^T_k Q d_k} = - \frac{g_k^Td_k}{d^T_k Q d_k} \end{displaymath}$

Next: Conjugate Gradient Method Up: Lecture 8 Previous: Inexact Line Search

Mats Holmstr|m
10/31/1997