As seen in the previous subsection, the reason why the method of Steepest Descent converges slowly is that it has to take a right angle turn after each step, and consequently search in the same direction as earlier steps (see Figure 4.1). The method of Conjugate Gradients is an attempt to mend this problem by ``learning'' from experience.
``Conjugacy'' means that two unequal vectors, 
and 
, are
orthogonal with respect to any symmetric positive definite matrix, for example
in (4.6); i.e.
This can be looked upon as a generalization of orthogonality, for which
is the unity matrix. The idea is to let each search direction be
dependent on all the other directions searched to locate the minimum of 
through equation (4.9). A set of such search directions is referred to as a
-orthogonal, or conjugate, set, and it will take a positive definite
n-dimensional quadratic function as given in (4.6) to its minimum point in,
at most, n exact linear searches. This method is often referred to as Conjugate
Directions, and a short description follows.
The best way to visualize the working of Conjugate Directions is by comparing the space
we are working in with a ``stretched'' space. An example of this ``stretching'' of space
is illustrated in Figure 4.3: (a) demonstrates the shape of the contours of
a quadratic function in real space, which are elliptical (for 
). Any
pair of vectors that appear perpendicular in this space, would be orthogonal. (b) show
the same drawing in a space that are stretched along the eigenvector
axes so that the elliptical contours from (a) become
circular. Any pair of vectors that appear to be perpendicular in this space, is in fact
-orthogonal. The search for a minimum of the quadratic functions starts at
in Figure 4.3(a), and takes a step in the direction 
and stops at the point 
. This is a minimum point along that direction,
determined the same way as for the Steepest Decent method in the previous section: the
minimum along a line is where the directional derivative is zero (equation
(4.8)). The essential difference between the Steepest Descent and the
Conjugate Directions lies in the choice of the next search direction from this minimum
point. While the Steepest Descent method would search in the direction 
in
Figure 4.3(a), the Conjugate Direction method would chose 
. How
come Conjugate Directions manage to search in the direction that leads us straight to
the solution 
? The answer is found in Figure 4.3(b): In this
stretched space, the direction appears to be a tangent to the now circular
contours at the point . Since the next search direction is
constrained to be -orthogonal to the previous, they will appear perpendicular
in this modified space. Hence, will take us directly to the minimum point of
the quadratic function .
Figure 4.3: Optimality of the method of Conjugate Directions. (a) Lines that
appear perpendicular are orthogonal. (b) The same problem in a ``stretched'' space.
Lines that appear perpendicular are -orthogonal.
To avoid searching in directions that have been searched before, the Conjugate Direction
guarantees that the minimization of 
along one direction does not
``spoil'' the minimization along another; i.e. that after i steps, 
will
be minimized over all searched directions. This is essentially what is stated in
equation (4.9): A search along has revealed where the gradient
is perpendicular to , 
, and as we now move
along some new direction , the gradient changes by
(see equation (4.6)). In order to
not interfere with the minimization along , we require that the gradient
remain perpendicular to ; i.e. that the change in gradient itself be
perpendicular to . Hence, we have equation (4.9). We see from
Figure 4.3(b), where and appear perpendicular
because they are -orthogonal, that it is clear that must point to
the solution . A thorough description of the linear Conjugate Directions and
Conjugate Gradients methods has been given by Shew.
The Conjugate Gradients method is a special case of the method of Conjugate Directions, where the conjugate set is generated by the gradient vectors. This seems to be a sensible choice since the gradient vectors have proved their applicability in the Steepest Descent method, and they are orthogonal to the previous search direction. For a quadratic function, as given in equation (4.6), the procedure is as follows.
The initial step is in the direction of the steepest descent:
Subsequently, the mutually conjugate directions are chosen so that
where the coefficient 
is given by, for example, the so called
Fletcher-Reeves formula:
For details, see Walsh. The step length along each direction is given by
The resulting iterative formula is identical to (4.5).
When the matrix in (4.13) is not known, or is too computationally
costly to determine, the stepsize can be found by linear searches. For the Conjugate
Gradient method to converge in n iterations, these linear searches need to be accurate.
Even small deviations can cause the search vectors to lose -orthogonality,
resulting in the method spending more than n iterations in locating the minimum point.
In practice, accurate linear searches are impossible, both due to numerical accuracy and
limited computing time. The direct use of equation (4.13) will most likely
not bring us to the solution in n iterations either, the reason being the limited
numerical accuracy in the computations which gradually will make the search vectors lose
their conjugacy. It should also be mentioned that if the matrix is badly
scaled, the convergence will be slowed down considerably, as it was for the Steepest
Descent method.
Even though the Conjugate Gradients method is designed to find the minimum point for
simple quadratic functions, it also does the job well for any continuous function
for which the gradient 
can be computed. Equation
(4.13) can not be used for non-quadratic functions, so the step length has
to be determined by linear searches. The conjugacy of the generated directions may then
progressively be lost, not only due to the inaccurate linear searches, but also due to
the non-quadratic terms of the functions. An alternative to the Fletcher-Reeves formula
that, to a certain extent, deals with this problem, is the Polak-Ribière formula
Press:
The difference in performance between these two formulas is not big though, but the Polak-Ribière formula is known to perform better for non-quadratic functions.
The iterative algorithm for the Conjugate Gradients method for non-quadratic functions using the Polak-Ribière formula is given in Algorithm 4.2.
Regardless of the direction-update formula used, one must deal with the loss of conjugacy that results from the the non-quadratic terms. The Conjugate Gradients method is often employed to problems where the number of variables n is large, and it is not unusual for the method to start generating nonsensical and inefficient directions of search after a few iterations. For this reason it is important to operate the method in cycles, with the first step being the Steepest Descent step. One example of a restarting policy is to restart with the Steepest Descent step after n iterations after the preceding restart.
Another practical issue relates to the accuracy of the linear search that is necessary for efficient computation. On one hand, an accurate linear search is needed to limit the loss of direction conjugacy. On the other hand, insisting on very accurate line search can be computationally expensive. To find the best possible middle path, trial and error is needed.
The Conjugate Gradients method is apart from being an optimization method, also one of the most prominent iterative method for solving sparse systems of linear equations. It is fast and uses small amounts of storage since it only needs the calculation and storage of the second derivative at each iteration. The latter becomes significant when n is so large that problems of computer storage arises. But, everything is not shiny; the less similar f is to a quadratic function, the more quickly the search directions lose conjugacy, and the method may in the worst case not converge at all. Although, it is generally to be preferred over the Steepest Descent method.
