10.5 Direction Set(Powell's)Methods in Multidimensions 415 In the approximation of(10.5.1),the gradient of f is easily calculated as Vf=A·x-b (10.53) (This implies that the gradient will vanish-the function will be at an extremum- at a value of x obtained by solving A.x=b.This idea we will return to in 810.7!) How does the gradient Vf change as we move along some direction?Evidently 6(7f)=A·(6x) (10.5.4) Suppose that we have moved along some direction u to a minimum and now propose to move along some new direction v.The condition that motion along v not spoil our minimization along u is just that the gradient stay perpendicular to u,i.e., that the change in the gradient be perpendicular to u.By equation(10.5.4)this is just 0=u·6(7f)=u·A·v (10.5.5) When (10.5.5)holds for two vectors u and v,they are said to be conjugate. 2 When the relation holds pairwise for all members of a set of vectors,they are said to be a conjugate set.If you do successive line minimization of a function along a conjugate set of directions,then you don't need to redo any of those directions (unless,of course,you spoil things by minimizing along a direction that they are not conjugate to). 县气%∽ 9 A triumph for a direction set method is to come up with a set of N linearly independent,mutually conjugate directions.Then,one pass of N line minimizations OF SCIENTIFIC will put it exactly at the minimum of a quadratic form like (10.5.1).For functions f that are not exactly quadratic forms,it won't be exactly at the minimum;but 61 repeated cycles of N line minimizations will in due course converge quadratically to the minimum Powell's Quadratically Convergent Method Powell first discovered a direction set method that does produce N mutually Numerica 10621 conjugate directions.Here is how it goes:Initialize the set of directions u;to the basis vectors, 431 Recipes ui=ei i=1,...,N (10.5.6) (outside Now repeat the following sequence of steps("basic procedure")until your function North stops decreasing: Save your starting position as Po. For i=1,...,N,move Pi-1 to the minimum along direction ui and call this point Pi. ·Fori=1,,N-1,set ui←ui+1 ·Set un-Pw-Po. Move Pn to the minimum along direction un and call this point Po10.5 Direction Set (Powell’s) Methods in Multidimensions 415 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). In the approximation of (10.5.1), the gradient of f is easily calculated as ∇f = A · x − b (10.5.3) (This implies that the gradient will vanish — the function will be at an extremum — at a value of x obtained by solving A · x = b. This idea we will return to in §10.7!) How does the gradient ∇f change as we move along some direction? Evidently δ(∇f) = A · (δx) (10.5.4) Suppose that we have moved along some direction u to a minimum and now propose to move along some new direction v. The condition that motion along v not spoil our minimization along u is just that the gradient stay perpendicular to u, i.e., that the change in the gradient be perpendicular to u. By equation (10.5.4) this is just 0 = u · δ(∇f) = u · A · v (10.5.5) When (10.5.5) holds for two vectors u and v, they are said to be conjugate. When the relation holds pairwise for all members of a set of vectors, they are said to be a conjugate set. If you do successive line minimization of a function along a conjugate set of directions, then you don’t need to redo any of those directions (unless, of course, you spoil things by minimizing along a direction that they are not conjugate to). A triumph for a direction set method is to come up with a set of N linearly independent, mutually conjugate directions. Then, one pass of N line minimizations will put it exactly at the minimum of a quadratic form like (10.5.1). For functions f that are not exactly quadratic forms, it won’t be exactly at the minimum; but repeated cycles of N line minimizations will in due course converge quadratically to the minimum. Powell’s Quadratically Convergent Method Powell first discovered a direction set method that does produce N mutually conjugate directions. Here is how it goes: Initialize the set of directions ui to the basis vectors, ui = ei i = 1,...,N (10.5.6) Now repeat the following sequence of steps (“basic procedure”) until your function stops decreasing: • Save your starting position as P0. • For i = 1,...,N, move Pi−1 to the minimum along direction ui and call this point Pi. • For i = 1,...,N − 1, set ui ← ui+1. • Set uN ← PN − P0. • Move PN to the minimum along direction uN and call this point P0