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