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  v2v v1, and v1  a +c(b- a). If f(v1) ≥ f(v2), the minimizing value is in (v1, b). In this case, v1, v1  v2, and v2  ‑ c( 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 fis 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 = "#".