Find the minimum point of a smooth function f(x) of a single variable using only function evaluations.
#include <imsl.h>
float imsl_f_min_uncon (float fcn(), float a, float b, ¼, 0)
The type double function is imsl_d_min_uncon.
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.
The point at which a minimum value of fcn is found. If no value can be computed, NaN is returned.
#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)
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 the Introduction, Passing Data to
User-Supplied Functions at the beginning of this manual for more
details.
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.
A minimum point of f(x) = ex − 5x is found.
#include <imsl.h>
#include
<math.h>
float
fcn(float);
void 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;
}
The solution is: 1.6094
The function
evaluated at the solution is: -3.0472
A minimum point of f(x) = x(x3 − 1) + 10 is found with an initial guess x0 = 3.
#include
<imsl.h>
float
fcn(float);
void 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;
}
The solution is: 0.6298
The function
evaluated at the solution is: 9.5275
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.
|
Visual Numerics, Inc. PHONE: 713.784.3131 FAX:713.781.9260 |