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_uncon_simplex (e04cb)

Purpose

nag_opt_uncon_simplex (e04cb) minimizes a general function F(x)F(x) of nn independent variables x = (x1,x2,,xn)T x = (x1,x2,,xn)T  by the Nelder and Mead simplex method (see Nelder and Mead (1965)). Derivatives of the function need not be supplied.

Syntax

[x, f, user, ifail] = e04cb(x, tolf, tolx, funct, monit, maxcal, 'n', n, 'user', user)
[x, f, user, ifail] = nag_opt_uncon_simplex(x, tolf, tolx, funct, monit, maxcal, 'n', n, 'user', user)

Description

nag_opt_uncon_simplex (e04cb) finds an approximation to a minimum of a function FF of nn variables. You must supply a function to calculate the value of FF for any set of values of the variables.
The method is iterative. A simplex of n + 1n+1 points is set up in the nn-dimensional space of the variables (for example, in 22 dimensions the simplex is a triangle) under the assumption that the problem has been scaled so that the values of the independent variables at the minimum are of order unity. The starting point you have provided is the first vertex of the simplex, the remaining nn vertices are generated by nag_opt_uncon_simplex (e04cb). The vertex of the simplex with the largest function value is reflected in the centre of gravity of the remaining vertices and the function value at this new point is compared with the remaining function values. Depending on the outcome of this test the new point is accepted or rejected, a further expansion move may be made, or a contraction may be carried out. See Nelder and Mead (1965) and Parkinson and Hutchinson (1972) for more details. When no further progress can be made the sides of the simplex are reduced in length and the method is repeated.
The method can be slow, but computational bottlenecks have been reduced following Singer and Singer (2004). However, nag_opt_uncon_simplex (e04cb) is robust, and therefore very useful for functions that are subject to inaccuracies.
There are the following options for successful termination of the method: based only on the function values at the vertices of the current simplex (see (1)); based only on a volume ratio between the current simplex and the initial one (see (2)); or based on which one of the previous two tests passes first. The volume test may be useful if FF is discontinuous, while the function-value test should be sufficient on its own if FF is continuous.

References

Nelder J A and Mead R (1965) A simplex method for function minimization Comput. J. 7 308–313
Parkinson J M and Hutchinson D (1972) An investigation into the efficiency of variants of the simplex method Numerical Methods for Nonlinear Optimization (ed F A Lootsma) Academic Press
Singer S and Singer S (2004) Efficient implementation of the Nelder–Mead search algorithm Appl. Num. Anal. Comp. Math. 1(3) 524–534

Parameters

Compulsory Input Parameters

1:     x(n) – double array
n, the dimension of the array, must satisfy the constraint n1n1.
A guess at the position of the minimum. Note that the problem should be scaled so that the values of the x(i)xi are of order unity.
2:     tolf – double scalar
The error tolerable in the function values, in the following sense. If fifi, for i = 1,2,,n + 1i=1,2,,n+1, are the individual function values at the vertices of the current simplex, and if fmfm is the mean of these values, then you can request that nag_opt_uncon_simplex (e04cb) should terminate if
sqrt( 1/(n + 1) i = 1n + 1 (fifm)2 ) < tolf .
1 n+1 i=1 n+1 ( fi - fm ) 2 < tolf .
(1)
You may specify tolf = 0tolf=0 if you wish to use only the termination criterion (2) on the spatial values: see the description of tolx.
Constraint: tolftolf must be greater than or equal to the machine precision (see Chapter X02), or if tolf equals zero then tolx must be greater than or equal to the machine precision.
3:     tolx – double scalar
The error tolerable in the spatial values, in the following sense. If LVLV denotes the ‘linearized’ volume of the current simplex, and if LVinitLVinit denotes the ‘linearized’ volume of the initial simplex, then you can request that nag_opt_uncon_simplex (e04cb) should terminate if
(LV)/( LVinit ) < tolx .
LV LV init < tolx .
(2)
You may specify tolx = 0tolx=0 if you wish to use only the termination criterion (1) on function values: see the description of tolf.
Constraint: tolxtolx must be greater than or equal to the machine precision (see Chapter X02), or if tolx equals zero then tolf must be greater than or equal to the machine precision.
4:     funct – function handle or string containing name of m-file
funct must evaluate the function FF at a specified point. It should be tested separately before being used in conjunction with nag_opt_uncon_simplex (e04cb).
[fc, user] = funct(n, xc, user)

Input Parameters

1:     n – int64int32nag_int scalar
nn, the number of variables.
2:     xc(n) – double array
The point at which the function value is required.
3:     user – Any MATLAB object
funct is called from nag_opt_uncon_simplex (e04cb) with the object supplied to nag_opt_uncon_simplex (e04cb).

Output Parameters

1:     fc – double scalar
The value of the function FF at the current point xx.
2:     user – Any MATLAB object
5:     monit – function handle or string containing name of m-file
monit may be used to monitor the optimization process. It is invoked once every iteration.
If no monitoring is required, monit may be string 'e04cbk'
[user] = monit(fmin, fmax, sim, n, ncall, serror, vratio, user)

Input Parameters

1:     fmin – double scalar
The smallest function value in the current simplex.
2:     fmax – double scalar
The largest function value in the current simplex.
3:     sim(n + 1n+1,n) – double array
The n + 1n+1 position vectors of the current simplex.
4:     n – int64int32nag_int scalar
nn, the number of variables.
5:     ncall – int64int32nag_int scalar
The number of times that funct has been called so far.
6:     serror – double scalar
The current value of the standard deviation in function values used in termination test (1).
7:     vratio – double scalar
The current value of the linearized volume ratio used in termination test (2).
8:     user – Any MATLAB object
monit is called from nag_opt_uncon_simplex (e04cb) with the object supplied to nag_opt_uncon_simplex (e04cb).

Output Parameters

1:     user – Any MATLAB object
6:     maxcal – int64int32nag_int scalar
The maximum number of function evaluations to be allowed.
Constraint: maxcal1maxcal1.

Optional Input Parameters

1:     n – int64int32nag_int scalar
Default: The dimension of the array x.
nn, the number of variables.
Constraint: n1n1.
2:     user – Any MATLAB object
user is not used by nag_opt_uncon_simplex (e04cb), but is passed to funct and monit. 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.

Input Parameters Omitted from the MATLAB Interface

iuser ruser

Output Parameters

1:     x(n) – double array
The value of xx corresponding to the function value in f.
2:     f – double scalar
The lowest function value found.
3:     user – Any MATLAB object
4:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
An input parameter is invalid.
  ifail = 2ifail=2
maxcal function evaluations have been completed without termination test (1) or (2) passing. Check the coding of funct before increasing the value of maxcal.
  ifail = 999ifail=-999
Internal memory allocation failed.

Accuracy

On a successful exit the accuracy will be as defined by tolf or tolx, depending on which criterion was satisfied first.

Further Comments

Local workspace arrays of fixed lengths (depending on n) are allocated internally by nag_opt_uncon_simplex (e04cb). The total size of these arrays amounts to n2 + 6n + 2 n2 + 6n+2  double elements.
The time taken by nag_opt_uncon_simplex (e04cb) depends on the number of variables, the behaviour of the function and the distance of the starting point from the minimum. Each iteration consists of 11 or 22 function evaluations unless the size of the simplex is reduced, in which case n + 1n+1 function evaluations are required.

Example

function nag_opt_uncon_simplex_example
x = [-1; 1];
tolf = sqrt(nag_machine_precision);
tolx = sqrt(tolf);
maxcal = int64(100);
user = [int64(0)];
[xOut, f, user, ifail] = ...
    nag_opt_uncon_simplex(x, tolf, tolx, @funct, @monit, maxcal, 'user', user)

function [fc, user] = funct(n, xc, user)
  fc = exp(xc(1))*(4*xc(1)*(xc(1)+xc(2))+2*xc(2)*(xc(2) +1)+1);
function [user] = monit(fmin, fmax, sim, n, ncall, serror, vratio, user)
  if (user(1) ~= 0)
    fprintf('\nThere have been %d function calls\n', ncall);
    fprintf('The smallest function value is %10.4f\n', fmin);
    fprintf('The simplex is\n');
    disp(sim);
    fprintf('The standard deviation in function values at the vertices of the simplex is %10.4f\n', serror);
    fprintf('The linearized volume ratio of the current simplex to the starting one is %10.4f\n', vratio);
  end
 

xOut =

    0.5000
   -0.9999


f =

   1.7885e-08


user =

                    0


ifail =

                    0


function e04cb_example
x = [-1; 1];
tolf = sqrt(x02aj);
tolx = sqrt(tolf);
maxcal = int64(100);
user = [int64(0)];
[xOut, f, user, ifail] = e04cb(x, tolf, tolx, @funct, @monit, maxcal, 'user', user)

function [fc, user] = funct(n, xc, user)
  fc = exp(xc(1))*(4*xc(1)*(xc(1)+xc(2))+2*xc(2)*(xc(2) +1)+1);
function [user] = monit(fmin, fmax, sim, n, ncall, serror, vratio, user)
  if (user(1) ~= 0)
    fprintf('\nThere have been %d function calls\n', ncall);
    fprintf('The smallest function value is %10.4f\n', fmin);
    fprintf('The simplex is\n');
    disp(sim);
    fprintf('The standard deviation in function values at the vertices of the simplex is %10.4f\n', serror);
    fprintf('The linearized volume ratio of the current simplex to the starting one is %10.4f\n', vratio);
  end
 

xOut =

    0.5000
   -0.9999


f =

   1.7885e-08


user =

                    0


ifail =

                    0



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