10.5 Direction Set(Powell's)Methods in Multidimensions 413 direction n,then any function of N variables f(P)can be minimized along the line n by our one-dimensional methods.One can dream up various multidimensional minimization methods that consist of sequences of such line minimizations.Different methods will differ only by how,at each stage,they choose the next direction n to try.All such methods presume the existence of a"black-box"sub-algorithm,which we might call linmin (given as an explicit routine at the end of this section).whose definition can be taken for now as linmin:Given as input the vectors P and n,and the function f,find the scalar A that minimizes f(P+An). 三 Replace P by P+An.Replace n by An.Done. g All the minimization methods in this section and in the two sections following g fall under this general schema of successive line minimizations.(The algorithm in $10.7 does not need very accurate line minimizations.Accordingly,it has its own approximate line minimization routine,Insrch.)In this section we consider a class of methods whose choice of successive directions does not involve explicit computation of the function's gradient;the next two sections do require such gradient 9 calculations.You will note that we need not specify whether linmin uses gradient information or not.That choice is up to you,and its optimization depends on your particular function.You would be crazy,however,to use gradients in linmin and not use them in the choice of directions,since in this latter role they can drastically reduce the total computational burden. But what if,in your application,calculation of the gradient is out of the question. 、a之 You might first think of this simple method:Take the unit vectors e1,e2,...en as a set of directions.Using linmin,move along the first direction to its minimum,then from there along the second direction to its minimum,and so on,cycling through the 6 whole set of directions as many times as necessary,until the function stops decreasing. This simple method is actually not too bad for many functions.Even more interesting is why it is bad,i.e.very inefficient,for some other functions.Consider a function of two dimensions whose contour map(level lines)happens to define a long,narrow valley at some angle to the coordinate basis vectors(see Figure 10.5.1). 10621 Then the only way "down the length of the valley"going along the basis vectors at each stage is by a series of many tiny steps.More generally,in N dimensions,if Numerical Recipes 43106 the function's second derivatives are much larger in magnitude in some directions than in others,then many cycles through all N basis vectors will be required in order to get anywhere.This condition is not all that unusual;according to Murphy's (outside Law,you should count on it. North Obviously what we need is a better set of directions than the ei's.All direction set methods consist of prescriptions for updating the set of directions as the method proceeds,attempting to come up with a set which either(i)includes some very good directions that will take us far along narrow valleys,or else (more subtly) (ii)includes some number of"non-interfering"directions with the special property that minimization along one is not "spoiled"by subsequent minimization along another,so that interminable cycling through the set of directions can be avoided.10.5 Direction Set (Powell’s) Methods in Multidimensions 413 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin 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) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). direction n, then any function of N variables f(P) can be minimized along the line n by our one-dimensional methods. One can dream up various multidimensional minimization methods that consist of sequences of such line minimizations. Different methods will differ only by how, at each stage, they choose the next direction n to try. All such methods presume the existence of a “black-box” sub-algorithm, which we might call linmin (given as an explicit routine at the end of this section), whose definition can be taken for now as linmin: Given as input the vectors P and n, and the function f, find the scalar λ that minimizes f(P+λn). Replace P by P + λn. Replace n by λn. Done. All the minimization methods in this section and in the two sections following fall under this general schema of successive line minimizations. (The algorithm in §10.7 does not need very accurate line minimizations. Accordingly, it has its own approximate line minimization routine, lnsrch.) In this section we consider a class of methods whose choice of successive directions does not involve explicit computation of the function’s gradient; the next two sections do require such gradient calculations. You will note that we need not specify whether linmin uses gradient information or not. That choice is up to you, and its optimization depends on your particular function. You would be crazy, however, to use gradients in linmin and not use them in the choice of directions, since in this latter role they can drastically reduce the total computational burden. But what if, in your application, calculation of the gradient is out of the question. You might first think of this simple method: Take the unit vectors e 1, e2,... eN as a set of directions. Using linmin, move along the first direction to its minimum, then from there along the second direction to its minimum, and so on, cycling through the whole set of directions as many times as necessary, until the function stops decreasing. This simple method is actually not too bad for many functions. Even more interesting is why it is bad, i.e. very inefficient, for some other functions. Consider a function of two dimensions whose contour map (level lines) happens to define a long, narrow valley at some angle to the coordinate basis vectors (see Figure 10.5.1). Then the only way “down the length of the valley” going along the basis vectors at each stage is by a series of many tiny steps. More generally, in N dimensions, if the function’s second derivatives are much larger in magnitude in some directions than in others, then many cycles through all N basis vectors will be required in order to get anywhere. This condition is not all that unusual; according to Murphy’s Law, you should count on it. Obviously what we need is a better set of directions than the ei’s. All direction set methods consist of prescriptions for updating the set of directions as the method proceeds, attempting to come up with a set which either (i) includes some very good directions that will take us far along narrow valleys, or else (more subtly) (ii) includes some number of “non-interfering” directions with the special property that minimization along one is not “spoiled” by subsequent minimization along another, so that interminable cycling through the set of directions can be avoided