10.7 Variable Metric Methods in Multidimensions 427 using the true Hessian.We can understand this paradoxical result by considering the descent directions of f at xi.These are the directions p along which f decreases: Vf.p<0.For the Newton direction(10.7.4)to be a descent direction,we must have 7f(x:)·(x-x)=-(x-x)·A·(x-x:)<0 (10.7.5) which is true if A is positive definite.In general,far from a minimum,we have no guarantee that the Hessian is positive definite.Taking the actual Newton step with the real Hessian can move us to points where the function is increasing in value. The idea behind quasi-Newton methods is to start with a positive definite,symmetric 81 approximation to A (usually the unit matrix)and build up the approximating Hi's in such a way that the matrix H;remains positive definite and symmetric.Far from the minimum,this guarantees that we always move in a downhill direction.Close to the minimum,the updating formula approaches the true Hessian and we enjoy the quadratic convergence of Newton's method. When we are not close enough to the minimum,taking the full Newton step p even with a positive definite A need not decrease the function;we may move RECIPES too far for the quadratic approximation to be valid.All we are guaranteed is that initially f decreases as we move in the Newton direction.Once again we can use 9 the backtracking strategy described in 89.7 to choose a step along the direction of the Newton step p,but not necessarily all the way. We won't rigorously derive the DFP algorithm for taking Hi into Hi+1;you can consult [3]for clear derivations.Following Brodlie (in [2)),we will give the following heuristic motivation of the procedure. Subtracting equation(10.7.4)at x from that same equation at x:gives x+1-x=A-1.(7f+1-7f) (10.7.6) where Vf;=Vf(xj).Having made the step from xi to x:+1,we might reasonably want to require that the new approximation Hi+satisfy (10.7.6)as if it were actually A,that is, Numerica 10621 xi+1-xi=H+1·(7f+1-7f) (10.7.7) 43126 We might also imagine that the updating formula should be of the form H= H;+correction. What"objects"are around out of which to construct a correction term?Most notable are the two vectors x:+1-xi and Vfi+1-Vfi;and there is also Hi. There are not infinitely many natural ways of making a matrix out of these objects, especially if(10.7.7)must hold!One such way,the DFP updating formula,is H+1=H+ (K+1-x)图(x+1-x) (K+1-x)·(Vf+1-7f) -4·(f+1-f]®画，·(Vf+1-Vf】 (10.7.8) (7fi+1-7fi):H·(Tf+1-7fi) where denotes the "outer"or "direct"product of two vectors,a matrix:The ij component ofuv is uivj.(You might want to verify that 10.7.8 does satisfy 10.7.7.)10.7 Variable Metric Methods in Multidimensions 427 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). using the true Hessian. We can understand this paradoxical result by considering the descent directions of f at xi. These are the directions p along which f decreases: ∇f ·p < 0. For the Newton direction (10.7.4) to be a descent direction, we must have ∇f(xi) · (x − xi) = −(x − xi) · A · (x − xi) < 0 (10.7.5) which is true if A is positive definite. In general, far from a minimum, we have no guarantee that the Hessian is positive definite. Taking the actual Newton step with the real Hessian can move us to points where the function is increasing in value. The idea behind quasi-Newton methods is to start with a positive definite, symmetric approximation to A (usually the unit matrix) and build up the approximating H i’s in such a way that the matrix Hi remains positive definite and symmetric. Far from the minimum, this guarantees that we always move in a downhill direction. Close to the minimum, the updating formula approaches the true Hessian and we enjoy the quadratic convergence of Newton’s method. When we are not close enough to the minimum, taking the full Newton step p even with a positive definite A need not decrease the function; we may move too far for the quadratic approximation to be valid. All we are guaranteed is that initially f decreases as we move in the Newton direction. Once again we can use the backtracking strategy described in §9.7 to choose a step along the direction of the Newton step p, but not necessarily all the way. We won’t rigorously derive the DFP algorithm for taking Hi into Hi+1; you can consult [3] for clear derivations. Following Brodlie (in [2]), we will give the following heuristic motivation of the procedure. Subtracting equation (10.7.4) at xi+1 from that same equation at xi gives xi+1 − xi = A−1 · (∇fi+1 − ∇fi) (10.7.6) where ∇fj ≡ ∇f(xj ). Having made the step from xi to xi+1, we might reasonably want to require that the new approximation Hi+1 satisfy (10.7.6) as if it were actually A−1, that is, xi+1 − xi = Hi+1 · (∇fi+1 − ∇fi) (10.7.7) We might also imagine that the updating formula should be of the form H i+1 = Hi + correction. What “objects” are around out of which to construct a correction term? Most notable are the two vectors xi+1 − xi and ∇fi+1 − ∇fi; and there is also Hi. There are not infinitely many natural ways of making a matrix out of these objects, especially if (10.7.7) must hold! One such way, the DFP updating formula, is Hi+1 = Hi + (xi+1 − xi) ⊗ (xi+1 − xi) (xi+1 − xi) · (∇fi+1 − ∇fi) − [Hi · (∇fi+1 − ∇fi)] ⊗ [Hi · (∇fi+1 − ∇fi)] (∇fi+1 − ∇fi) · Hi · (∇fi+1 − ∇fi) (10.7.8) where ⊗ denotes the “outer” or “direct” product of two vectors, a matrix: The ij component of u⊗v is uivj . (You might want to verify that 10.7.8 does satisfy 10.7.7.)