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

C#
public static void e04bb( E04..::..E04BB_FUNCT funct, ref double e1, ref double e2, ref double a, ref double b, ref int maxcal, out double x, out double f, out double g, out int ifail )

Visual Basic
Public Shared Sub e04bb ( _ funct As E04..::..E04BB_FUNCT, _ ByRef e1 As Double, _ ByRef e2 As Double, _ ByRef a As Double, _ ByRef b As Double, _ ByRef maxcal As Integer, _ <OutAttribute> ByRef x As Double, _ <OutAttribute> ByRef f As Double, _ <OutAttribute> ByRef g As Double, _ <OutAttribute> ByRef ifail As Integer _ )

Visual Basic

Public Shared Sub e04bb ( _
	funct As E04..::..E04BB_FUNCT, _
	ByRef e1 As Double, _
	ByRef e2 As Double, _
	ByRef a As Double, _
	ByRef b As Double, _
	ByRef maxcal As Integer, _
	<OutAttribute> ByRef x As Double, _
	<OutAttribute> ByRef f As Double, _
	<OutAttribute> ByRef g As Double, _
	<OutAttribute> ByRef ifail As Integer _
)

Visual C++
public: static void e04bb( E04..::..E04BB_FUNCT^ funct, double% e1, double% e2, double% a, double% b, int% maxcal, [OutAttribute] double% x, [OutAttribute] double% f, [OutAttribute] double% g, [OutAttribute] int% ifail )

Visual C++

public:
static void e04bb(
	E04..::..E04BB_FUNCT^ funct, 
	double% e1, 
	double% e2, 
	double% a, 
	double% b, 
	int% maxcal, 
	[OutAttribute] double% x, 
	[OutAttribute] double% f, 
	[OutAttribute] double% g, 
	[OutAttribute] int% ifail
)

F#
static member e04bb : funct : E04..::..E04BB_FUNCT * e1 : float byref * e2 : float byref * a : float byref * b : float byref * maxcal : int byref * x : float byref * f : float byref * g : float byref * ifail : int byref -> unit

static member e04bb : 
        funct : E04..::..E04BB_FUNCT * 
        e1 : float byref * 
        e2 : float byref * 
        a : float byref * 
        b : float byref * 
        maxcal : int byref * 
        x : float byref * 
        f : float byref * 
        g : float byref * 
        ifail : int byref -> unit

Parameters

funct: Type: NagLibrary..::..E04..::..E04BB_FUNCT
You must supply this method to calculate the values of $F (x)$ and $\frac{d F}{d x}$ at any point $x$ in $[a, b]$ .
It should be tested separately before being used in conjunction with e04bb.
A delegate of type E04BB_FUNCT.

e1: Type: System..::..Double%
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.)
e1 should be no smaller than $2 ε$ , and preferably not much less than $\sqrt{ε}$ , where $ε$ is the machine precision.

On exit: 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.

e2: Type: System..::..Double%
On entry: the absolute accuracy to which the position of a minimum is required. e2 should be no smaller than $2 ε$ .
On exit: if you set e2 to $0.0$ (or to any value less than $ε$ ), e2 will be reset to the default value $\sqrt{ε}$ .

a: Type: System..::..Double%
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: Type: System..::..Double%
On entry: the upper bound $b$ of the interval containing a minimum.
On exit: an improved upper bound on the position of the minimum.

maxcal: Type: System..::..Int32%
On entry: 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
On exit: the total number of times that funct was actually called.

x: Type: System..::..Double%
On exit: the estimated position of the minimum.

f: Type: System..::..Double%
On exit: the function value at the final point given in x.

g: Type: System..::..Double%
On exit: the value of the first derivative at the final point in x.

ifail: Type: System..::..Int32%
On exit: $ifail = 0$ unless the method detects an error or a warning has been flagged (see [Error Indicators and Warnings]).

Description

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 method 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 parameters 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, 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

Error Indicators and Warnings

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

Errors or warnings detected by the method:

$ifail = 1$

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

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

$ifail = -9000$: An error occured, see message report.
$ifail = -8000$: Negative dimension for array $〈value〉$
$ifail = -6000$: Invalid Parameters $〈value〉$

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)

Parallelism and Performance

None.

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]

, e04bb will determine an approximation

x

(and improved bounds

a

and

b

) for one of the minima.

If 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 method. Therefore funct should be programmed to calculate

F (x)

as accurately as possible, so that 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 e04bb can be used to obtain a good approximation to the position of a minimum.

Example program (C#): e04bbe.cs

Example program results: e04bbe.r