Software Design for Engineers and Scientists

to the steepest but taking account of previous directions). For example,

Figure 16.3 shows a function in 2D, where lightness represents the

function value.

This has a single minimum at the origin, shown at the centre of the

diagram. A descent algorithm started at any point would just walk

towards the minimum, adjusting its step size as it converged.

But Figure 16.4 shows a different kind of 2D function.

This time there are many minima and descent is practically use-

less. The problem is like trying to find the highest tuft in the pile of

a carpet.

So in multidimensional optimization there are two extremes, and

some interesting places between. At one extreme are the functions

with one minimum. The minimum can be found quickly, by descent.

At the other extreme are noiselike functions, where one of the huge

number of local minima happens to be the global minimum. The only

hope of finding the global minimum is exhaustive search. The interest-

ing cases in between are where there are a significant number of local

minima that are good enough – they may not be the global minimum,

but they are close in value. Finding one of these will take a lot longer

than a single descent, but much shorter than searching every possible

value. Methods for doing just this include simulated annealing and

various kinds of evolutionary algorithms. There is another interesting

case though, exemplified by the 2D function in Figure 16.5.

This is the sum of a simple, single minimum, function and noise. If

we were to take a cross-section through it, we would get a 1D equiva-

lent something like Figure 16.6.

This is another intermediate case between global and local opti-

mization. But we don’t want to use as expensive a method as simu-

lated annealing here. We really want a kind of noise-resilient local

optimizer. That is the problem addressed in this chapter.

Multidimensional optimization is a standard numerical method, so the

place to start is the contents and index pages of standard textbooks.

Well, not quite the first. A Google search takes only a few seconds, and

332 Software Design for Engineers and Scientists

Figure 16.3 A two-dimensional function

with a single minimum at the origin

Figure 16.4 A two-dimensional function

with many minima

Figure 16.5 A noisy two-dimensional

function

16.3 Researching possible

solutions

y

x

Figure 16.6 A noisy one-dimensional

function