Computational Physics

A4 Finding the optimum of a function 561

xxx 1324 xxxx 1324 x

Figure A.1. Bracketing the minimum using the bisection method. The pointx 4 is

chosen midway betweenx 1 andx 3. The two graphs show two possibilities for the

interval at the next step of the iteration. These intervals are indicated by the dotted

lines.

We takefto depend on a single variable at first. A sufficient (but not a necessary)
condition to have a local minimum in the interval[x 1 ,x 2 ]is to have a pointx 3
betweenx 1 andx 2 wherefassumes a value smaller thanf(x 1 )andf(x 2 ):

x 1 <x 3 <x 2 ; (A.9a)

f(x 3 )<f(x 1 ) and f(x 3 )<f(x 2 ). (A.9b)

There must always exist such a triad of points closely around the local minimum.
We use this condition to find an interval in whichfhas a minimum; we say that the
interval[x 1 ,x 2 ]‘brackets’ the minimum. Then we can apply an algorithm to narrow
this interval down to some required precision. In order to find the first bracketing
interval, consider two initial pointsx 1 andx 2 withf(x 2 )<f(x 1 ). Then we choose a
pointx 3 beyondx 2 and check whether the value offinx 3 is still smaller, or whether
we are going ‘uphill’ again. If that is the case we have bracketed the minimum,
otherwise we continue in the same manner with the pointsx 1 andx 3.
We consider now an algorithm for narrowing down the bracketing interval for
the case that we know the derivative of the functionf. Then we can use the methods
of the previous section, applied to the derivative offrather than tofitself. If the
derivative is not known, we can apply a variant of the bisection method described
in the previous section. The procedure is represented inFigure A.1. Suppose we
have pointsx 1 ,x 2 ,x 3 satisfying(A.9). We take a new pointx 4 either halfway in
betweenx 1 andx 3 , or betweenx 3 andx 2. Suppose we take the first option. Then
eitherx 4 is the lowest point of(x 1 ,x 4 ,x 3 )orx 3 is the lowest point of(x 4 ,x 3 ,x 2 ).
In the first case, the new interval becomes[x 1 ,x 3 ], withx 4 as the point in between,
in the second it becomes[x 4 ,x 2 ], withx 3 as the point in between, wherefassumes
a value lower than at the boundary points of the interval. There exist also methods
for minimising a function if we do not know the derivative. Usually, more elaborate
but more efficient procedures are used, which go by the name ofBrent’s method;
foradescriptionseeRefs.[ 1 , 7 ].