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
$dF/dx$ can be calculated.
e04bbc normally computes a sequence of
$x$ values which tend in the limit to a minimum of
$F\left(x\right)$ subject to the given bounds. It also progressively reduces the interval
$\left[a,b\right]$ in which the minimum is known to lie. It uses the safeguarded quadraticinterpolation method described in
Gill and Murray (1973).
You must supply a function
funct to evaluate
$F\left(x\right)$ and its first derivative. The arguments
e1 and
e2 together specify the accuracy:
 $\mathit{Tol}\left(x\right)={\mathbf{e1}}\times \leftx\right+{\mathbf{e2}}$
to which the position of the minimum is required. Note that
funct is never called at any point which is closer than
$\mathit{Tol}\left(x\right)$ to a previous point.
If the original interval $\left[a,b\right]$ 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:
$\mathbf{funct}$ – function, supplied by the user
External Function

funct must calculate the values of
$F\left(x\right)$ and
$dF/dx$ at any point
$x$ in
$\left[a,b\right]$.
The specification of
funct is:
void 
funct (double xc,
double *fc,
double *gc,
Nag_Comm *comm)



1:
$\mathbf{xc}$ – double
Input

On entry: $x$, the point at which the values of $F$ and $dF/dx$ are required.

2:
$\mathbf{fc}$ – double *
Output

On exit: the value of the function $F$ at the current point $x$.

3:
$\mathbf{gc}$ – double *
Output

On exit: the value of the first derivative $dF/dx$ at the current point $x$.

4:
$\mathbf{comm}$ – 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 floatingpoint 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:
$\mathbf{e1}$ – 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
$x$ is automatically taken into account.)
It is recommended that
e1 should be no smaller than
$2\epsilon $, and preferably not much less than
$\sqrt{\epsilon}$, where
$\epsilon $ is the
machine precision.
If
e1 is set to a value less than
$\epsilon $, its value is ignored and the default value of
$\sqrt{\epsilon}$ is used instead. In particular, you may set
${\mathbf{e1}}=0.0$ to ensure that the default value is used.

3:
$\mathbf{e2}$ – 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
$2\epsilon $.
If
e2 is set to a value less than
$\epsilon $, its value is ignored and the default value of
$\sqrt{\epsilon}$ is used instead. In particular, you may set
${\mathbf{e2}}=0.0$ to ensure that the default value is used.

4:
$\mathbf{a}$ – double *
Input/Output

On entry: the lower bound $a$ of the interval containing a minimum.
On exit: an improved lower bound on the position of the minimum.

5:
$\mathbf{b}$ – double *
Input/Output

On entry: the upper bound $b$ of the interval containing a minimum.
On exit: an improved upper bound on the position of the minimum.
Constraint:
${\mathbf{b}}>{\mathbf{a}}+{\mathbf{e2}}$.
Note that the value ${\mathbf{e2}}=\sqrt{\epsilon}$ applies here if ${\mathbf{e2}}<\epsilon $ on entry to e04bbc.

6:
$\mathbf{max\_fun}$ – 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 nonNULL argument
comm (see below) and examining the structure member
$\mathbf{comm}\mathbf{\to}\mathbf{nf}$ on exit.
Constraint:
${\mathbf{max\_fun}}\ge 2$(Few problems will require more than 20 function calls.)

7:
$\mathbf{x}$ – double *
Output

On exit: the estimated position of the minimum.

8:
$\mathbf{f}$ – double *
Output

On exit: the value of
$F$ at the final point
x.

9:
$\mathbf{g}$ – double *
Output

On exit: the value of the first derivative
$dF/dx$ at the final point
x.

10:
$\mathbf{comm}$ – 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 usersupplied functions; see the above description of
funct for details. The number of times the function
funct was called is returned in the member
$\mathbf{comm}\mathbf{\to}\mathbf{nf}$.
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 usersupplied functions.

11:
$\mathbf{fail}$ – 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, ${\mathbf{a}}+{\mathbf{e2}}=\u2329\mathit{\text{value}}\u232a$ while ${\mathbf{b}}=\u2329\mathit{\text{value}}\u232a$. These arguments must satisfy ${\mathbf{a}}+{\mathbf{e2}}<{\mathbf{b}}$.
 NE_INT_ARG_LT

On entry,
max_fun must not be less than 2:
${\mathbf{max\_fun}}=\u2329\mathit{\text{value}}\u232a$.
 NW_MAX_FUN

The maximum number of function calls, $\u2329\mathit{\text{value}}\u232a$, 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 usersupplied 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 $F\left(x\right)$ is $\delta $unimodal for some $\delta <\mathit{Tol}\left(x\right)$, where $\mathit{Tol}\left(x\right)={\mathbf{e1}}\times \leftx\right+{\mathbf{e2}}$, then, on exit, $x$ approximates the minimum of $F\left(x\right)$ in the original interval $\left[a,b\right]$ with an error less than $3\times \mathit{Tol}\left(x\right)$.
8
Parallelism and Performance
e04bbc is not threaded in any implementation.
Timing depends on the behaviour of
$F\left(x\right)$, the accuracy demanded, and the length of the interval
$\left[a,b\right]$. Unless
$F\left(x\right)$ and
$dF/dx$ can be evaluated very quickly, the run time will usually be dominated by the time spent in
funct.
If $F\left(x\right)$ has more than one minimum in the original interval $\left[a,b\right]$, e04bbc will determine an approximation $x$ (and improved bounds $a$ and $b$) for one of the minima.
If
e04bbc finds an
$x$ such that
$F\left(x{\delta}_{1}\right)>F\left(x\right)<F\left(x+{\delta}_{2}\right)$ for some
${\delta}_{1},{\delta}_{2}\ge \mathit{Tol}\left(x\right)$, the interval
$\left[x{\delta}_{1},x+{\delta}_{2}\right]$ will be regarded as containing a minimum, even if
$F\left(x\right)$ is less than
$F\left(x{\delta}_{1}\right)$ and
$F\left(x+{\delta}_{2}\right)$ only due to rounding errors in the usersupplied function. Therefore
funct should be programmed to calculate
$F\left(x\right)$ as accurately as possible, so that
e04bbc will not be liable to find a spurious minimum. (For similar reasons,
$dF/dx$ should be evaluated as accurately as possible.)
10
Example
A sketch of the function
shows that it has a minimum somewhere in the range
$\left[3.5,5.0\right]$. 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