Michael Thomas Flanagan's Java Library: Minimisation methods

Michael Thomas Flanagan's Java Scientific Library

Minimisation Class: Simplex Minimisation
Minimization Class:

Last update: 23 September 2010 PERMISSION TO USE
Main Page of Michael Thomas Flanagan's Java Scientific Library

This class contains the method for obtaining the minimum of a function, f(a[0],a[1],a[2]...) and the values of the parameters, a[0], a[1], a[2] ..., at the minimum, using a Nelder and Mead simplex approach. A limited number of constraint options are also available. The value of the function to be minimized is supplied via an interface, MinimisationFunction or MinimizationFunction. Either spelling, Minimization or Minimisation, may be used but you must be consistent, i.e. class Minimization requires the MinimizationFunction interface.
Minimization is a subclass of Minimisation.

import statement/s:

import flanagan.math.Minimisation;
import flanagan.math.MinimisationFunction;

import flanagan.math.Minimization;
import flanagan.math.MinimizationFunction;

Summary table of constructors and methods
Details of constuctors and methods
Example program demonstrating the use of Minimisation.
Last update of the source code for Minimisation.java: 23 September 2010.
Last update of the source code for Minimization.java: May 2008.
Last update of the source code for MinimisationFunction.java:April 2004.
Last update of the source code for MinimizationFunction.java: May 2008.
Other classes, from this library, used by this class.
Main Page of Michael Thomas Flanagan's Java Scientific Library.

Related classes

SUMMARY OF CONSTRUCTORS AND METHODS

Constructors		public Minimization()
Constructors		public Minimisation()
Minimisation	Nelder and Mead Simplex for y = f(a[0],a[1],a[2]...)	public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
		public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
		public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step, double ftol)
		public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step, double ftol)
		public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step, int nmax)
		public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step, int nmax)
		public void nelderMead(MinimizationFunction mf, double[ ] start, double ftol, int nmax)
		public void nelderMead(MinimisationFunction mf, double[ ] start, double ftol, int nmax)
		public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step)
		public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step)
		public void nelderMead(MinimizationFunction mf, double[ ] start, double ftol)
		public void nelderMead(MinimisationFunction mf, double[ ] start, double ftol)
		public void nelderMead(MinimizationFunction mf, double[ ] start, int nmax)
		public void nelderMead(MinimisationFunction mf, double[ ] start, int nmax)
		public void nelderMead(MinimizationFunction mf, double[ ] start)
		public void nelderMead(MinimisationFunction mf, double[ ] start)
	Constrained minimisation	public void addConstraint(int pIndex, int direction, double boundary)
		public void addConstraint(int[] pIndices, double[] plusOrMinus, int direction, double boundary)
		public void addConstraint(int[] pIndices, int[] plusOrMinus, int direction, double boundary)
		public void removeConstraints()
		public void setPenaltyWeight(double pWeight)
		public double getPenaltyWeight()
		public void setConstraintTolerance(double tolerance)
	Scaling the initial estimates	public void setScale(int opt)
		public void setScale(double[] opt)
		public double[ ] getScale()
	Convergence tests	public boolean getConvStatus()
		public void setTolerance(double tol)
		public int getTolerance()
		public double getSimplexSd()
	Restarts	public void setNrestartsMax(int nrm)
		public int getNrestartsMax()
		public int getNrestarts()
	Number of iterations	public void setNmax(int nMax)
		public int getNmax()
		public int getNiter()
	Nelder and Mead Simplex Coefficients	public void setNMreflect(double reflectC)
		public double getNMreflect()
		public void setNMextend(double extendC)
		public double getNMextend()
		public void setNMcontract(double contractC)
		public double getNMcontract()
	Print the minimisation results	public void print( String filename, int prec)
		public void print( String filename)
		public void print(int prec)
		public void print()
	Return the parameter values, a[i], at minimum	public double[] getParamValues()
	Return the function value at minimum	public double getMinimum()
	Suppress message	public void suppressNoConvergenceMessage()

CONSTRUCTORS

public Minimization()
public Minimisation()
Usage: Minimization min = new Minimization()
Minimisation min = new Minimisation()
Creates a new instance of Minimization (or Minimisation) that allows the determination of the minimum value of a function, y[i] = f(a[0], a[1], a[2] ...), provided through the interface MinimizationFunction (or MinimisationFunction), and the values of the function parameters, a[0], a[1], a[2] ..., at the minimum.

METHODS

MINIMIZATION
Nelder and Mead Simplex Method
public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step, double ftol)
public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step, int nmax)
public void nelderMead(MinimizationFunction mf, double[ ] start, double ftol, int nmax)
public void nelderMead(MinimizationFunction mf, double[ ] start, double[ ] step)
public void nelderMead(MinimizationFunction mf, double[ ] start, double ftol)
public void nelderMead(MinimizationFunction mf, double[ ] start, int nmax)
public void nelderMead(MinimizationFunction mf, double[ ] start)
public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step, double ftol)
public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step, int nmax)
public void nelderMead(MinimisationFunction mf, double[ ] start, double ftol, int nmax)
public void nelderMead(MinimisationFunction mf, double[ ] start, double[ ] step)
public void nelderMead(MinimisationFunction mf, double[ ] start, double ftol)
public void nelderMead(MinimisationFunction mf, double[ ] start, int nmax)
public void nelderMead(MinimisationFunction mf, double[ ] start)
Usage: min.nelderMead(mf, start, step, ftol, nmax);
This method implements the Nelder and Mead heuristic simplex optimization procedure to minimize the function coded in the interface MinimizationFunction (or MinimisationFunction), mf in the above usage.
Reference: Nelder, J.A. and Mead, R. (1965) Computer Journal, 7, 308-313.

The array, start, holds the initial estimates of the parameters whose best estimates are required.

The array, step, holds the initial step sizes for each of the parameters. These step sizes are used to construct the initial simplex. They may differ for each parameter. This argument is optional [see below]

The double, ftol, is the tolerance used in determining the convergence of the minimization. This argument is optional [see below]
The minimization is terminated if the standard deviation, of the values of the function being minimized, at the apices of the simplex is less than the tolerance, ftol.

The integer, nmax, is the maximum number of iterations allowed by the simplex procedure. This argument is optional [see below]. If the maximum number of iterations is reached the method returns the current estimates at that point in the iteration.

The procedure for coding the function, e.g. g, is described below and is illustrated in the Example Program See below, or summary table above, for methods to obtain

value of the fuction, f(a[0], a[1], a[2] ... ), at the minimum
values of the parameters, a[0], a[1], a[2] ..., at the minimum
simplex termination details

Usage: min.nelderMead(mf, start, step, ftol);
As min.nelderMead(mf, start, step, ftol, nmax) above with the exception that the maximum number of iterations is not provided as an argument. A default value of 3000 is used.

Usage: min.nelderMead(mf, start, step, nmax);
As min.nelderMead(mf, start, step, ftol, nmax) above with the exception that the terrmination tolerance is not provided as an argument. A default value of 1e-9 is used.

Usage: min.nelderMead(mf, start, ftol, nmax);
As min.nelderMead(mf, start, step, ftol, nmax) above with the exception that the initial simplex step values are not provided as an argument. A default value of 0.5 times the corresponing initial estimate [start] is used for the steps for all parameters.

Usage: min.nelderMead(mf, start, step);
As min.nelderMead(mf, start, step, ftol, nmax) above with the exception that the maximum number of iterations and the termination tolerance are not provided as arguments. Default values of 1e-9 and 3000 respectively are used.

Usage: min.nelderMead(mf, start, ftol);
As min.nelderMead(mf, start, step, ftol, nmax) above with the exception that the initial simplex step sizes and the maximum number of iterations are not provided as arguments. Default values of 0.5 times the corresponing initial estimate [start] for all parameters and 3000 respectively are used.

Usage: min.nelderMead(mf, start, nmax);
As min.nelderMead(mf, start, step, ftol, nmax) above with the exception that the initial simplex step sizes and the termination tolerance are not provided as arguments. Default values of 0.5 times the corresponing initial estimate [start] for all parameters and 1e-9 respectively are used.

Usage: min.nelderMead(mf, start);
As min.nelderMead(mf, start, step, ftol, nmax) above with the exception that the initial simplex step sizes, the termination tolerance and the maximum number of iterations are not provided as arguments. Default values of 0.5 times the corresponing initial estimate [start] for all parameters, 1e-9 and 3000 respectively are used.

CODING THE FUNCTION TO BE MINIMIZED
The mathematical function to minimized, f(a[0], a[1], a[2]), where the array a[] contains the current estimates the parameters for which we require values at the minimum, must be coded as a method
public double function(double[ ] parameters)
The method, function, must have the above signature, i.e. name, type and argument list, and be a method in a class which must implement the interface, MinimizationFunction (or MinimisationFunction). The name of this class is the user's choice.
Any constants in the function, to be minimized, that are not included in the set of parameters for which we require a value at the minimum, i.e. constants of known fixed value, are not transferred to the function via the argument list but should be declared as members of the class of which function(x) is a member. Their values may be set in that declaration and can be reset within the calling program (see Example Program

The function is passed to the minimization method, Minimisation.nelderMead(...) as an instance of the class containing the method function(x) [f() in the above example but this instance may be named at the user's choice]. This instance should be created in the method that calls simplex(. . .). This procedure can be seen more clearly in the Example program demonstrating the use of Minimization.

CONSTRAINED MINIMIZATION
Add a constraint applied to individual parameters
public void addConstraint(int pIndex, int direction, double boundary)
Usage: min.addConstraint(pIndex, direction, boundary);
This method allows the addition of a simple, but often effective constraint, to the minimization. A parameter may be constrained either to take only values above a certain value or below a certain value. The arguments of the method, [in the above usage], are:

pIndex: the index of the parameter to be constrained [remember, indices start at 0, i.e. the first parameter to be estimated as an index 0]
direction:
- direction set to −1: the constraint applies below the constraint boundary, i.e. the parameter may only take values above the constraint boundary
- direction set to +1: the constraint applies above the constraint boundary, i.e. the parameter may only take values below the constraint boundary
- direction set to 0: The parameter will be constrained to a single constraint value (boundary) within a tolerance of 0.01% of the constraint value, i.e. a parameter with a supplied boundary value of 2.1 will be constrained to the interval 2.1*(1 − 10⁻⁴) to 2.1*(1 + 10⁻⁴). Whether the minimization can achieve this will depend on the tolerance, 10⁻⁴, exceeding the rounding error. This tolerance may be reset using the setConstraintTolerance method. This is not a sensible way to fix a value. It would be more sensible to rewrite the function to be minimized with this parameter set at a fixed value, e.g. 2.1 in this example. The value of this option is in constraining a sum of parameters (see immediately below).
boundary: the boundary value, i.e. the value of the current estimate of the parameter beyond which the constraint applies.

More than one constraint may be added and more than one constraint may be applied to the same parameter
If an attempt to enter a constrained region is made the value of the function is not calculated but is replaced by the previously calculated value plus a penalty term equal to a penalty weight [see setPenaltyWeight below] multiplied by the square of the attempted estimate of the parameter entering the constraint region minus the constraint boundary value, i.e. if any set constraint is violated the function, to be minimized, fm, is replaced by

where there are q parameters constrained to lay above lower boundaries, l_i, r parameters constrained to lay below upper boundaries, u_i and s parameters constrained to fixed values, f_i within a tolerance, t, H(arg) is the Heaviside step function taking the value of zero for arg < or = 0 and a value of 1 for arg >0, P_w is the penalty weight and fm_{previous value} is the last calculated value of fm in which no constraint boundaries were violated.

Add a constraint applied to a summation of some or all parameters
public void addConstraint(int[] pIndices, double[] plusOrMinus, int direction, double boundary)
public void addConstraint(int[] pIndices, int[] plusOrMinus, int direction, double boundary)
Usage: min.addConstraint(pIndices, plusOrMinus, direction, boundary);
This method allows the addition of a simple, but often effective constraint, to the minimization. A sum of some or all of the parameters may be constrained either to take only values above a certain value or below a certain value. The arguments of the method, [in the above usage], are:

pIndices: the indices of the parameter to be included in the constraint [remember, indices start at 0, i.e. the first parameter to be estimated as an index 0]
plusOrMinus: the values by which the individual parameters in the sum should be multiplied.
direction:
- direction set to −1: the constraint applies below the constraint boundary, i.e. the parameter may only take values above the constraint boundary
- direction set to +1: the constraint applies above the constraint boundary, i.e. the parameter may only take values below the constraint boundary
- direction set to 0: The designated sum of parameters will be constrained to a single constraint value (boundary) within a tolerance of 0.01% of the constraint value, i.e. if three parameters aa, bb and dd are to be constrained as aa + bb − dd = 2.1 the minimization procedure will attempt to constrain aa + bb − dd to the interval 2.1*(1 − 10⁻⁴) to 2.1*(1 + 10⁻⁴). Whether the minimization can achieve this will depend on the tolerance, 10⁻⁴, exceeding the rounding error. This tolerance may be reset using the setConstraintTolerance method.

boundary:

For example, if, for a minimization with four parameters aa, bb, cc and dd, whose initial estimates were set in start[0], start[1], start[2] and start[3] respectively, one wishes to apply the constraint,
          1.1aa − 2.3bb + 5.7dd > 13.4,
the addConstraint method would be called with:
          pIndices[0] = 0, pIndices[1] = 1, pIndices[2] = 3;
          plusOrMinus[0] = 1.1, plusOrMinus[1] = −2.3, plusOrMinus[2] = 5.7;
          direction = −1;
          boundary = 13.4;

More than one constraint sum may be added.
If an attempt to enter a constrained region is made the value of the function is not calculated but is replaced by the previously calculated value plus a penalty term equal to a penalty weight [see setPenaltyWeight below] multiplied by the square of the attempted estimate of the constraint sum minus the constraint boundary value, i.e. if any set constraint is violated the function, to be minimized, fm, is replaced by

where there are q parameters constrained to lay above lower boundaries, l_i, r parameters constrained to lay below upper boundaries, u_i and s parameters constrained to fixed values, f_i within a tolerance, t, H(arg) is the Heaviside step function taking the value of zero for arg < or = 0 and a value of 1 for arg >0, P_w is the penalty weight and fm_{previous value} is the last calculated value of fm in which no constraint boundaries were violated.

Remove all constraints
public void removeConstraints()
Usage:                      min.removeConstraints();
This method removes all constraints.

Reset the penalty weight
public void setPenaltyWeight(double pWeight)
Usage:                      min.setPenaltyWeight(pWeight);
This method resets the penalty weight [pWeight in the above usage] used by the constraint procedure [see addConstraint above]. The default value is 1e30.

Return the penalty weight
public double getPenaltyWeight()
Usage:                      pWeight = min.getPenaltyWeight();
Returns the penalty weight used by the constraint procedure [see addConstraint above]. The default value is 1e30.

Reset the constraint tolerance
public void setConstraintTolerance(double tolerance)
Usage:                      reg.setConstraintTolerance(tolerance);
Resets the tolerance value used by the constraint procedure for multiple parameters and a fixed constraint value [see addConstraint immediately above]. The default value is 10⁻⁴.

SCALING OF THE INITIAL ESTIMATES
Reset the scaling factors applied to the initial estimates
public void setScale(int opt)
public void setScale(double[] opt)
Usage: min.setScale(opt);
Resets the factors by which the initial estimates are scaled. The options [opt in the above usage] may take values:

opt = an int of value = 0: No scaling occurs
opt = an int of value = 1; All estimates are scaled to unity
opt = a double[ ] (one dimensional array of length equal to the number of initial estimates): The estimates are scaled to values in the array opt

The default value is opt=0, i.e. no scaling. Scaling is advised if there are significant disparities between some of the magnitudes of the initial estimates. If the default option is to be overriden, setScale must be called before the minimization method is called.

Get the scaling factors
public double[ ] getScale()
Usage: scale = min.getScale();
Returns the scaling factors applied to the initial estimates used by the Nelder and Mead Simplex method.

CONVERGENCE TEST
Check whether convergence achieved
public boolean getConvStatus()
Usage:                      convergeCheck = min.getConvStatus();
Returns true if convergence was achieved and false if convergence not achieved before maximum number of iterations. If false the current values of the function and its parameters at the maximum number of iterations iterations are returned by nelderMead.

Reset the tolerance value
public void setTolerance(double fTol)
Usage:                      min.setTolerance(fTol);
Resets the tolerance [fTol in the above usages] used in testing for convergence. Default value is 10e-13.

Get the tolerance value
public int getTolerance()
Usage:                      fTol = min.getTolerance();
Returns the tolerance [fTol in the above usages] used in testing for convergence.

Get the simplex standard deviation
public double getSimplexSd()
Usage:                      simplexSd = min.getSimplexSd();
Returns the standard deviation of the simplex at the minimum.

RESTARTS
Reset the maximum number of restarts
public void setNrestartsMax(int nrm)
Usage:                      min.setNrestartsMax(nrm);
Resets the maximum number of restarts allowed in the Nelder and Mead Simplex procedure. On reaching a minimum the procedure will be restarted this number [nrm in the above usage] of times. The default option is 3.

Get the maximum number of restarts allowed
public int getNrestartMax()
Usage:                      nrm = min.getNrestartsMax();
Returns the maximum number of restarts allowed.

Get the number of restarts that occured
public int getNrestart()
Usage:                      nr = min.getNrestarts();
Returns the number of restarts that occured.

NUMBER OF ITERATIONS
Reset the maximum number of iterations allowed
public void setNmax(double tol)
Usage:                      min.setNmax(nMax);
Resets the maximum number of iterations allowed in the Nelder and Mead simplex procedure to the method argument [nMax in the above usage]. The default value is 3000.

Get the maximum number of iterations allowed
public int getNmax()
Usage:                      nim = min.getNmax();
Returns the maximum number of iterations allowed in the Nelder and Mead simplex procedure.

Get the number of iterations taken
public int getNiter()
Usage:                      nr = min.getNiter();
Returns the number of iterations taken.

THE NELDER AND MEAD SIMPLEX COEFFICIENTS
Reset the reflection coefficient
public void setNMreflect(doublereflectC)
Usage:                      min.setNMreflect(reflectC);
Resets the Nelder and Mead simplex reflection coefficient. The default value is 1.0D.

Get the reflection coefficient
public double getNMreflect()
Usage:                      reflectC = min.getNMreflect();
Returns the Nelder and Mead simplex reflection coefficient. The default value is 1.0D.

Reset the extension coefficient
public void setNMextend(doubleextendC)
Usage:                      min.setNMextend(extendC);
Resets the Nelder and Mead simplex extension coefficient. The default value is 2.0D.

Get the reflection coefficient
public double getNMextend()
Usage:                      extedC = min.getNMextend();
Returns the Nelder and Mead simplex extension coefficient. The default value is 2.0D.

Reset the contraction coefficient
public void setNMcontract(doublecontractC)
Usage:                      min.setNMcontract(contractC);
Resets the Nelder and Mead simplex contraction coefficient. The default value is 0.5D.

Get the contraction coefficient
public double getNMcontract()
Usage:                      contractC = min.getNMcontract();
Returns the Nelder and Mead simplex contraction coefficient. The default value is 0.5D.

PRINT THE MINIMIZATION RESULTS
public void print( String filename, int prec)
public void print( String filename)
public void print(int prec)
public void print()
Usage: min.print(filename, prec);
Outputs a time and date stamped text file, whose name is in the String filename, to which is written:

the value of the function, f(a[0], a[1], a[2] ...), at the minimum
the values of the parameters, a[0], a[1], a[2] ... , at the minimum
the best estimates of the unknown parameters
the initial estimates
the initial step sizes
the number of iterations
the maximum number of iterations allowed
the number of restarts
the maximum number of restarts allowed
the standard deviation of the simplex at the minimum
the convergence tolerance

All floating point outputted values have had their mantissae truncted and rounded to prec decimal places. No truncation occurs if a minus value is assigned to prec

Usage:                      min.print(filename);
Outputs a time and date stamped text file, whose name is in the String filename, to which is written the same data has listed above. A default option of 4 decimal places is used in the truncation and rounding method.

Usage:                      min.print(prec);
Outputs a time and date stamped text file, called MinimizationOutputN, to which is written the same data has listed above. The file name final integer, N is incremeted by 1 on creating a new file without having deleted the previous one. The argument prec has the same meaning as above.

Usage:                      min.print();
Outputs a time and date stamped text file, called MinimizationOutputN, to which is written the same data has listed above. The file name final integer, N is incremeted by 1 on creating a new file without having deleted the previous one. A default option of 4 decimal places is used in the truncation and rounding method.

RETURN THE VALUE OF THE FUNCTION AT THE MINIMUM
public double getMinimum()
Usage: minim = min.getMinimum();
Returns the value of the function, f(a[0], a[1], a[2] ... ), at its minimum.

RETURN THE VALUES OF THE FUNCTION PARAMETERS AT THE MINIMUM
public double[] getParamValues()
Usage: param = min.getParamValues();
Returns the values, at the minimum of the function, f(a[0], a[1], a[2] ... ), of the parameters, a[0], a[1], a[2] . . .

SUPPRESS THE NO CONVERGENCE ERROR MESSAGE
public void suppressNoConvergenceMessage()
Usage: min.suppressNoConvergenceMessage();
Calling this method suppresses the printing to screen of the message saying that convergence has not been achieved that is displayed when the convergence criteia are not satisfied. USE WITH CARE!! It has been included to cover those situations in which it is known that the convergence tolerance has been set to be very tight, in general, but where it is inconvenient to reset it for individual cases.

EXAMPLE PROGAM

Download MinimisationExample.java

OTHER CLASSES USED BY THIS CLASS

This class uses the following classes in this library:

PERMISSION TO USE

Permission to use, copy and modify this software and its documentation for NON-COMMERCIAL purposes is granted, without fee, provided that an acknowledgement to the author, Dr Michael Thomas Flanagan at www.ee.ucl.ac.uk/~mflanaga, appears in all copies and associated documentation or publications.

Public listing of the source codes on the internet is not permitted.

Redistribution of the source codes or of the flanagan.jar file is not permitted.

Redistribution in binary form of all or parts of these classes is not permitted.

Dr Michael Thomas Flanagan makes no representations about the suitability or fitness of the software for any or for a particular purpose. Dr Michael Thomas Flanagan shall not be liable for any damages suffered as a result of using, modifying or distributing this software or its derivatives.

This page was prepared by Dr Michael Thomas Flanagan