SIMPLEX procedure

Searches for the minimum of a function using the Nelder-Mead simplex algorithm (J.A. Nelder & W. van den Berg).


Options

PRINT = strings
Controls printed output (results, monitoring); default resu

CALCULATION = expressions
Expressions to calculate the target function

FUNCTION = 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 GenStat, Part 2 Statistics, Section 3.8). For example, in Section 3.7. of the Introduction to 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 FUNCTION option defines the function value that is calculated by the expression (similarly to the FUNCTION option of the MODEL directive). So, we can now estimate the parameters using the command

SIMPLEX [PRINT=monitoring,results;\

           CALCULATION=E[1,2]; FUNCTION=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, FUNCTION, 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 FUNCTION 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). FUNCTION 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"\

  'FUNCTION'; "(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]

& FUNCTION = 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.