Searches for the minimum of a function using the Nelder-Mead simplex algorithm (J.A. Nelder & W. van den Berg).
Options
PRINT = string tokens |
Controls printed output (results, monitoring); default resu |
|---|---|
CALCULATION = expression structures |
Expressions to calculate the target function |
FUNCTIONVALUE = scalar |
Identifier of the scalar, calculated by CALCULATION, whose value is to be minimized |
DATA = any type |
Data to be used with procedure _SIMPLEXFUNCTION |
POINTS = pointer |
Saves the points of the final simplex |
FVALUES = pointer |
Saves the function values at the points |
MAXCYCLE = scalar |
Maximum number of iterations; default 500 |
TOLERANCE = scalar |
Convergence criterion; when standard deviation of function values is lower than TOLERANCE convergence is assumed to be reached; default 1.E-9 |
Parameters
PARAMETER = scalars |
Parameters to be estimated |
|---|---|
LOWERINITIAL = scalars |
Lower starting values for the parameters |
UPPERINITIAL = scalars |
Upper starting values for the parameters |
Description
SIMPLEX uses the simplex algorithm devised by John Nelder & Roger Mead (1965) to search for the minimum of a function. The parameters to be estimated by the minimization are listed by the PARAMETER parameter of SIMPLEX. The optimum function value is found by constructing, and then moving, a “simplex” of points. The lower values for the parameters on the initial simplex are specified using the LOWERINITIAL parameter, and the upper values by the UPPERINITIAL parameter. All of these parameters must be set.
The function can be defined by specifying a list of Genstat calculation structures with the CALCULATION option, similarly to the way in which functions for optimization are specified for the FITNONLINEAR directive (see the Guide to the Genstat Command Language, Part 2 Statistics, Section 3.8). For example, in Section 2.9 of the Guide to Regression, Nonlinear and Generalized Linear Models in Genstat, an exponential model is fitted to a set crop yields. The model is
Yield = A + B * R ** Nitrogen + Residual
where Yield is the yield recorded on a plot, and Nitrogen is the amount of nitrogen fertiliser that was applied. To fit the model using the standard least-squares criterion, we need to calculate the sum of squares of the residual values. This can be done using the expressions E[1] and E[2], defined as follows:
EXPRESSION [VALUE= Fittedvalue = A + B * R**Nitrogen] E[1]
& [VALUE= RSS = SUM ((Yield - Fittedvalue)**2)] E[2]
The FUNCTIONVALUE option defines the function value that is calculated by the expression (similarly to the FUNCTIONVALUE option of the MODEL directive). So, we can now estimate the parameters using the command
SIMPLEX [PRINT=monitoring,results;\
CALCULATION=E[1,2]; FUNCTIONVALUE=RSS]\
A,B,R; LOWER=200,-140,0.98; UPPER=210,-120,0.99
Alternatively, more complicated functions can be specified by defining a procedure _SIMPLEXFUNCTION, which operates similarly to the RESAMPLE procedure which is called by procedures BOOTSTRAP and JACKKNIFE. This is more complicated to specify, but it has the advantage that you can use any Genstat command to obtain the function value (e.g. ANOVA, FIT, SVD and so on). The DATA option is then used to list any data structures that are needed by _SIMPLEXFUNCTION to calculate the value of the function. Details are given in the Methods Section.
The PRINT option controls printed output with the settings:
results |
to print numbers of iterations and function evaluations and the parameter estimates for the final simplex, and |
|---|---|
monitoring |
to print to monitor information showing the progress of the fit. |
By default, PRINT=results.
The scalars specified by the PARAMETER parameter save the estimated values of the parameters. You can also use the POINTS option to save the points of the final simplex (in a pointer containing a variate for each point), and the function values at these points can be saved using the FVALUES option (as a pointer to a set of scalars).
The MAXCYCLE option sets a limit on the number of iterations; by default this is 500. The TOLERANCE option controls the convergence criterion (default 1.E-10). When the standard deviation of the function values around the simplex is less than or equal to Limit the algorithm stops. Limit is defined as TOLERANCE multiplied by the standard deviation of the function values on the initial simplex, or 1.E-10 if the initial variance is zero.
Options: PRINT, CALCULATION, FUNCTIONVALUE, DATA, POINTS, FVALUES, MAXCYCLE, TOLERANCE.
Parameters: PARAMETER, LOWERINITIAL, UPPERINITIAL.
Method
The simplex method of Nelder & Mead (1965) searches for the minimum function value by constructing, and then moving, a “simplex” of points around the parameter space. SIMPLEX uses a revised version of the algorithm which deals with the failed contraction position. This is important if the process is not to become stuck when there are steep curved valleys in the surface. The following steps are possible at each iteration:
| E | worst point replaced by expanded point; |
|---|---|
| FE | worst point replaced by reflected point; |
| C | contracted point on better side when reflected point worst; |
| R | replace worst point by initial expanded point. |
If, after step C, the new point is still the worst point, the points are shrunk to best point, and FC is printed in the monitoring output.
The algorithm thus searches directly for a minimum, rather than for zeros of the derivative of the function. It does not assume knowledge of derivatives, and it generally works rather well when there is some noise in the pointwise evaluation of the function itself. However, it is not fast, particularly in higher dimensions. (See Thompson 1998.)
The procedure _SIMPLEXFUNCTION, which you can use to calculate the function instead of the CALCULATION and FUNCTIONVALUE options, has two options. DATA supplies a pointer containing the data structures specified by the DATA option of SIMPLEX (so, DATA[1] is the first of these structures, DATA[2] is the second, and so on). FUNCTIONVALUE is a scalar, which should be set to the function value. There is one parameter, called PARAMETER. The PROCEDURE statement that defines _SIMPLEXFUNCTION should set option PARAMETER=pointer. The parameters of the function can then be referred to as PARAMETER[1], PARAMETER[2], and so on (and these will be in the same order as in the PARAMETER parameter of SIMPLEX). The definition below has the same effect as the two expressions
EXPRESSION [VALUE= Fittedvalue = A + B * R**Nitrogen] E[1]
& [VALUE= RSS = SUM ((Yield - Fittedvalue)**2)] E[2]
shown in the description.
PROCEDURE [PARAMETER=pointer] '_SIMPLEXFUNCTION'
" calculates the function for SIMPLEX "
OPTION NAME=\
'DATA', "(I: any type) data to calculate the function"\
'FUNCTIONVALUE'; "(O: scalar) returns the function value"\
MODE = p;\
TYPE = *, 'scalar';\
LIST = yes, no
PARAMETER NAME=\
'PARAMETER'; "(I: scalar) parameter values"\
MODE = p;\
TYPE = 'scalar';\
SET = yes;\
DECLARED = yes;\
PRESENT = yes
CALCULATE Fittedvalue = PARAMETER[1] + PARAMETER[2] * PARAMETER[3]**DATA[2]
& FUNCTIONVALUE = SUM((DATA[1] - Fittedvalue)**2)
ENDPROCEDURE
The parameters can then be estimated by the statement
SIMPLEX [PRINT= monitoring,results; DATA=Yield,Nitrogen]\
A,B,R; LOWER=200,-140,0.98; UPPER=210,-120,0.99
Action with RESTRICT
The effects of restrictions on the data variables will depend on how the calculation is defined (by the CALCULATION option or within the _SIMPLEXFUNCTION procedure).
References
Nelder, J.A. & Mead, R. (1965). A simplex method for function minimization. Computer Journal, 7, 303-333.
Thompson, J.R. (2000). Simulation: a Modeler’s Approach. Wiley, New York.
See also
Directive: FITNONLINEAR.
Procedures: FPARETOSET, MINIMIZE, MIN1DIMENSION.
Commands for: Regression analysis.
Example
CAPTION 'SIMPLEX example',\
'Data from Section 5.5 of the Introduction.'; STYLE=meta,plain
VARIATE Nitrogen,Yield
READ Nitrogen,Yield
0 60 0 73 0 77 0 72
50 125 50 144 50 145 50 116
100 152 100 154 100 160 100 141
150 182 150 167 150 181 150 185
200 198 200 188 200 189 200 182 :
EXPRESSION [VALUE= Fittedvalue = A + B * R**Nitrogen] E[1]
& [VALUE= RSS = SUM ((Yield - Fittedvalue)**2)] E[2]
CAPTION 'Analysis by FITNONLINEAR (three nonlinear parameters).'
MODEL Yield; FITTED = Fittedvalue
RCYCLE A,B,R; INITIAL=100,-100,0.95; UPPER=*,*,1
FITNONLIN [CALCULATION=E[1]]
CAPTION 'Parameter estimation using SIMPLEX with the CALCULATION option.'
SIMPLEX [PRINT= monitoring,results; CALCULATION=E[1,2]; FUNCTIONVALUE=RSS]\
A,B,R; LOWER=200,-140,0.98; UPPER=210,-120,0.99
CAPTION 'Parameter estimation using SIMPLEX and _SIMPLEXFUNCTION.'
PROCEDURE [PARAMETER=pointer] '_SIMPLEXFUNCTION'
" calculates the function for SIMPLEX "
OPTION NAME=\
'DATA', "(I: any type) data to calculate the function"\
'FUNCTIONVALUE';"(O: scalar) returns the function value"\
MODE = p;\
TYPE = *, 'scalar';\
LIST = yes, no
PARAMETER NAME=\
'PARAMETER'; "(I: scalar) parameter values"\
MODE = p;\
TYPE = 'scalar'; \
SET = yes;\
DECLARED = yes;\
PRESENT = yes
CALCULATE Fittedvalue = PARAMETER[1] + PARAMETER[2] * PARAMETER[3]**DATA[2]
& FUNCTIONVALUE = SUM((DATA[1] - Fittedvalue)**2)
ENDPROCEDURE
SIMPLEX [PRINT= monitoring,results; DATA=Yield,Nitrogen]\
A,B,R; LOWER=200,-140,0.98; UPPER=210,-120,0.99