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).
The function may be called by the names: e04bbc or nag_opt_one_var_deriv.
3Description
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.
4References
Gill P E and Murray W (1973) Safeguarded steplength algorithms for optimization using descent methods NPL Report NAC 37 National Physical Laboratory
5Arguments
1: – function, supplied by the userExternal Function
funct must calculate the values of and at any point in .
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: – doubleInput
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: – doubleInput
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: – IntegerInput
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.)
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).
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).
7Accuracy
If is -unimodal for some , where , then, on exit, approximates the minimum of in the original interval with an error less than .
8Parallelism and Performance
Background information to multithreading can be found in the Multithreading documentation.
e04bbc is not threaded in any implementation.
9Further Comments
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.)
10Example
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.