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

## Rosenbrock's One-Dimensional Optimization Search

Rosenbrock's success / failure search routines are procedures to search for an upper and lower bound which bracket a local minimum or a local maximum.

Assume that one wishes to find a local minimum of a given real-valued function of a real variable f : RR. Given a starting point x, an initial step size h, a forward scale factor
a ≥ 1.0, a positive backward scale factor 0 < b < 1.0, a tolerance ε and a run-time loop protection constant N, Rosenbeck's success/failure procedure searches for a relative minimum starting at the initial points x and x + h and evaluating the function f at x and x + h. If ( f ( x + h ) < f ( x ) ) the step is called a success, the base point x is replaced by x + h and the step size is increased to a h. If ( f ( x + h ) ≥ f ( x ) ) the step is called a failure, the base point x is replaced by x + h, the step size is decreased to b h and the step direction is reversed. The minimum is bracketed when two failures occur.
The procedure terminates if | x + h/2 | ≤ 1 when | h | < ε and if | x + h/2 | > 1 when the relative length of the interval of uncertainty to the magnitude of its midpoint is less than the preassigned tolerance ε. If the procedure fails to find both an upper bound and a lower bound within N iterations, the procedure unsuccessfully is terminated.

The procedure for finding an upper and lower bound which bracket a local maximum is analogous to that given for finding an upper and lower bound which bracket a local minimum.

### Function List

• int Min_Search_Success_Failure( double (*f)(double), double* base_point, double* step_size, double *f0, double *f1, int max_tries_to_bracket, double forward_scale, double backward_scale, double tolerance )

This routine attempts to bracket a local minimum of the user-supplied function f(x) within max_tries_to_bracket iterations starting at x = *base_point with an initial step size step_size using forward_scale for the forward scale factor and backward_scale as the backward scale factor. If a local minimum is bracketed, then the procedure continues until the length of the bracket interval is less than or equal to tolerance. If the procedure is successful, the return value is 0, *base_point is the value of the left-most endpoint of the bracket interval and *step_size is the length of the bracket interval, i.e. the right-most endpoint is *base_point + *step_size, *f0 is the value of f(x) evaluated at the left-most endpoint of the bracket interval and *f1 is the value of f(x) evaluated at the right-most endpoint of the bracket interval. If the procedure is unsuccessful, i.e. it could not bracket a local minimum within max_tries_to_bracket iterations the function returns -1.

The forward scale factor should be greater than or equal to 1.0 and the backward scale factor should be a positive number strictly less than 1.0.

• int Max_Search_Success_Failure( double (*f)(double), double* base_point, double* step_size, double *f0, double *f1, int max_tries_to_bracket, double forward_scale, double backward_scale, double tolerance )

This routine attempts to bracket a local maximum of the user-supplied function f(x) within max_tries_to_bracket iterations starting at x = *base_point with an initial step size step_size using forward_scale for the forward scale factor and backward_scale as the backward scale factor. If a local maximum is bracketed, then the procedure continues until the length of the bracket interval is less than or equal to tolerance. If the procedure is successful, the return value is 0, *base_point is the value of the left-most endpoint of the bracket interval and *step_size is the length of the bracket interval, i.e. the right-most endpoint is *base_point + *step_size, *f0 is the value of f(x) evaluated at the left-most endpoint of the bracket interval and *f1 is the value of f(x) evaluated at the right-most endpoint of the bracket interval. If the procedure is unsuccessful, i.e. it could not bracket a local maximum within max_tries_to_bracket iterations the function returns -1.

The forward scale factor should be greater than or equal to 1.0 and the backward scale factor should be a positive number strictly less than 1.0.

• int Max_Line_Search_Success_Failure( double (*f)(double*), double* base, double* direction, double* x, int n, double* base_lambda, double* step_size, double *f0, double *f1, int max_tries_to_bracket, double forward_scale, double backward_scale, double tolerance )

This routine attempts to bracket a local maximum of the user-supplied real-valued function of a vector f(x) along the line base + λ * direction within max_tries_to_bracket iterations starting at x = base + lambda_base * direction with an initial lambda step size step_size using forward_scale for the forward scale factor and backward_scale as the backward scale factor. If a local maximum is bracketed, then the procedure continues until the length of the bracket interval is less than or equal to tolerance. If the procedure is successful, the return value is 0, *base_lambda is the value of the left-most endpoint of the bracket interval and *step_size is the length of the bracket interval, i.e. the right-most endpoint is *base_lambda + *step_size, *f0 is the value of f(x) evaluated at the left-most endpoint of the bracket interval and *f1 is the value of f(x) evaluated at the right-most endpoint of the bracket interval. If the procedure is unsuccessful, i.e. it could not bracket a local maximum within max_tries_to_bracket iterations the function returns -1.

The forward scale factor should be greater than or equal to 1.0 and the backward scale factor should be a positive number strictly less than 1.0. The argument x is working storage and should be dimensioned at least n in calling routine.

• int Min_Line_Search_Success_Failure( double (*f)(double*), double* base, double* direction, double* x, int n, double* base_lambda, double* step_size, double *f0, double *f1, int max_tries_to_bracket, double forward_scale, double backward_scale, double tolerance )

This routine attempts to bracket a local minimum of the user-supplied real-valued function of a vector f(x) along the line base - λ * direction within max_tries_to_bracket iterations starting at x = base - lambda_base * direction with an initial lambda step size step_size using forward_scale for the forward scale factor and backward_scale as the backward scale factor. If a local minimum is bracketed, then the procedure continues until the length of the bracket interval is less than or equal to tolerance. If the procedure is successful, the return value is 0, *base_lambda is the value of the left-most endpoint of the bracket interval and *step_size is the length of the bracket interval, i.e. the right-most endpoint is *base_lambda + *step_size, *f0 is the value of f(x) evaluated at the left-most endpoint of the bracket interval and *f1 is the value of f(x) evaluated at the right-most endpoint of the bracket interval. If the procedure is unsuccessful, i.e. it could not bracket a local minimum within max_tries_to_bracket iterations the function returns -1.

The forward scale factor should be greater than or equal to 1.0 and the backward scale factor should be a positive number strictly less than 1.0. The argument x is working storage and should be dimensioned at least n in calling routine.