Minimization or Maximization of Functions part 2

one-dimensional sub-minimization. Turn to §10.6 for detailed discussion and implementation. • The second family goes under the names quasi-Newton or variable metric methods, as typified by the Davidon-Fletcher-Powell (DFP) algorithm
Nội dung trích xuất từ tài liệu:
Minimization or Maximization of Functions part 2 10.1 Golden Section Search in One Dimension 397 one-dimensional sub-minimization. Turn to §10.6 for detailed discussion and implementation. • The second family goes under the names quasi-Newton or variable metric methods, as typified by the Davidon-Fletcher-Powell (DFP) algorithm (sometimes referred to just as Fletcher-Powell) or the closely related Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. These methods visit 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). readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine- Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) require of order N 2 storage, require derivative calculations and one- dimensional 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 and Nonlinear 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: Mathe- matical Association of America), Chapter 17.Jacobs, D.A.H. (ed.) 1977, The State of the Art in Numerical Analysis (London: Academic Press), Chapter III.1.Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: Prentice- Hall).Dahlquist, G., and Bjorck, A. 1974, Numerical Methods (Englewood Cliffs, NJ: Prentice-Hall), Chapter 10.10.1 Golden Section Search in One Dimension Recall 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);398 Chapter 10. Minimization or Maximization of Functions 2 4 1 4 visit 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). ...