c10-1 (Numerical Recipes in C)

10.1 Golden Section Search in One Dimension397You are now ready to proceed with scaling the peaks (and/or plumbing thedepths) of practical optimization.CITED REFERENCES AND FURTHER READING:Dennis, J.E., and Schnabel, R.B. 1983, Numerical Methods for Unconstrained Optimization andNonlinear Equations (Englewood Cliffs, NJ: Prentice-Hall).Polak, E. 1971, Computational Methods in Optimization (New York: Academic Press).Gill, P.E., Murray, W., and Wright, M.H. 1981, Practical Optimization (New York: Academic Press).Acton, F.S.

1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America), Chapter 17.Jacobs, D.A.H. (ed.) 1977, The State of the Art in Numerical Analysis (London: AcademicPress), Chapter III.1.Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: PrenticeHall).Dahlquist, G., and Bjorck, A.

1974, Numerical Methods (Englewood Cliffs, NJ: Prentice-Hall),Chapter 10.10.1 Golden Section Search in One DimensionRecall how the bisection method finds roots of functions in one dimension(§9.1): The root is supposed to have been bracketed in an interval (a, b). Onethen evaluates the function at an intermediate point x and obtains a new, smallerbracketing interval, either (a, x) or (x, b). The process continues until the bracketinginterval is acceptably small.

It is optimal to choose x to be the midpoint of (a, b)so that the decrease in the interval length is maximized when the function is asuncooperative as it can be, i.e., when the luck of the draw forces you to take thebigger bisected segment.There is a precise, though slightly subtle, translation of these considerations tothe minimization problem: What does it mean to bracket a minimum? A root of afunction is known to be bracketed by a pair of points, a and b, when the functionhas opposite sign at those two points. A minimum, by contrast, is known to bebracketed only when there is a triplet of points, a < b < c (or c < b < a), such thatf(b) is less than both f(a) and f(c).

In this case we know that the function (if itis nonsingular) has a minimum in the interval (a, c).The analog of bisection is to choose a new point x, either between a and b orbetween b and c. Suppose, to be specific, that we make the latter choice. Then weevaluate f(x). If f(b) < f(x), then the new bracketing triplet of points is (a, b, x);Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).one-dimensional sub-minimization. Turn to §10.6 for detailed discussionand implementation.• The second family goes under the names quasi-Newton or variable metricmethods, as typified by the Davidon-Fletcher-Powell (DFP) algorithm(sometimes referred to just as Fletcher-Powell) or the closely relatedBroyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. These methodsrequire of order N 2 storage, require derivative calculations and onedimensional sub-minimization. Details are in §10.7.398Chapter 10.Minimization or Maximization of Functions2416653Figure 10.1.1.

Successive bracketing of a minimum. The minimum is originally bracketed by points1,3,2. The function is evaluated at 4, which replaces 2; then at 5, which replaces 1; then at 6, whichreplaces 4. The rule at each stage is to keep a center point that is lower than the two outside points.

Afterthe steps shown, the minimum is bracketed by points 5,3,6.contrariwise, if f(b) > f(x), then the new bracketing triplet is (b, x, c). In all casesthe middle point of the new triplet is the abscissa whose ordinate is the best minimumachieved so far; see Figure 10.1.1. We continue the process of bracketing until thedistance between the two outer points of the triplet is tolerably small.How small is “tolerably” small? For a minimum located at a value b, youmight naively think that you will be able to bracket it in as small a range as(1 − )b < b < (1 + )b, where is your computer’s floating-point precision, anumber like 3 × 10−8 (for float) or 10−15 (for double).

Not so! In general, theshape of your function f(x) near b will be given by Taylor’s theorem1f(x) ≈ f(b) + f 00 (b)(x − b)22(10.1.1)The second term will be negligible compared to the first (that is, will be a factor smaller and will act just like zero when added to it) whenever√|x − b| < |b|s2 |f(b)|b2 f 00 (b)(10.1.2)The reason for writing the right-hand side in this way is that, for most functions,the final square root is a number of order unity.

Therefore, as√a rule of thumb, itis hopeless to ask for a bracketing interval of width less than times its centralvalue, a fractional width of only about 10−4 (single precision) or 3 × 10−8 (doubleprecision). Knowing this inescapable fact will save you a lot of useless bisections!The minimum-finding routines of this chapter will often call for a user-suppliedargument tol, and return with an abscissa whose fractional precision is about ±tol(bracketing interval of fractional size about 2×tol).

Unless you have a betterSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).4539910.1 Golden Section Search in One Dimensionestimate for the right-hand side of equation (10.1.2), you should set tol equal to(not much less than) the square root of your machine’s floating-point precision, sincesmaller values will gain you nothing.It remains to decide on a strategy for choosing the new point x, given (a, b, c).Suppose that b is a fraction w of the way between a and c, i.e.c−b=1−wc−a(10.1.3)Also suppose that our next trial point x is an additional fraction z beyond b,x−b=zc−a(10.1.4)Then the next bracketing segment will either be of length w + z relative to the currentone, or else of length 1 − w.

If we want to minimize the worst case possibility, thenwe will choose z to make these equal, namelyz = 1 − 2w(10.1.5)We see at once that the new point is the symmetric point to b in the original interval,namely with |b − a| equal to |x − c|. This implies that the point x lies in the largerof the two segments (z is positive only if w < 1/2).But where in the larger segment? Where did the value of w itself come from?Presumably from the previous stage of applying our same strategy. Therefore, if zis chosen to be optimal, then so was w before it. This scale similarity implies thatx should be the same fraction of the way from b to c (if that is the bigger segment)as was b from a to c, in other words,z=w1−wEquations (10.1.5) and (10.1.6) give the quadratic equation√3− 52≈ 0.38197yieldingw=w − 3w + 1 = 02(10.1.6)(10.1.7)In other words, the optimal bracketing interval (a, b, c) has its middle point b afractional distance 0.38197 from one end (say, a), and 0.61803 from the other end(say, b).

These fractions are those of the so-called golden mean or golden section,whose supposedly aesthetic properties hark back to the ancient Pythagoreans. Thisoptimal method of function minimization, the analog of the bisection method forfinding zeros, is thus called the golden section search, summarized as follows:Given, at each stage, a bracketing triplet of points, the next point to be triedis that which is a fraction 0.38197 into the larger of the two intervals (measuringfrom the central point of the triplet). If you start out with a bracketing triplet whosesegments are not in the golden ratios, the procedure of choosing successive pointsat the golden mean point of the larger segment will quickly converge you to theproper, self-replicating ratios.The golden section search guarantees that each new function evaluation will(after self-replicating ratios have been achieved) bracket the minimum to an intervalSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.