min_uncon
Find the minimum point of a smooth function f(x) of a single variable using only function evaluations.
Synopsis
#include <imsl.h>
float imsl_f_min_uncon (float fcn(), float a, float b, …, 0)
The type double function is imsl_d_min_uncon.
Required Arguments
float fcn(float x) (Input/Output)
User-supplied function to compute the value of the function to be minimized where x is the point at which the function is evaluated, and fcn is the computed function value at the point x.
float a (Input)
The lower endpoint of the interval in which the minimum point of fcn is to be located.
float b (Input)
The upper endpoint of the interval in which the minimum point of fcn is to be located.
Return Value
The point at which a minimum value of fcn is found. If no value can be computed, NaN is returned.
Synopsis with Optional Arguments
#include <imsl.h>
float imsl_f_min_uncon (float fcn(), float a, float b,
IMSL_XGUESS, float xguess,
IMSL_STEP, float step,
IMSL_ERR_ABS, float err_abs,
IMSL_MAX_FCN, int max_fcn,
IMSL_FCN_W_DATA, float fcn(), void *data,
0)
Optional Arguments
IMSL_XGUESS, float xguess (Input)
An initial guess of the minimum point of fcn.
Default: xguess = (a + b)/2
IMSL_STEP, float step (Input)
An order of magnitude estimate of the required change in x.
Default: step = 1.0
IMSL_ERR_ABS, float err_abs (Input)
The required absolute accuracy in the final value of x. On a normal return, there are points on either side of x within a distance err_abs at which fcn is no less than fcn at x.
Default: err_abs = 0.0001
IMSL_MAX_FCN, int max_fcn (Input)
Maximum number of function evaluations allowed.
Default: max_fcn = 1000
IMSL_FCN_W_DATA, float fcn(float x, void *data), void *data, (Input)
User supplied function to compute the value of the function to be minimized, which also accepts a pointer to data that is supplied by the user. data is a pointer to the data to be passed to the user-supplied function. See Passing Data to User-Supplied Functions in the introduction to this manual for more details.
Description
The function imsl_f_min_uncon uses a safeguarded quadratic interpolation method to find a minimum point of a univariate function. Both the code and the underlying algorithm are based on the subroutine ZXLSF written by M.J.D. Powell at the University of Cambridge.
The function imsl_f_min_uncon finds the least value of a univariate function, f, which is specified by the function fcn. Other required data are two points a and b that define an interval for finding a minimum point from an initial estimate of the solution, x0 where x0 = xguess. The algorithm begins the search by moving from x0 to x = x0 + s where s = step is an estimate of the required change in x and may be positive or negative. The first two function evaluations indicate the direction to the minimum point and the search strides out along this direction until a bracket on a minimum point is found or until x reaches one of the endpoints a or b. During this stage, the step length increases by a factor of between two and nine per function evaluation. The factor depends on the position of the minimum point that is predicted by quadratic interpolation of the three most recent function values.
When an interval containing a solution has been found, we have three points,
x1, x2, x3, with x1 < x2 < x3, f(x1) ≥ f(x2), and f(x2) ≤ f(x3).
There are three main rules in the technique for choosing the new x from these three points. They are (i) the estimate of the minimum point that is given by quadratic interpolation of the three function values, (ii) a tolerance parameter η, which depends on the closeness of f to a quadratic, and (iii) whether x2 is near the center of the range between x1 and x3 or is relatively close to an end of this range. In outline, the new value of x is as near as possible to the predicted minimum point, subject to being at least ɛ from x2, and subject to being in the longer interval between x1 and x2, or x2 and x3, when x2 is particularly close to x1 or x3.
The algorithm is intended to provide fast convergence when f has a positive and continuous second derivative at the minimum. Also, the algorithim avoids gross inefficiencies in pathological cases, such as
f(x) = x + 1.001∣x∣
The algorithm can automatically make ɛ large in the pathological cases. In this case, it is usual for a new value of x to be at the midpoint of the longer interval that is adjacent to the least-calculated function value. The midpoint strategy is used frequently when changes to f are dominated by computer rounding errors, which will almost certainly happen if the user requests an accuracy that is less than the square root of the machine precision. In such cases, the subroutine claims to have achieved the required accuracy if it decides that there is a local minimum point within distance δ of x, where δ = err_abs, even though the rounding errors in f may cause the existence of other local minimum points nearby. This difficulty is inevitable in minimization routines that use only function values, so high precision arithmetic is recommended.
Examples
Example 1
A minimum point of f(x) = ex − 5x is found.
#include <imsl.h>
#include <math.h>
float fcn(float);
int main ()
{
float a = -100.0;
float b = 100.0;
float fx, x;
x = imsl_f_min_uncon (fcn, a, b, 0);
fx = fcn(x);
printf ("The solution is: %8.4f\n", x);
printf ("The function evaluated at the solution is: %8.4f\n", fx);
}
float fcn(float x)
{
return exp(x) - 5.0*x;
}
Output
The solution is: 1.6094
The function evaluated at the solution is: -3.0472
Example 2
A minimum point of f(x) = x(x3 − 1) + 10 is found with an initial guess x0 = 3.
#include <imsl.h>
float fcn(float);
int main ()
{
int max_fcn = 50;
float a = -10.0;
float b = 10.0;
float xguess = 3.0;
float step = 0.1;
float err_abs = 0.001;
float fx, x;
x = imsl_f_min_uncon (fcn, a, b,
IMSL_XGUESS, xguess,
IMSL_STEP, step,
IMSL_ERR_ABS, err_abs,
IMSL_MAX_FCN, max_fcn,
0);
fx = fcn(x);
printf ("The solution is: %8.4f\n", x);
printf ("The function evaluated at the solution is: %8.4f\n", fx);
}
float fcn(float x)
{
return x*(x*x*x-1.0) + 10.0;
}
Output
The solution is: 0.6298
The function evaluated at the solution is: 9.5275
Warning Errors
|
IMSL_MIN_AT_BOUND |
The final value of x is at a bound. |
|
IMSL_NO_MORE_PROGRESS |
Computer rounding errors prevent further refinement of x. |
|
IMSL_TOO_MANY_FCN_EVAL |
Maximum number of function evaluations exceeded. |
Fatal Errors
|
IMSL_STOP_USER_FCN |
Request from user supplied function to stop algorithm. |
