nag_opt_one_var_deriv (e04bb) 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).

Syntax

[e1, e2, a, b, maxcal, x, f, g, user, ifail] = e04bb(funct, e1, e2, a, b, maxcal, 'user', user)

[e1, e2, a, b, maxcal, x, f, g, user, ifail] = nag_opt_one_var_deriv(funct, e1, e2, a, b, maxcal, 'user', user)

Description

nag_opt_one_var_deriv (e04bb) is applicable to problems of the form:

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

when the first derivative

\frac{d F}{d x}

can be calculated. The function 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 cubic-interpolation method described in Gill and Murray (1973).

You must supply a funct to evaluate

F (x)

and

\frac{d F}{d 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 a 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 (e04bb) will normally find one of the minima.

References

Gill P E and Murray W (1973) Safeguarded steplength algorithms for optimization using descent methods NPL Report NAC 37 National Physical Laboratory

Parameters

Compulsory Input Parameters

1: $funct$ – function handle or string containing name of m-file

You must supply this function to calculate the values of

F (x)

and

\frac{d F}{d x}

at any point

x

[a, b]

It should be tested separately before being used in conjunction with nag_opt_one_var_deriv (e04bb).

[fc, gc, user] = funct(xc, user)

Input Parameters

1: $xc$ – double scalar: The point $x$ at which the values of $F$ and $\frac{d F}{d x}$ are required.
2: $user$ – Any MATLAB object: funct is called from nag_opt_one_var_deriv (e04bb) with the object supplied to nag_opt_one_var_deriv (e04bb).

Output Parameters

1: $fc$ – double scalar: Must be set to the value of the function $F$ at the current point $x$ .
2: $gc$ – double scalar: Must be set to the value of the first derivative $\frac{d F}{d x}$ at the current point $x$ .
3: $user$ – Any MATLAB object

2: $e1$ – double scalar

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

e1 should be no smaller than

2 ε

, and preferably not much less than

\sqrt{ε}

, where

ε

is the machine precision.

3: $e2$ – double scalar

The absolute accuracy to which the position of a minimum is required. e2 should be no smaller than

2 ε

4: $a$ – double scalar

The lower bound

a

of the interval containing a minimum.

5: $b$ – double scalar

The upper bound

b

of the interval containing a minimum.

6: $maxcal$ – int64int32nag_int scalar

The maximum number of calls of funct to be allowed.

Constraint:

maxcal \geq 2

. (Few problems will require more than

20

There will be an error exit (see Error Indicators and Warnings) after maxcal calls of funct

Optional Input Parameters

1: $user$ – Any MATLAB object: user is not used by nag_opt_one_var_deriv (e04bb), but is passed to funct. Note that for large objects it may be more efficient to use a global variable which is accessible from the m-files than to use user.

Output Parameters

1: $e1$ – double scalar: If you set e1 to $0.0$ (or to any value less than $ε$ ), e1 will be reset to the default value $\sqrt{ε}$ before starting the minimization process.
2: $e2$ – double scalar: If you set e2 to $0.0$ (or to any value less than $ε$ ), e2 will be reset to the default value $\sqrt{ε}$ .
3: $a$ – double scalar: An improved lower bound on the position of the minimum.
4: $b$ – double scalar: An improved upper bound on the position of the minimum.
5: $maxcal$ – int64int32nag_int scalar: The total number of times that funct was actually called.
6: $x$ – double scalar: The estimated position of the minimum.
7: $f$ – double scalar: The function value at the final point given in x.
8: $g$ – double scalar: The value of the first derivative at the final point in x.
9: $user$ – Any MATLAB object
10: $ifail$ – int64int32nag_int scalar: $ifail = 0$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Note: nag_opt_one_var_deriv (e04bb) may return useful information for one or more of the following detected errors or warnings.

Errors or warnings detected by the function:

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

W $ifail = 1$

On entry,	$(a + e2) \geq b$ ,
or	$maxcal < 2$ .

W $ifail = 2$: The number of calls of funct has exceeded maxcal. This may have happened simply because maxcal was set too small for a particular problem, or may be due to a mistake in funct. If no mistake can be found in funct, restart nag_opt_one_var_deriv (e04bb) (preferably with the values of a and b given on exit from the previous call of nag_opt_one_var_deriv (e04bb)).

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

F (x)

δ

-unimodal for some

δ < Tol (x)

, where

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

, then, on exit,

x

approximates the minimum of

F (x)

in the original interval

[a, b]

with an error less than

3 \times Tol (x)

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

\frac{d F}{d 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]

, nag_opt_one_var_deriv (e04bb) will determine an approximation

x

(and improved bounds

a

and

b

) for one of the minima.

If nag_opt_one_var_deriv (e04bb) 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 function. Therefore funct should be programmed to calculate

F (x)

as accurately as possible, so that nag_opt_one_var_deriv (e04bb) will not be liable to find a spurious minimum. (For similar reasons,

\frac{d F}{d x}

should be evaluated as accurately as possible.)

Example

A sketch of the function

F (x) = \frac{\sin x}{x}

shows that it has a minimum somewhere in the range

[3.5, 5.0]

. The following program shows how nag_opt_one_var_deriv (e04bb) can be used to obtain a good approximation to the position of a minimum.

Open in the MATLAB editor: e04bb_example

function e04bb_example


fprintf('e04bb example results\n\n');

e1 = 0;
e2 = 0;
a = 3.5;
b = 5;
maxcal = int64(30);

[e1, e2, a, b, maxcal, x, f, g, user, ifail] = ...
e04bb( ...
       @funct, e1, e2, a, b, maxcal);

fprintf('The minimum lies in the interval  [%11.8f,%11.8f]\n', a, b);
fprintf('Estimated position of minimum, x = %11.8f\n', x);
fprintf('Function value at minimum,  f(x) = %7.4f\n', f);
fprintf('Gradient value at minimum, f''(x) = %8.1e\n', g);
fprintf('Number of function evaluations   = %2d\n', maxcal);



function [fc,gc,user] = funct(xc,user)
  fc=sin(xc)/xc;
  gc=(cos(xc)-fc)/xc;

e04bb example results

The minimum lies in the interval  [ 4.49340946, 4.49340952]
Estimated position of minimum, x =  4.49340946
Function value at minimum,  f(x) = -0.2172
Gradient value at minimum, f'(x) = -3.8e-16
Number of function evaluations   =  6

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox