e04abf/e04aba searches for a minimum, in a given finite interval, of a continuous function of a single variable, using function values only. The method (based on quadratic interpolation) is intended for functions which have a continuous first derivative (although it will usually work if the derivative has occasional discontinuities).
e04aba is a version of e04abf that has additional arguments in order to make it safe for use in multithreaded applications (see Section 5).
e04abf/e04aba is applicable to problems of the form:
It 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 funct to evaluate . 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, e04abf/e04aba 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: – Subroutine, supplied by the user.External Procedure
You must supply this routine to calculate the value of the function at any point in . It should be tested separately before being used in conjunction with e04abf/e04aba.
On entry: the point at which the value of is required.
2: – Real (Kind=nag_wp)Output
On exit: must be set to the value of the function at the current point .
Note: the following are additional arguments for specific use with e04aba. Users of e04abf therefore need not read the remainder of this description.
3: – Integer arrayUser Workspace
4: – Real (Kind=nag_wp) arrayUser Workspace
funct is called with the arguments iuser and ruser as supplied to e04abf/e04aba. You should use the arrays iuser and ruser to supply information to funct.
funct must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which e04abf/e04aba is called. Arguments denoted as Input must not be changed by this procedure.
Note:funct should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e04abf/e04aba. If your code inadvertently does return any NaNs or infinities, e04abf/e04aba is likely to produce unexpected results.
2: – Real (Kind=nag_wp)Input/Output
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.)
e1 should be no smaller than , and preferably not much less than , where is the machine precision.
On exit: if you set e1 to (or to any value less than ), e1 will be reset to the default value before starting the minimization process.
3: – Real (Kind=nag_wp)Input/Output
On entry: the absolute accuracy to which the position of a minimum is required. e2 should be no smaller than .
On exit: if you set e2 to (or to any value less than ), e2 will be reset to the default value .
4: – Real (Kind=nag_wp)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: – Real (Kind=nag_wp)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.
6: – IntegerInput/Output
On entry: the maximum number of calls of to be allowed.
Constraint:
. (Few problems will require more than .)
On exit: the total number of times that funct was actually called.
7: – Real (Kind=nag_wp)Output
On exit: the estimated position of the minimum.
8: – Real (Kind=nag_wp)Output
On exit: the function value at the final point given in x.
9: – IntegerInput/Output
Note:for e04aba, ifail does not occur in this position in the argument list. See the additional arguments described below.
On entry: ifail must be set to , or to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of means that an error message is printed while a value of means that it is not.
If halting is not appropriate, the value or is recommended. If message printing is undesirable, then the value is recommended. Otherwise, the value is recommended since useful values can be provided in some output arguments even when on exit. When the value or is used it is essential to test the value of ifail on exit.
On exit: unless the routine detects an error or a warning has been flagged (see Section 6).
Note: the following are additional arguments for specific use with e04aba. Users of e04abf therefore need not read the remainder of this description.
9: – Integer arrayUser Workspace
10: – Real (Kind=nag_wp) arrayUser Workspace
iuser and ruser are not used by e04abf/e04aba, but are passed directly to funct and may be used to pass information to this routine.
11: – IntegerInput/Output
Note: see the argument description for ifail above.
6Error Indicators and Warnings
If on entry or , explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
Note: in some cases e04abf/e04aba may return useful information.
On entry, , and .
Constraint: .
On entry, .
Constraint: .
The maximum number of function calls, , have been performed. This may have happened simply because maxcal was set too small for the particular problem, or may be due to a mistake in the user-supplied function funct. If no mistake can be found in funct, restart e04abf/e04aba (preferably with the values of a and b given on exit from the previous call to e04abf/e04aba).
An unexpected error has been triggered by this routine. Please
contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.
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.
e04abf/e04aba is not threaded in any implementation.
9Further Comments
Timing depends on the behaviour of , the accuracy demanded and the length of the interval . Unless 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 , e04abf/e04aba will determine an approximation (and improved bounds and ) for one of the minima.
If e04abf/e04aba 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 subroutine. Therefore, funct should be programmed to calculate as accurately as possible, so that e04abf/e04aba will not be liable to find a spurious minimum.
10Example
A sketch of the function
shows that it has a minimum somewhere in the range . The following program shows how e04abf/e04aba can be used to obtain a good approximation to the position of a minimum.
10.1Program Text
Note:the following programs illustrate the use of e04abf and e04aba.