Biomedical Engineering Reference
In-Depth Information
where
g
(
k
)
is the gradient vector at point
q
(
k
)
and γ
(
k
)
is a scalar given by
g
(
k
)
T
g
(
k
)
(
g
(
k
−
1)
)
T
g
(
k
−
1)
γ
(
k
)
=
(5.3)
I have used the superscript T to denote the transpose of a matrix. The line search method
is then used to determine the distance to be moved along this vector. This algorithm was
first proposed by Fletcher and Reeves (1964).
Conjugate gradients methods produce a set of directions that overcome the oscillatory
behaviour of steepest descents in narrow valleys. Successive directions are not at right
angles to each other. Such methods are also referred to as
conjugate direction
methods.
Polak and Ribière (1969) proposed an alternative form for the scalar γ
(
k
)
:
g
(
k
)
g
(
k
−
1)
T
g
(
k
)
(
g
(
k
−
1)
)
T
g
(
k
−
1)
−
γ
(
k
)
=
(5.4)
For a purely quadratic function, their method is identical to the original Fletcher-Reeves
algorithm. The authors pointed out that most
U
's encountered in chemistry are only
approximately quadratic, and that their method was therefore superior.
5.8 Second-Order Methods
5.8.1 Newton-Raphson
Second-order methods use not only the gradient but also the Hessian to locate a min-
imum. Before launching into any detail about second-order methods, it is worth spending
a little time discussing the well-known Newton-Raphson method for finding the roots of
an equation of a single variable. This is a simple illustration of a second-order method. For
illustration, consider the function
x
exp
−
x
2
f
(
x
)
=
shown as the full curve in Figure 5.7. It is obvious by inspection that our chosen function
has roots at
x
, but suppose for the sake of argument that we do
not know that the function had a root at
x
=
0 and at
+∞
and
−∞
=
0. We might make a guess that the function
has a root at (say)
x
=
0.4. This is our first guess, so I set the iteration count
=
1 and write
the guess
x
(1)
(also, the function has a value of
f
(1)
=
0.3409). Thus we have
x
(1)
f
(1)
=
0.4,
=
0.3409
The function can be differentiated to give
d
x
=
1
2
x
2
exp
−
x
2
d
f
−
and the gradient
g
(1)
at
x
(1)
=
0.4 has a value 0.5795. The tangent line at
x
(1)
=
0.4 is
therefore
y
=
0.5795
x
+
0.1091
