Conjugate Direction Methods in Optimization

One of the fundamental problems in optimization is that of developing computational procedures for finding extreme points of an objective function. The purpose of this book is to derive a class of iterative methods for obtaining these extreme points. We term these methods conjugate direction methods because of their geometric interpretation in the quadratic case. We concentrate on finding a minimum point x₀ of a real-valued function f of n real variables. Obviously, maximum points of f are minimum points of –f We also extend our routines to yield saddle points of f In the main we consider unconstrained minimum problems. This specialization is not as restrictive as it may seem because constrained problems can be reduced to a sequence of unconstrained minimum problems by a method of multipliers or to a sequence of unconstrained saddle point problems involving Lagrangians. Applications of unconstrained methods to constrained problems will be given in special sections in the text.

In the preceding pages we considered two methods for finding a minimum point of a real-valued function f of n real variables, namely, Newton’s method and the gradient method. The gradient method is easy to apply. However, convergence is often very slow. On the other hand, Newton’s algorithm normally has rapid convergence but involves considerable computation at each step. Recall that one step of Newton’s method involves the computation of the gradient f′(x) and the Hessian f″(x) of f and the solution of a linear system of equations, usually, by the inversion of the Hessian f″(x) of f It is a crucial fact that a Newton step can be accomplished instead by a sequence of n linear minimizations in n suitably chosen directions, called conjugate directions. This fact is the central theme in the design of an important class of minimization algorithms, called conjugate direction algorithms.

We continue the study of conjugate direction methods for finding the minimum point x₀ of a positive definite quadratic function .

A first form of the conjugate gradient routine was given in Section 6, Chapter II. It was redeveloped in Section 3, Chapter III, as a CGS-method. In the present chapter we shall study the CG-algorithm in depth, giving several alternative versions of the CG-routine. It is shown that the number of steps required to obtain the minimum point of a quadratic function F is bounded by the number of distinct eigenvalues of the Hessian A of F. Good estimates of the minimum point are obtained early when the eigenvalues of A are clustered. If the Hessian A of F is nonnegative but not positive definite, a Cg-algorithm will yield the minimum point of F when minimum points of F exist. If A is indefinite and nonsingular, the function F has a unique saddle point. It can be found by a CG-routine except in special circumstances. However, a modified Cg-routine, called a planar Cg-algorithm, yields the critical point of F in all cases. In this modified routine-we obtain critical points of F successively on mutually conjugate lines and 2-planes, whereas, in the standard Cg-algorithm, we restrict ourselves to successively locating critical points of F on mutually conjugate lines. A generalized Cg-algorithm is given in Section 9 involving a generalized gradient HF′ of F. Such algorithms are useful when the Hessian A of F is sparse. They also enable us to minimize F on a prescribed N-plane. It is shown, in Section 11, that, in general, a conjugate direction algorithm is equivalent to a generalized Cg-algorithm in the sense that they generate the same estimates of the minimum point of F.