e04 Chapter Contents
e04 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_opt_one_var_no_deriv (e04abc)

## 1  Purpose

nag_opt_one_var_no_deriv (e04abc) 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).

## 2  Specification

 #include #include
void  nag_opt_one_var_no_deriv (
 void (*funct)(double xc, double *fc, Nag_Comm *comm),
double e1, double e2, double *a, double *b, Integer max_fun, double *x, double *f, Nag_Comm *comm, NagError *fail)

## 3  Description

nag_opt_one_var_no_deriv (e04abc) is applicable to problems of the form:
 $Minimize F x subject to a ≤ x ≤ b .$
It 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 quadratic-interpolation method described in Gill and Murray (1973).
You must supply a function funct to evaluate $F\left(x\right)$. The arguments e1 and e2 together specify the accuracy
• $\mathit{Tol}\left(x\right)={\mathbf{e1}}×\left|x\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, nag_opt_one_var_no_deriv (e04abc) 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:     functfunction, supplied by the userExternal Function
funct must calculate the value of $F\left(x\right)$ at any point $x$ in $\left[a,b\right]$.
The specification of funct is:
 void funct (double xc, double *fc, Nag_Comm *comm)
1:     xcdoubleInput
On entry: $x$, the point at which the value of $F\left(x\right)$ is required.
2:     fcdouble *Output
On exit: the value of the function $F$ at the current point $x$.
3:     commNag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to funct.
firstNag_BooleanInput
On entry: will be set to Nag_TRUE on the first call to funct and Nag_FALSE for all subsequent calls.
nfIntegerInput
On entry: the number of calls made to funct so far.
userdouble *
iuserInteger *
pPointer
The type Pointer will be void * with a C compiler that defines void * and char * otherwise. Before calling nag_opt_one_var_no_deriv (e04abc) these pointers may be allocated memory and initialized with various quantities for use by funct when called from nag_opt_one_var_no_deriv (e04abc).
Note: funct should be tested separately before being used in conjunction with nag_opt_one_var_no_deriv (e04abc).
2:     e1doubleInput
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:     e2doubleInput
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.
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:     bdouble *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 nag_opt_one_var_no_deriv (e04abc).
6:     max_funIntegerInput
On entry: the maximum number of function evaluations (calls to funct) which you are prepared to allow.
The number of evaluations actually performed by nag_opt_one_var_no_deriv (e04abc) may be determined by supplying a non-NULL argument comm (see below) and examining the structure member $\mathbf{comm}\mathbf{\to }\mathbf{nf}$ on exit.
Constraint: ${\mathbf{max_fun}}\ge 3$.
(Few problems will require more than 30 function evaluations.)
7:     xdouble *Output
On exit: the estimated position of the minimum.
8:     fdouble *Output
On exit: the value of $F$ at the final point x.
9:     commNag_Comm *Input/Output
Note: comm is a NAG defined type (see Section 3.2.1.1 in the Essential Introduction).
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 $\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 nag_opt_one_var_no_deriv (e04abc); comm will then be declared internally for use in calls to user-supplied functions.
10:   failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_2_REAL_ARG_GE
On entry, ${\mathbf{a}}+{\mathbf{e2}}=〈\mathit{\text{value}}〉$ while ${\mathbf{b}}=〈\mathit{\text{value}}〉$. These arguments must satisfy ${\mathbf{a}}+{\mathbf{e2}}<{\mathbf{b}}$.
NE_INT_ARG_LT
On entry, max_fun must not be less than 3: ${\mathbf{max_fun}}=〈\mathit{\text{value}}〉$.
NW_MAX_FUN
The maximum number of function calls, $〈\mathit{\text{value}}〉$, 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 nag_opt_one_var_no_deriv (e04abc) (preferably with the values of a and b given on exit from the previous call to nag_opt_one_var_no_deriv (e04abc)).

## 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}}×\left|x\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×\mathit{Tol}\left(x\right)$.

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)$ 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]$, nag_opt_one_var_no_deriv (e04abc) will determine an approximation $x$ (and improved bounds $a$ and $b$) for one of the minima.
If nag_opt_one_var_no_deriv (e04abc) finds an $x$ such that $F\left(x-{\delta }_{1}\right)>F\left(x\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 user-supplied function. Therefore funct should be programmed to calculate $F\left(x\right)$ as accurately as possible, so that nag_opt_one_var_no_deriv (e04abc) will not be liable to find a spurious minimum.

## 9  Example

A sketch of the function
 $F x = sin⁡x x$
shows that it has a minimum somewhere in the range $\left[3.5,5.0\right]$. The example program below shows how nag_opt_one_var_no_deriv (e04abc) can be used to obtain a good approximation to the position of a minimum.

### 9.1  Program Text

Program Text (e04abce.c)

None.

### 9.3  Program Results

Program Results (e04abce.r)