NAG CL Interface
e04bbc (one_var_deriv)
1
Purpose
e04bbc searches for a minimum, in a given finite interval, of a continuous function of a single variable, using function and first derivative values. The method (based on cubic interpolation) is intended for functions which have a continuous first derivative (although it will usually work if the derivative has occasional discontinuities).
2
Specification
void |
e04bbc (
double e1,
double e2,
double *a,
double *b,
Integer max_fun,
double *x,
double *f,
double *g,
Nag_Comm *comm,
NagError *fail) |
|
The function may be called by the names: e04bbc or nag_opt_one_var_deriv.
3
Description
e04bbc is applicable to problems of the form:
when the first derivative
can be calculated.
e04bbc normally computes a sequence of
values which tend in the limit to a minimum of
subject to the given bounds. It also progressively reduces the interval
in which the minimum is known to lie. It uses the safeguarded quadratic-interpolation method described in
Gill and Murray (1973).
You must supply a function
funct to evaluate
and its first derivative. The arguments
e1 and
e2 together specify the accuracy:
to which the position of the minimum is required. Note that
funct is never called at any point which is closer than
to a previous point.
If the original interval contains more than one minimum,e04bbc will normally find one of the minima.
4
References
Gill P E and Murray W (1973) Safeguarded steplength algorithms for optimization using descent methods NPL Report NAC 37 National Physical Laboratory
5
Arguments
-
1:
– function, supplied by the user
External Function
-
funct must calculate the values of
and
at any point
in
.
The specification of
funct is:
void |
funct (double xc,
double *fc,
double *gc,
Nag_Comm *comm)
|
|
-
1:
– double
Input
-
On entry: , the point at which the values of and are required.
-
2:
– double *
Output
-
On exit: the value of the function at the current point .
-
3:
– double *
Output
-
On exit: the value of the first derivative at the current point .
-
4:
– Nag_Comm *
-
Pointer to structure of type Nag_Comm; the following members are relevant to
funct.
- first – Nag_BooleanInput
-
On entry: will be set to Nag_TRUE on the first call to
funct and Nag_FALSE for all subsequent calls.
- nf – IntegerInput
-
On entry: the number of calls made to
funct so far.
- user – double *
- iuser – Integer *
- p – Pointer
-
The type Pointer will be
void * with a C compiler that defines
void * and
char * otherwise. Before calling
e04bbc these pointers may be allocated memory and initialized with various quantities for use by
funct when called from
e04bbc.
Note: funct should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by
e04bbc. If your code inadvertently
does return any NaNs or infinities,
e04bbc is likely to produce unexpected results.
Note: funct should be tested separately before being used in conjunction with
e04bbc.
-
2:
– double
Input
-
On entry: the relative accuracy to which the position of a minimum is required. (Note that since
e1 is a relative tolerance, the scaling of
is automatically taken into account.)
It is recommended that
e1 should be no smaller than
, and preferably not much less than
, where
is the
machine precision.
If
e1 is set to a value less than
, its value is ignored and the default value of
is used instead. In particular, you may set
to ensure that the default value is used.
-
3:
– double
Input
-
On entry: the absolute accuracy to which the position of a minimum is required. It is recommended that
e2 should be no smaller than
.
If
e2 is set to a value less than
, its value is ignored and the default value of
is used instead. In particular, you may set
to ensure that the default value is used.
-
4:
– double *
Input/Output
-
On entry: the lower bound of the interval containing a minimum.
On exit: an improved lower bound on the position of the minimum.
-
5:
– double *
Input/Output
-
On entry: the upper bound of the interval containing a minimum.
On exit: an improved upper bound on the position of the minimum.
Constraint:
.
Note that the value applies here if on entry to e04bbc.
-
6:
– Integer
Input
-
On entry: the maximum number of calls to
funct which you are prepared to allow.
The number of calls to
funct actually made by
e04bbc may be determined by supplying a non-NULL argument
comm (see below) and examining the structure member
on exit.
Constraint:
(Few problems will require more than 20 function calls.)
-
7:
– double *
Output
-
On exit: the estimated position of the minimum.
-
8:
– double *
Output
-
On exit: the value of
at the final point
x.
-
9:
– double *
Output
-
On exit: the value of the first derivative
at the final point
x.
-
10:
– Nag_Comm *
Input/Output
-
Note: comm is a NAG defined type (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).
On entry/exit: structure containing pointers for communication to user-supplied functions; see the above description of
funct for details. The number of times the function
funct was called is returned in the member
.
If you do not need to make use of this communication feature, the null pointer
NAGCOMM_NULL may be used in the call to
e04bbc;
comm will then be declared internally for use in calls to user-supplied functions.
-
11:
– NagError *
Input/Output
-
The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
6
Error Indicators and Warnings
- NE_2_REAL_ARG_GE
-
On entry, while . These arguments must satisfy .
- NE_INT_ARG_LT
-
On entry,
max_fun must not be less than 2:
.
- NW_MAX_FUN
-
The maximum number of function calls, , have been performed.
This may have happened simply because
max_fun was set too small for a particular problem, or may be due to a mistake in the user-supplied function,
funct. If no mistake can be found in
funct, restart
e04bbc (preferably with the values of
a and
b given on exit from the previous call to
e04bbc).
7
Accuracy
If is -unimodal for some , where , then, on exit, approximates the minimum of in the original interval with an error less than .
8
Parallelism and Performance
e04bbc is not threaded in any implementation.
Timing depends on the behaviour of
, the accuracy demanded, and the length of the interval
. Unless
and
can be evaluated very quickly, the run time will usually be dominated by the time spent in
funct.
If has more than one minimum in the original interval , e04bbc will determine an approximation (and improved bounds and ) for one of the minima.
If
e04bbc finds an
such that
for some
, the interval
will be regarded as containing a minimum, even if
is less than
and
only due to rounding errors in the user-supplied function. Therefore
funct should be programmed to calculate
as accurately as possible, so that
e04bbc will not be liable to find a spurious minimum. (For similar reasons,
should be evaluated as accurately as possible.)
10
Example
A sketch of the function
shows that it has a minimum somewhere in the range
. The example program below shows how
e04bbc can be used to obtain a good approximation to the position of a minimum.
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results