IMSL C Math Library
min_uncon_golden
Finds the minimum point of a nonsmooth function of a single variable using the golden section search method.
Synopsis
#include <imsl.h>
float imsl_f_min_uncon_golden (float fcn(), float a, float b, ..., 0)
The type double function is imsl_d_min_uncon_golden.
Required Arguments
float fcn (float x) (Input)
User-supplied function, f(x), to be minimized.
float x (Input)
The point at which the function is evaluated.
Return Value
The computed function value at the point x.
float a (Input)
The lower endpoint of the interval in which the minimum of f is to be located.
float b (Input)
The upper endpoint of the interval in which the minimum of f is to be located.
Return Value
The approximate minimum point of the function f on the original interval [a,b]. If no value can be computed, NaN is returned.
Synopsis with Optional Arguments
#include <imsl.h>
float imsl_f_min_uncon_golden (float fcn(), float a, float b,
IMSL_TOLERANCE, float tol,
IMSL_FCN_W_DATA, float fcn(), void *data,
IMSL_LOWER_ENDPOINT, float *lower,
IMSL_UPPER_ENDPOINT, float *upper,
0)
Optional Arguments
IMSL_TOLERANCE, float tol (Input)
The allowable length of the final subinterval containing the minimum point.
Default: tol = , where ɛ is the machine precision.
IMSL_FCN_W_DATA, float fcn (float x, void *data), void *data (Input)
float fcn (float x, void *data)
User-supplied function, f(x), to be minimized, which also accepts a pointer to data that is supplied by the user. See Passing Data to User-Supplied Functions in the introduction to this manual for more details.
Arguments
float x (Input)
The point at which the function is evaluated.
void *data (Input)
A pointer to the data to be passed to the user-supplied function.
Return Value
The computed function value at the point x.
void data (Input)
A pointer to the data to be passed to the user-supplied function.
IMSL_LOWER_ENDPOINT, float *lower (Output)
The lower endpoint of the interval in which the minimum of f is located.
IMSL_UPPER_ENDPOINT, float *upper (Output)
The upper endpoint of the interval in which the minimum of f is located.
Description
The function imsl_f_min_uncon_golden uses the golden section search technique to compute to the desired accuracy the independent variable value that minimizes a function of one independent variable, where a known finite interval contains the minimum and where the function is unimodal in the same known finite interval.
Let =tol. The number of iterations required to compute the minimizing value to accuracy is the greatest integer less than or equal to
where a and b define the interval and
The first two test points are v1 and v2 that are defined as
v1 =a +c(b - a), and v2 =b - c(b - a)
If f(v1) < f(v2), then the minimizing value is in the interval (a, v2). In this case, b ← v2, v2 ← v1, and v1 ← a +c(b - a). If f(v1) ≥ f(v2), the minimizing value is in (v1, b). In this case, a ←v1, v1 ← v2, and v2 ← b ‑ c(b − a).
The algorithm continues in an analogous manner where only one new test point is computed at each step. This process continues until the desired accuracy is achieved. The point, xmin, producing the minimum value for the current iteration is returned.
Mathematically, the algorithm always produces the minimizing value to the desired accuracy, however, numerical problems may be encountered. If f is too flat in part of the region of interest, the function may appear to be constant to the computer in that region. The user may rectify the problem by relaxing the requirement on , modifying (scaling, etc.) the form of f or executing the program in a higher precision.
Remarks
1. On exit from imsl_f_min_uncon_golden without any error messages, the following conditions hold:
(upper-lower) ≤tol
lower ≤xmin and xmin ≤upper
f(xmin) ≤f(lower) and f(xmin) ≤f(upper)
2. On exit from imsl_f_min_uncon_golden with IMSL_NOT_UNIMODAL error, the following conditions hold:
lower ≤xmin and xmin ≤upper
f(xmin) ≥f(lower) and f(xmin) ≥f(upper) (only one equality can hold)
Further analysis of the function f is necessary in order to determine whether it is not unimodal in the mathematical sense or whether it appears to be not unimodal to the routine due to rounding errors, in which case the lower, upper, and xmin returned may be acceptable.
Example
A minimum point of 3x2 - 2x +4 is found.
 
#include <imsl.h>
#include <stdio.h>
 
float fcn(float);
 
int main () {
float a = 0.0e0, b = 5.0e0, tol = 1.0e-3, lower,
upper, xmin, fx;
xmin = imsl_f_min_uncon_golden (fcn, a, b,
IMSL_TOLERANCE, tol,
IMSL_LOWER_ENDPOINT, &lower,
IMSL_UPPER_ENDPOINT, &upper,
0);
fx = fcn(xmin);
printf ("The minimum is at: %8.3f\n", xmin);
printf ("The function value is: %8.3f\n", fx);
printf ("The final interval is: (%8.3f, %8.3f)\n",
lower, upper);
}
 
float fcn(float x) {
return 3.0e0*x*x - 2.0e0*x + 4.0e0;
}
Output
 
The minimum is at: 0.333
The function value is: 3.667
The final interval is: ( 0.333, 0.334)
Warning Errors
IMSL_TOL_TOO_SMALL
tol is too small to be satisfied..
Fatal Errors
IMSL_NOT_UNIMODAL
Due to rounding errors, the function does not appear to be unimodal.
IMSL_STOP_USER_FCN
Request from user supplied function to stop algorithm. User flag = "#".