## Steepest Descent

The method of (optimal) steepest-descent is used to find the location of a local minimum of a real-valued function of*n*real-variables. The method is primarily useful when the current estimate of the location of a local minimum is far from the location of a local minimum. Near a local minimum, it is better to use either the Newton-Raphson, damped Newton-Raphson, or the quasi-Newtonian methods, Fletcher-Powell-Davidon or Broyden-Fletcher-Shanno, or the conjugate gradient methods, Fletcher-Reeves or Fletcher-Reeves-Polak-Ribiere.

The (optimal) steepest-descent method proceeds as follows:

**Initialization:**Choose an initial estimate,, for the location of a local minimum of the predetermined function**x**_{0}*f : R*.^{n}→ R**Determine the Search Direction**Calculate the gradient of*d*:*f*evaluated at,, the search direction is then opposite to that of the gradient,**x**_{0}= -**d****grad***f (***x**)._{0}**Check if**If*d*vanishes:, then the point**d**=**0**is a local extremum.**x**_{0}**The line search:**Find the minimum of*f (*along the line**x**)=**x**+**x**_{0}*t*, for**d***t*> 0. Let*t*be the value of_{0}*t*for which*f (*is a minimum.**x**+ t_{0})**d****Check if the stopping criterion is satisfied:**The conventional stopping rules are: (1) Stop if*f (*-**x**)_{0}*f (*< ε for some preassigned ε, (2) Stop if ||**x**+ t_{0}_{0}**d**)*t*|| < ε for either the_{0}**d***max*-norm or the*l*-norm, and/or (3) Stop if ||_{2}|| < ε for either the**d***max*-norm or the*l*-norm,_{2}**Update the estimate for the location of a local minimum:**Replace the initial estimate,**x**, with_{0}**x**+_{0}*t*_{0}and repeat the process.**d**

### Function List

- int Steepest_Descent( double (*f)(double *), void (*df)(double *, double *), int (*stopping_rule)(double*, double, double*, double, double*, int, int), double a[], double *fa, double *dfa, double cutoff, double cutoff_scale_factor, double tolerance, int n )

This routine uses the method of steepest descent to approximately locate a local minimum of the user-supplied function*f(*. The procedure starts at**x**)=**x***a*with the value of*f*at*a*stored in*fa*. 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*cutoff*,*cutoff_scale_factor*and*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 initial point, the function evaluated at the initial point**x**_{0}*f(*, the new estimate**x**)_{0}, the function evaluated at the new estimate**x***f(*, the gradient of the function evaluated at the new point**x**)*dfa*, the total number of iterations performed, and*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, return values -1, -2, -3, -4, and -5 are intrinsic return values used by the steepest-descent routine. Upon exiting the function returns either the return of the user-supplied*stopping-rule*, a 0 indicates success in the case where the gradient of the function evaluated other than at the initial starting point vanishes, -1 indicates that during the line search for a minimum the three points were collinear, -2 indicates that during the line search the parabolic interpolation phase produced a local maximum, -3 indicates that during the line search the initial three points during the parabolic interpolation phase failed to satisfy the condition for a local minimum to exist, -4 indicates that there was not enough dynamic heap memory, -5 indicates that the gradient of the function evaluated at the initial point vanishes which implies that the initial point may be a local maximum, a local minimum, or a local saddle point. The value*a*is set to the current estimate and the argument*fa*is set to the value of the function evaluated there.

*C* Source Code

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