Nash - Compact Numerical Methods for Computers (523163), страница 41
Текст из файла (страница 41)
For these reasons, Newton’s method does not recommend itself for mostproblems.Suppose now that a method could be found to approximate H -1 directly fromthe first derivative information available at each step of the iteration defined by(15.2). This would save a great deal of work in computing both the derivativematrix H and its inverse. This is precisely the role of the matrix B in generating theconjugate search directions of the variable metric family of algorithms, and hasled to their being known also as quasi-Newton methods.15.2. VARIABLE METRIC ALGORITHMSVariable metric algorithms, also called quasi-Newton or matrix iteration algorithms, have proved to be the most effective class of general-purpose methodsfor solving unconstrained minimisation problems.
Their development is continuing so rapidly, however, that the vast array of possibilities open to a programmerwishing to implement such a method is daunting. Here an attempt will be made tooutline the underlying structure on which such methods are based. The nextsection will describe one set of choices of strategy.All the variable metric methods seek to minimise the function S( b) of n188Compact numerical methods for computersparameters by means of a sequence of stepsb ' =b - k Bg(15.2)where g is the gradient of S. The definition of an algorithm of this type consists inspecifying (a) how the matrix B is computed, and (b) how k is chosen.
The secondof these choices is the linear search problem of §13.2. In practice the algorithmsuggested there is unnecessarily rigorous and a simpler search will be used. Therest of this section will be devoted to the task of deciding appropriate conditionson the matrix B.Firstly, when it works, Newton’s method generally converges very rapidly. Thusit would seem desirable that B tend in some way towards the inverse Hessianmatrix H-l. However, the computational requirement in Newton’s method forsecond partial derivatives and for the solution of linear-equation systems at eachiteration must be avoided.Secondly, B should be positive definite, not only to avoid the possibility that thealgorithm will ‘get stuck’ because Bg lacks components necessary to reduce thefunction because they are in the null space of B but also to permit the algorithmto exhibit quadratic termination, that is, to minimise a quadratic form in at most nsteps (15.2).
A quadratic form(15.11)has a unique minimum if H is positive definite. Note that H can always be madesymmetric, and will be presumed so here. The merits of quadratic termination andpositive definiteness are still being debated (see, for instance, Broyden 1972,p 94). Also, a function with a saddle point or ridge has a Hessian which is notalways positive definite. Nevertheless, the discussion here will be confined tomethods which generate positive definite iteration matrices.If n linearly independent directions tj , j=1, 2, .
. . , n, exist for whichBHt j =t j(15.12)thenBH =l norB= H - l .(15.13)The search directions t j are sought conjugate to H, leading in an implicit fashionto the expansion(15.14)Since B is to be developed as a sequence of matrices B ( m ), the condition (15.12)will be statedB( m) H tj = t j(15.15)Thus we haveB ( n +1)= H -1.(15.16)For a quadratic form, the change in the gradient at b j, that isg j =Hbj - c(15.17)Descent to a minimum I: variable metric algorithms189is given byyj = gj + l - g j =H(b j + l -b j )=k jHt j(15.18)since the elements of H are constant in this case. From this it follows that (15.15)becomes(15.19)B( m ) yj =k jtj .Assuming (15.15) is correct for j<m, a new stept m =B( m ) g m(15.20)is required to be conjugate to all previous directions tj , i.e.f o r j<m.(15.21)But from (15.18), (15.19) and (15.20) we obtain(15.22)Suppose now that the linear searches at each step have been performedaccurately.
Then the directions(15.23)t1, t 2, . . . , t m- ldefine a hyperplane on which the quadratic form has been minimised. Thus g m isorthogonal to tj , j<m, and (15.21) is satisfied, so that the new direction t m isconjugate to the previous ones.In order that B( m +l) satisfies the above theory so that the process can continue,the update C inB ( m + 1 ) =B ( m ) +C(15.24)must satisfy (15.19), that isB( m + l ) y m=k mt m(15.25)Cy m =k mt m -B( m ) y m(15.26)orandB ( m + l )yj =k j t jf o r j<m(15.27)orCy j =k jt j -B( m ) y j= k jt j -k jt j =0.(15.28)In establishing (15.26) and (15.28), equation (15.19) has been applied for B ( m ) .There are thus m conditions on the order-n matrix C. This degree of choice in Chas in part been responsible for the large literature on variable metric methods.The essence of the variable metric methods, i.e.
that information regardingthe Hessian has been drawn from first derivative computations only is somewhathidden in the above development. Of course, differences could have been used togenerate an approximate Hessian from (n+1) vectors of first derivatives, but a190Compact numerical methods for computersNewton method based on such a matrix would still require the solution of a linearsystem of equations at each step. The variable metric methods generate anapproximate inverse Hessian as they proceed, requiring only one evaluation of thefirst derivatives per step and, moreover, reduce the function value at each of thesesteps.15.3.
A CHOICE OF STRATEGIESIn order to specify a particular variable metric algorithm it is now necessary tochoose a matrix-updating formula and a linear search procedure. One set ofchoices resulting in a compact algorithm is that of Fletcher (1970). Here this willbe simplified somewhat and some specific details made clear.
First, Fletcherattempts to avoid an inverse interpolation in performing the linear search. Hesuggests an ‘acceptable point’ search procedure which takes the first point in somegenerated sequence which satisfies some acceptance criterion. Suppose that thestep taken ist = b ' -b = -k B g(15.29)with k=1 initially. The decrease in the function(15.30)will be approximated for small steps t by the first term in the Taylor series for Salong t from b, that is, by t Tg.
This is negative when t is a ‘downhill’ direction. Itis not desirable that ∆S be very different in magnitude from t T g since this wouldimply that the local approximation of the function by a quadratic form is grosslyin error. By choosing k=1, w, w2, . . . , for 0<w<1 successively, it is alwayspossible to produce a t such that0<tolerance< ∆S/tTgfor tolerance << 1(15.31)unless the minimum has been found.
This presumest Tg< 0(15.32)to ensure a ‘downhill’ direction. In any practical program a test of the condition(15.32) is advisable before proceeding with any search along t. Fletcher recommends the values w=0·1, tolerance=0·0001. However, if the point is notacceptable, he uses a cubic inverse interpolation to reduce k, with the proviso that0·1k be the smallest value permitted to generate the next step in the search.The author retains tolerance=0·0001, but uses w=0·2 with no interpolationprocedure. For a study of acceptable point-interpolation procedures in minimisation algorithms see Sargent and Sebastian (1972).An updating formula which has received several favourable reports is that ofBroyden (1970a, b), Fletcher (1970) and Shanno (1970). This employs the updateC=d 2 tt T - [t(By) T + (By)t T ] /d 1where y is the gradient differencey =g( b' ) -g( b)(15.33)(15.34)Descent to a minimum I: variable metric algorithms191and the coefficients d1 and d 2 are given byd1 =t T y(15.35)d 2 = ( 1 +y T By/d l )d 1 .(15.36)andThere are several ways in which the update can be computed and added into B.
Inpractice these may give significantly different convergence patterns due to themanner in which digit cancellation may occur. However, the author has not beenable to make any definite conclusion as to which of the few ways he has tried issuperior overall. The detailed description in the next section uses a simpleform for convenience of implementation. The properties of the BroydenFletcher-Shanno update will not be discussed further in this work.In order to start the algorithm, some initial matrix B must be supplied.
If itwere easy to compute the Hessian H for the starting parameters b , H-1 wouldbe the matrix of choice. For general application, however, B=1n (15.37) is asimpler choice and has the advantage that it generates the steepest descentdirection in equation (15.29). I have found it useful on a machine having shortmantissa arithmetic to apply the final convergence test on the steepest descentFIGURE 15.1. Illustration of the test at step 14 of algorithm 21. Aniteration of the variable metric algorithm 21 consists of a linear searchalong direction t using the step parameter k.
At a given point along thesearch line g T t gives the slope of the function with respect to the steplength k. If the search finds kA, then the update can proceed since thisslope is increased (made less negative) as we would expect if minimisinga quadratic function. If, however, k B is found, the slope is decreased,and because such behaviour is not consistent with the assumption thatthe function is approximately represented by a quadratic form, theupdate cannot be performed and we restart algorithm 21 with asteepest descent step from the point defined by kB .192Compact numerical methods for computersdirection to ensure that rounding errors in updating B and forming t via (15.29)have not accidentally given a direction in which the function S cannot bereduced.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
