hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_opt_one_var_deriv (e04bb)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

Purpose

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:
MinimizeFx  subject to  axb  
when the first derivative dF dx  can be calculated. The function normally computes a sequence of x values which tend in the limit to a minimum of Fx 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 Fx and dF dx . The arguments e1 and e2 together specify the accuracy
Tolx=e1×x+e2  
to which the position of the minimum is required. Note that funct is never called at a point which is closer than Tolx 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 Fx and dF dx  at any point x in 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 dF dx  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 dF dx 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 ε, 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: maxcal2. (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 ε 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 ε.
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+e2b,
ormaxcal<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

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

Further Comments

Timing depends on the behaviour of Fx, the accuracy demanded and the length of the interval a,b. Unless Fx and dF dx  can be evaluated very quickly, the run time will usually be dominated by the time spent in funct.
If Fx 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 Fx-δ1>Fx<Fx+δ2 for some δ1,δ2Tolx, the interval x-δ1,x+δ2 will be regarded as containing a minimum, even if Fx is less than Fx-δ1 and Fx+δ2 only due to rounding errors in the function. Therefore funct should be programmed to calculate Fx as accurately as possible, so that nag_opt_one_var_deriv (e04bb) will not be liable to find a spurious minimum. (For similar reasons, dF dx  should be evaluated as accurately as possible.)

Example

A sketch of the function
Fx=sinxx  
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.
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

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015