Biomedical Engineering Reference
In-Depth Information
minimum, M, to within a step's length. (There are, of course, much
more efficient ways for him to find the minimum than always taking
equal-sized steps.) The point is, if the searcher starts off
down
the
slope, he is headed in the right direction and will eventually reach the
bottom.
The direction set methods of optimization extend the one-dimensional
idea to landscapes of many dimensions. They differ mainly in the
way in which they pick the downhill direction, realizing that we now
mean downhill in a multi-dimensional world. Figure 9.7 shows how
this might look in a two-dimensional world. The searcher starts as
usual at the point S. In the method of steepest descent he determines
the direction of steepest descent from that point - that is, the direction
in which the gradient is largest, shown by the short arrow at S. He
then sets off in that direction
−
staying, therefore, in the colored plane
of Figure 9.7. He keeps
going in that plane until
he reaches a minimum,
1
because this is a 1D
search, which we have
just seen is feasible.
Once at M
1
, he
determines the direction
of steepest descent from
that point and then goes
off in that direction,
performing a 1D search,
until he again finds a
minimum. He continues
this process until he no longer finds himself getting significantly
lower. It is also possible to reassess the direction of steepest descent
after each step, rather than after reaching the minimum in the plane
determined by the first step.
One problem with the method of steepest descent is that it can be very
objective
function, f(x,y)
objective
function, f(x,y)
y
y
S
S
M . He can do this
M
1
M
1
x
x
Figure 9.7. Using the method of steepest
descent in a two-dimensional world - in this
case a valley somewhat of the form of the
crater of a volcano (see text)
inefficient. For example, if the searcher finds himself in a long
narrow valley, he may find himself taking very many small steps as
he continually crosses the valley from side to side, while inching
toward the bottom. The conjugate gradient method largely solves this
problem. It differs mainly in its way of deciding on the next direction
to go after each step. Its algorithm to do this is based on finding good
directions in which to go that do not “interfere” with the direction
