Figure 
gives a closer look at the ridge problem. Hill climbing
algorithms typically take orthogonal steps, e.g. they might move in one
dimension at a time. The objective function in the figure has a long, narrow
ridge with a tilted axis of symmetry. The optimum direction of change has
components in both dimensions. The arrows show the behavior of a procedure
restricted to use two orthogonal vectors. Unless the ridge is optimally
oriented, this procedure is very inefficient, taking many small steps to get to
the maximum. The local optimizer presented in the previous chapter suffers
from this problem. Although it is not restricted to orthogonal directions and
chooses its steps randomly, without a memory of previous steps, it is unable
to keep the right direction.
Figure:
The ridge problem: The concentric ellipses are the contour map of an objective
function. A hill-climbing algorithm restricted to moves in a single dimension
has to go through many zig-zags to reach the optimum.
Figure:
The number of combinations of main directions increase exponentially with the
number of dimensions.
Figure
illustrates the problem with trying to use systematic combinations of
the main directions. In one dimension we only have a +1 direction and
a -1 direction. In two dimensions, in addition to the four main
directions, we have 4 more secondary directions that are combinations
of the main ones. In three dimensions the total number goes up to 26.
The step has n components in n dimensions, and each of them can take
one of three values, {-1,1,0}. We subtract away the origin and we
have (3^n - 1) directions in n dimensions.