nag_opt_one_var_deriv (e04bbc) (PDF version)
e04 Chapter Contents
e04 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_opt_one_var_deriv (e04bbc)

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_opt_one_var_deriv (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

#include <nag.h>
#include <nage04.h>
void  nag_opt_one_var_deriv (
void (*funct)(double xc, double *fc, double *gc, Nag_Comm *comm),
double e1, double e2, double *a, double *b, Integer max_fun, double *x, double *f, double *g, Nag_Comm *comm, NagError *fail)

3  Description

nag_opt_one_var_deriv (e04bbc) is applicable to problems of the form:
Minimize   F x   subject to   a x b
when the first derivative dF / dx  can be calculated. nag_opt_one_var_deriv (e04bbc) normally computes a sequence of x  values which tend in the limit to a minimum of F x  subject to the given bounds. It also progressively reduces the interval a,b  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 x  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 Tol x  to a previous point.
If the original interval a,b  contains more than one minimum,nag_opt_one_var_deriv (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:     functfunction, supplied by the userExternal Function
funct must calculate the values of F x  and dF / dx  at any point x  in a,b .
The specification of funct is:
void  funct (double xc, double *fc, double *gc, Nag_Comm *comm)
1:     xcdoubleInput
On entry: x , the point at which the values of F  and dF / dx  are required.
2:     fcdouble *Output
On exit: the value of the function F  at the current point x .
3:     gcdouble *Output
On exit: the value of the first derivative dF / dx  at the current point x .
4:     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_deriv (e04bbc) these pointers may be allocated memory and initialized with various quantities for use by funct when called from nag_opt_one_var_deriv (e04bbc).
Note: funct should be tested separately before being used in conjunction with nag_opt_one_var_deriv (e04bbc).
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 ε , 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 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 ε .
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 e2=0.0  to ensure that the default value is used.
4:     adouble *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:     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: b > a + e2 .
Note that the value e2 = ε  applies here if e2<ε  on entry to nag_opt_one_var_deriv (e04bbc).
6:     max_funIntegerInput
On entry: the maximum number of calls to funct which you are prepared to allow.
The number of calls to funct actually made by nag_opt_one_var_deriv (e04bbc) may be determined by supplying a non-NULL argument comm (see below) and examining the structure member commnf on exit.
Constraint: max_fun2 .
(Few problems will require more than 20 function calls.)
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:     gdouble *Output
On exit: the value of the first derivative dF / dx  at the final point x.
10:   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 commnf.
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_deriv (e04bbc); comm will then be declared internally for use in calls to user-supplied functions.
11:   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, a + e2 = value while b=value . These arguments must satisfy a + e2 < b .
NE_INT_ARG_LT
On entry, max_fun must not be less than 2: max_fun=value .
NW_MAX_FUN
The maximum number of function calls, 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_deriv (e04bbc) (preferably with the values of a and b given on exit from the previous call to nag_opt_one_var_deriv (e04bbc)).

7  Accuracy

If F x  is δ -unimodal for some δ < Tol x , where Tol x = e1 × x + e2 , then, on exit, x  approximates the minimum of F x  in the original interval a,b  with an error less than 3 × Tol x .

8  Parallelism and Performance

Not applicable.

9  Further Comments

Timing depends on the behaviour of F x , the accuracy demanded, and the length of the interval a,b . Unless F x  and dF / dx  can be evaluated very quickly, the run time will usually be dominated by the time spent in funct.
If F x  has more than one minimum in the original interval a,b , nag_opt_one_var_deriv (e04bbc) will determine an approximation x  (and improved bounds a  and b ) for one of the minima.
If nag_opt_one_var_deriv (e04bbc) finds an x  such that F x - δ 1 > F x < F x + δ 2  for some δ 1 , δ 2 Tol x , the interval x - δ 1 , x + δ 2  will be regarded as containing a minimum, even if F x  is less than F x - δ 1  and F x + δ 2  only due to rounding errors in the user-supplied function. Therefore funct should be programmed to calculate F x  as accurately as possible, so that nag_opt_one_var_deriv (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
F x = sinx x
shows that it has a minimum somewhere in the range 3.5,5.0 . The example program below shows how nag_opt_one_var_deriv (e04bbc) can be used to obtain a good approximation to the position of a minimum.

10.1  Program Text

Program Text (e04bbce.c)

10.2  Program Data

None.

10.3  Program Results

Program Results (e04bbce.r)


nag_opt_one_var_deriv (e04bbc) (PDF version)
e04 Chapter Contents
e04 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2014