## Broyden-Fletcher-Shanno

Given a function*:*

**f***R*→

^{n}*R*the Broyden-Fletcher-Shanno method belongs to a group of methods variously called quasi-Newton methods, matrix updating methods, or variable metric methods which attempt to locate a local minimum of

*f*.

Given a point

*∈*

**x**_{0}*R*, Newton-Raphson's method generates the search direction

^{n}*H( f,*, where

**x**)_{0}^{-1}**grad**f (**x**)_{0}*H( f,*is the Hessian of

**x**)_{0}*f*at

*. The quasi-Newton methods avoid the need for calculating the Hessian directly and then inverting it by successively estimating the inverse of the Hessian using only the gradient,*

**x**_{0}*.*

**grad**f (**x**)_{0}In general the quasi-Newton methods proceed as follows:

**Initialization:**Choose a point,, which approximates the location of a local minimum. Set**x**_{0}=**H**_{0}, the identity matrix, and calculate**I**=**d**_{0}**H**_{0}.**grad**f (**x**)_{0}**Determine the Displacement Vector**Given*Δ x*:_{k}and**x**_{k}, let**d**_{k}*λ*be the value of_{k}*λ*which minimizes*f (*. Then set**x**- λ_{k}**d**)_{k}*Δ*=**x**_{k}*λ*_{k}.**d**_{k}**Update the estimate for the location of a local minimum:**Set=**x**_{k+1}+**x**_{k}*Δ*.**x**_{k}**Check if the stopping criterion is satisfied:**The conventional stopping rules are: (1) Stop if |||| < ε for either the**g***max*-norm or the*l*-norm, and/or (2) Stop if_{2}

|||| < ε for either the**d***max*-norm or the*l*-norm. If the stopping criterion is satisfied, then halt._{2}**Calculate New Search Direction:**Define*Δ*=**g**_{k}-**grad**f (**x**)_{k+1}, update**grad**f (**x**)_{k}(see below) and finally calculate**H**_{k+1}=**d**_{k+1}**H**_{k+1}. Go to step 2.**grad**f (**x**)_{k+1}

*vary. For the Broyden-Fletcher-Shanno method the estimate for*

**H**_{k}*is*

**H**_{k+1}*=*

**H**_{k+1}*+ Δ*

**H**_{k}*· (1 +*

**x**Δ_{k}**x**/ Δ^{T}_{k}**x**Δ^{T}_{k}**g**_{k}*Δ*/

**g**Δ^{T}_{k}H_{k}**g**_{k}*Δ*)

**x**Δ^{T}_{k}**g**_{k}- (

**H**Δ_{k}**g**_{k}*Δ*+ Δ

**x**^{T}_{k}

**x**_{k}*Δ*

**g**^{T}_{k}**H**) / (

_{k}*Δ*)

**x**Δ^{T}_{k}**g**_{k}### Function List

- int Broyden_Fletcher_Shanno( double (*f)(double *), void (*df)(double*, double*), int (*Stopping_Rule)(double*, double*, int, int), double *a, double *dfa, double line_search_cutoff, double line_search_cutoff_scale_factor, double line_search_tolerance, int n )

This routine uses the Broyden-Fletcher-Shanno method to approximately locate a local minimum of the user-supplied function*f(*. The procedure starts at**x**)=**x***a*. The gradient is calculated using the user-supplied function*df(*where**x**,*dfa*)*dfa*is the*n*-dimensional array whose*i*component^{th}*dfa[i]*is ∂f(**x**)/∂x_{i}. The parameters*line_search_cutoff*,*line_search_cutoff_scale_factor*and*line_search_tolerance*are used for minimizing the function,*f (*down the line in a direction opposite to that given by the gradient. See Minimize_Down_the_Line for a discription of these parameters. The arguments to the user-supplied**x**),*stopping_rule*are: the displacement vectorbetween two successive iteratates, the gradient of the function evaluated at the new estimate**d***f(*, the total number of iterations performed, and**x**)*n*the dimension of. The user-supplied**x***stopping_rule*should return a non-zero, either positive or negative, integer to halt the procedure and return zero to continue iterating, the return value -1 is the only intrinsic return value used by the Broyden-Fletcher-Shanno routine. Upon exiting the function returns either the return of the user-supplied*stopping-rule*or a -1 indicating that there was not enough dynamic heap memory. The value*a*is set to the current estimate.

*C* Source Code

- The file, broyden_fletcher_shanno.c, contains the version of Broyden_Fletcher_Shanno( ) written in
*C*.