e04abc (one_var_func) : NAG Library CL Interface, Mark 27

1 Purpose

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 <nag.h>

void

e04abc (

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)

The function may be called by the names: e04abc, nag_opt_one_var_func or nag_opt_one_var_no_deriv.

3 Description

e04abc is applicable to problems of the form:

Minimize F (x) subject to a \leq x \leq b .

It 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)

. The arguments e1 and e2 together specify the accuracy

$Tol (x) = e1 \times |x| + e2$

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, e04abc will normally find one of the minima.

5 Arguments

funct

– function, supplied by the user External Function

funct must calculate the value of

F (x)

at any point

x

[a, b]

The specification of funct is:

void	funct (double xc, double fc, Nag_Comm comm)

1: $xc$ – double Input

On entry:

x

, the point at which the value of

F (x)

is required.

2: $fc$ – double * Output

On exit: the value of the function

F

at the current point

x

3: $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 e04abc these pointers may be allocated memory and initialized with various quantities for use by funct when called from e04abc.

Note: funct should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by e04abc. If your code inadvertently does return any NaNs or infinities, e04abc is likely to produce unexpected results.

Note: funct should be tested separately before being used in conjunction with e04abc.

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 ε

, and preferably not much less than

\sqrt{ε}

, where

ε

is the machine precision.

If e1 is set to a value less than

ε

, its value is ignored and the default value of

\sqrt{ε}

is used instead. In particular, you may set

e1 = 0.0

to ensure that the default value is used.

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 ε

If e2 is set to a value less than

ε

, its value is ignored and the default value of

\sqrt{ε}

is used instead. In particular, you may set

e2 = 0.0

to ensure that the default value is used.

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.

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:

b > a + e2

Note that the value

e2 = \sqrt{ε}

applies here if

e2 < ε

on entry to e04abc.

max_fun

– Integer Input

On entry: the maximum number of function evaluations (calls to funct) which you are prepared to allow.

The number of evaluations actually performed by e04abc may be determined by supplying a non-NULL argument comm (see below) and examining the structure member

comm \to nf

on exit.

Constraint:

max_fun \geq 3

(Few problems will require more than 30 function evaluations.)

x

– double * Output

On exit: the estimated position of the minimum.

f

– double * Output

On exit: the value of

F

at the final point x.

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

comm \to 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 e04abc; comm will then be declared internally for use in calls to user-supplied functions.

10:

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,

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 3:

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 e04abc (preferably with the values of a and b given on exit from the previous call to e04abc).

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)

can be evaluated very quickly, the run time will usually be dominated by the time spent in funct.

F (x)

has more than one minimum in the original interval

[a, b]

, e04abc will determine an approximation

x

(and improved bounds

a

and

b

) for one of the minima.

If e04abc finds an

x

such that

F (x - δ_{1}) > F (x) < F (x + δ_{2})

for some

δ_{1}, δ_{2} \geq 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 e04abc will not be liable to find a spurious minimum.

NAG CL Interface
e04abc (one_var_func)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG CL Interfacee04abc (one_​var_​func)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG CL Interface
e04abc (one_var_func)