Page 343 - Applied Numerical Methods Using MATLAB

332 OPTIMIZATION
Remark 7.1. Weak Point of Newton Method.
The Newton method is usually more efficient than the steepest descent method
if only it works as illustrated above, but it is not guaranteed to reach the minimum
point. The decisive weak point of the Newton method is that it may approach one
of the extrema having zero gradient, which is not necessarily a (local) minimum,
but possibly a maximum or a saddle point (see Fig. 7.13).

7.1.6 Conjugate Gradient Method
Like the steepest descent method or Newton method, this method also uses the
gradient to search for the minimum point of an objective function, but in a
different way. It has two versions—the Polak–Ribiere (PR) method and the
Fletcher–Reeves (FR) method—that are slightly different only in the search
direction vector. This algorithm, summarized in the following box, is cast into
the MATLAB routine “opt_conjg()”, which implements PR or FR depending
on the last input argument KC = 1 or 2. The quasi-Newton algorithm used in
the MATLAB built-in routine “fminunc()” is similar to the conjugate gradi-
ent method.
This method borrows the framework of the steepest descent method and needs
a bit more effort for computing the search direction vector s(n). It takes at most N
iterations to reach the minimum point in case the objective function is quadratic
with a positive-definite Hessian matrix H as
1 T T
f(x) = x Hx + b x + c where x:an N-dimensional vector (7.1.15)
2

CONJUGATE GRADIENT ALGORITHM
Step 0. With the iteration number k = 0, find the objective function value
f 0 = f(x 0 ) for the initial point x 0 .
Step 1. Initialize the inside loop index, the temporary solution and the search
direction vector to n = 0, x(n) = x k and s(n) =−g k =−g(x k ), respec-
tively, where g(x) is the gradient of the objective function f(x).
Step 2.For n = 0to N − 1, repeat the following things:
Find the (optimal) step-size

α n = ArgMin f(x(n) + αs(n)) (7.1.16)
α
and update the temporary solution point to
x(n + 1) = x(n) + α n s(n) (7.1.17)

and the search direction vector to

s(n + 1) =−g n+1 + β n s(n) (7.1.18)