Graphics Programs Reference
In-Depth Information
10.2 Minimization Along a Line
f ( x )
Local minimum
Figure 10.1. Example of local and global minima.
Global minimum
Constraint boundaries
x
c
d
Consider the problem of minimizing a function f ( x )ofa single variable x with the
constraints c
d .Ahypothetical plot of the functionis shown in Fig. 10.1. There
aretwominimumpoints:astationary pointcharacterizedby f ( x )
x
0that represents
a local minimum, andaglobal minimum at the constraint boundary. It appearsthat
finding the global minimum issimple.All the stationary points couldbe locatedby
finding the roots of df
=
0, and each constraint boundary may be checked fora
global minimum by evaluating f ( c ) and f ( d ). Thenwhydo we needanoptimization
algorithm? We needit if f ( x ) is difficult or impossible to differentiate; for example, if
f represents a complex computeralgorithm.
/
dx
=
Bracketing
Before a minimizationalgorithm can beentered, the minimum point must be brack-
eted. The procedureofbracketing issimple: start with an initial valueof x 0 and move
downhill computing the functionat x 1 ,
until we reach the point x n where
f ( x ) increases for the first time. The minimum point is nowbracketedinthe inter-
val( x n 2
x 2 ,
x 3 ,...
x i be? It is not agoodidea have
a constant h i since it oftenresults in too many steps.Amoreefficient scheme isto
increase the size with every step, the goal being to reach the minimum quickly,even
if the resulting bracket is wide.We chose to increase the step size by a constantfactor;
that is, we use h i + 1 =
,
x n ).What should the step size h i
=
x i + 1
ch i , c
>
1.
Golden Section Search
The golden section search is the counterpartofbisectionused in finding roots of
equations. Suppose that the minimum of f ( x )has beenbracketedinthe interval
( a
,
b )oflength h . To telescope the interval, weevaluate the functionat x 1 =
b
Rh
and x 2 =
a
+
Rh , as shown in Fig. 10.2(a). The constant R will be determined shortly.
If f 1 >
f 2 as indicatedinthe figure, the minimum lies in ( x 1 ,
b ); otherwise it is located
in ( a
,
x 2 ).
Search WWH ::




Custom Search