Press, Teukolsly, Vetterling, Flannery - Numerical Recipes in C (523184), страница 94
Текст из файла (страница 94)
(For definiteness, we will henceforthregard the optimization problem as that of minimization.) These sections areconnected, with later ones depending on earlier ones. If you are just looking forthe one “perfect” algorithm to solve your particular application, you may feel thatwe are telling you more than you want to know. Unfortunately, there is no perfectoptimization algorithm.
This is a case where we strongly urge you to try more thanone method in comparative fashion. Your initial choice of method can be basedon the following considerations:• You must choose between methods that need only evaluations of thefunction to be minimized and methods that also require evaluations of thederivative of that function.
In the multidimensional case, this derivativeis the gradient, a vector quantity. Algorithms using the derivative aresomewhat more powerful than those using only the function, but notalways enough so as to compensate for the additional calculations ofderivatives. We can easily construct examples favoring one approach orfavoring the other. However, if you can compute derivatives, be preparedto try using them.• For one-dimensional minimization (minimize a function of one variable)without calculation of the derivative, bracket the minimum as described in§10.1, and then use Brent’s method as described in §10.2.
If your functionhas a discontinuous second (or lower) derivative, then the parabolic396Chapter 10.Minimization or Maximization of Functionsinterpolations of Brent’s method are of no advantage, and you might wishto use the simplest form of golden section search, as described in §10.1.• For one-dimensional minimization with calculation of the derivative, §10.3supplies a variant of Brent’s method which makes limited use of the firstderivative information. We shy away from the alternative of usingderivative information to construct high-order interpolating polynomials.In our experience the improvement in convergence very near a smooth,analytic minimum does not make up for the tendency of polynomialssometimes to give wildly wrong interpolations at early stages, especiallyfor functions that may have sharp, “exponential” features.We now turn to the multidimensional case, both with and without computationof first derivatives.• You must choose between methods that require storage of order N 2 andthose that require only of order N , where N is the number of dimensions.For moderate values of N and reasonable memory sizes this is not aserious constraint.
There will be, however, the occasional applicationwhere storage may be critical.• We give in §10.4 a sometimes overlooked downhill simplex method dueto Nelder and Mead. (This use of the word “simplex” is not to beconfused with the simplex method of linear programming.) This methodjust crawls downhill in a straightforward fashion that makes almost nospecial assumptions about your function. This can be extremely slow, butit can also, in some cases, be extremely robust. Not to be overlooked isthe fact that the code is concise and completely self-contained: a generalN -dimensional minimization program in under 100 program lines! Thismethod is most useful when the minimization calculation is only anincidental part of your overall problem.
The storage requirement is oforder N 2 , and derivative calculations are not required.• Section 10.5 deals with direction-set methods, of which Powell’s methodis the prototype. These are the methods of choice when you cannot easilycalculate derivatives, and are not necessarily to be sneered at even if youcan. Although derivatives are not needed, the method does require aone-dimensional minimization sub-algorithm such as Brent’s method (seeabove). Storage is of order N 2 .There are two major families of algorithms for multidimensional minimizationwith calculation of first derivatives.
Both families require a one-dimensionalminimization sub-algorithm, which can itself either use, or not use, the derivativeinformation, as you see fit (depending on the relative effort of computing the functionand of its gradient vector). We do not think that either family dominates the other inall applications; you should think of them as available alternatives:• The first family goes under the name conjugate gradient methods, as typified by the Fletcher-Reeves algorithm and the closely related and probablysuperior Polak-Ribiere algorithm.
Conjugate gradient methods requireonly of order a few times N storage, require derivative calculations and10.1 Golden Section Search in One Dimension397one-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.You 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);398Chapter 10.Minimization or Maximization of Functions241456653Figure 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 (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|*2 |f(b)|b2 f (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 better39910.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.b−a=wc−ac−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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
