Mathematics Source Library
C & ASM

 Home Optimization Home Nonlinear Optimization Home One-Dimensional Optimization Home Rosenbrock's Success/Failure Routines Exhaustive Grid Search Three Point Equal Interval Search Golden Section Search Fibonacci Search Parabolic Extrapolation for Bracketing an Extremum Parabolic Interpolation Minimize Down the Line / Maximize Up the Line

## Exhaustive Grid Search

The exhaustive grid method partitions a closed and bounded interval into n subintervals with disjoint interiors and evaluates the function at each endpoint of the subintervals. The interval which consists of the union of the two subintervals which contain the extreme value is retained and the process is repeated. The process terminates either when the length of the interval of uncertainty is less than the preassigned tolerance if the magnitude of the midpoint of the interval of uncertainty is less than or equal to one or when when the relative length of the interval of uncertainty to the magnitude of its midpoint is less than the preassigned tolerance if the magnitude of the midpoint is greater than one.

### Function List

• void Min_Search_Exhaustive_Grid( double (*f)(double), double* a, double* fa, double* b, double* fb, int num_subintervals, double tolerance )

This routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local minimum of the user-supplied function f(x) by partitioning the interval into num_subintervals subintervals and evaluating the function at each endpoint. The two subintervals with the common endpoint at which the function is a minimum is retained. The process is terminated either when the length of the interval of uncertainty is less than the tolerance if the magnitude of the midpoint of the interval of uncertainty is less than or equal to one or when the when the relative length of the interval of uncertainty to the magnitude of its midpoint is less than the tolerance if the magnitude of the midpoint is greater than one. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local minimum, the function f evaluated at *a, *fa needs to be set, the function f evaluated at *b, *fb needs to be set, and the parameter, num_subintervals, should at least 3 or greater. The tolerance should be a positive number, but if it is nonpositive, it is set to
sqrt( DBL_EPSILON ) * fabs (*b - *a).

• void Max_Search_Exhaustive_Grid( double (*f)(double), double* a, double* fa, double* b, double* fb, int num_subintervals, double tolerance )

This routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local maximum of the user-supplied function f(x) by partitioning the interval into num_subintervals subintervals and evaluating the function at each endpoint. The two subintervals with the common endpoint at which the function is a maximum is retained. The process is terminated either when the length of the interval of uncertainty is less than the tolerance if the magnitude of the midpoint of the interval of uncertainty is less than or equal to one or when the when the relative length of the interval of uncertainty to the magnitude of its midpoint is less than the tolerance if the magnitude of the midpoint is greater than one. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local maximum, the function f evaluated at *a, *fa needs to be set, the function f evaluated at *b, *fb needs to be set, and the parameter, num_subintervals, should at least 3 or greater. The tolerance should be a positive number, but if it is nonpositive, it is set to
sqrt( DBL_EPSILON ) * fabs (*b - *a).

• void Min_Line_Search_Exhaustive_Grid( double (*f)(double *),double* base, double* direction, double* x, int n, double* a, double* b, double* fa, double* fb, int num_subintervals, double tolerance )

Given the user-supplied real-valued function f of a vector and the line segment base - λ direction where a ≤ λ ≤ b this routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local minimum g(λ) = f(base - λ direction) by partitioning the interval [*a,*b] into num_subintervals subintervals and evaluating the function at each endpoint of the subintervals. The two subintervals with the common endpoint at which the function is a minimum is retained. The process is repeated until the length of the retained interval is less than or equal to tolerance. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local minimum; the parameter, num_subintervals, should at least 3 or greater; fa is set to the value of f() at the lower endpoint; fb is set to the value of f() at the upper endpoint; and the parameter x is working storage and should be dimensioned at least n in the calling routine.

• void Max_Line_Search_Exhaustive_Grid( double (*f)(double *),double* base, double* direction, double* x, int n, double* a, double* b, double* fa, double* fb, int num_subintervals, double tolerance )

Given the user-supplied real-valued function f of a vector and the line segment base + λ direction where a ≤ λ ≤ b this routine attempts to shorten the interval [*a,*b] which brackets a local maximum g(λ) = f(base + λ direction) by partitioning the interval [*a,*b] into num_subintervals subintervals and evaluating the function at each endpoint of the subintervals. The two subintervals with the common endpoint at which the function is a maximum is retained. The process is repeated until the length of the retained interval is less than or equal to tolerance. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local maximum; the parameter, num_subintervals, should at least 3 or greater; fa is set to the value of f() at the lower endpoint; fb is set to the value of f() at the upper endpoint; and the parameter x is working storage and should be dimensioned at least n in the calling routine.