Michael Thomas Flanagan's Java Library: Maximization methods

Michael Thomas Flanagan's Java Scientific Library

Maximisation Class: Simplex Maximisation
Maximization 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 maximum of a function, f(a[0],a[1],a[2]...) and the values of the parameters, a[0], a[1], a[2] ..., at the maximum, using a Nelder and Mead simplex approach. A limited number of constraint options are also available. The value of the function to be maximized is supplied via an interface, MaximizationFunction or MaximizationFunction. Either spelling, Maximization or Maximization, may be used but you must be consistent, i.e. class Maximization requires the MaximizationFunction interface.
Maximization is a subclass of Maximization.

import statement/s:

import flanagan.math.Maximisation;
import flanagan.math.MaximisationFunction;

import flanagan.math.Maximization;
import flanagan.math.MaximizationFunction;

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

Related classes

Minimization - minimization of a function
Regression - contains a non-linear regression method based on the Nelder and Mead optimisation procedure.

SUMMARY OF CONSTRUCTORS AND METHODS

Constructors		public Maximization()
Constructors		public Maximisation()
Maximisation	Nelder and Mead Simplex for y = f(a[0],a[1],a[2]...)	public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
		public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
		public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step, double ftol)
		public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step, double ftol)
		public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step, int nmax)
		public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step, int nmax)
		public void nelderMead(MaximizationFunction mf, double[ ] start, double ftol, int nmax)
		public void nelderMead(MaximisationFunction mf, double[ ] start, double ftol, int nmax)
		public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step)
		public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step)
		public void nelderMead(MaximizationFunction mf, double[ ] start, double ftol)
		public void nelderMead(MaximisationFunction mf, double[ ] start, double ftol)
		public void nelderMead(MaximizationFunction mf, double[ ] start, int nmax)
		public void nelderMead(MaximisationFunction mf, double[ ] start, int nmax)
		public void nelderMead(MaximizationFunction mf, double[ ] start)
		public void nelderMead(MaximisationFunction mf, double[ ] start)
	Constrained maximization	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 maximization 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 maximum	public double[] getParamValues()
	Return the function value at maximum	public double getMaximum()
	Suppress message	public void suppressNoConvergenceMessage()

CONSTRUCTORS

public Maximization()
public Maximisation()
Usage: Maximization max = new Maximization()
Maximisation max = new Maximisation()
Creates a new instance of Maximization (or Maximisation) that allows the determination of the maximum value of a function, y[i] = f(a[0], a[1], a[2] ...), provided through the interface MaximizationFunction (or MaximisationFunction), and the values of the function parameters, a[0], a[1], a[2] ..., at the maximum.

METHODS

MaximIZATION
Nelder and Mead Simplex Method
public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step, double ftol)
public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step, int nmax)
public void nelderMead(MaximizationFunction mf, double[ ] start, double ftol, int nmax)
public void nelderMead(MaximizationFunction mf, double[ ] start, double[ ] step)
public void nelderMead(MaximizationFunction mf, double[ ] start, double ftol)
public void nelderMead(MaximizationFunction mf, double[ ] start, int nmax)
public void nelderMead(MaximizationFunction mf, double[ ] start)
public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step, double ftol, int nmax)
public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step, double ftol)
public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step, int nmax)
public void nelderMead(MaximisationFunction mf, double[ ] start, double ftol, int nmax)
public void nelderMead(MaximisationFunction mf, double[ ] start, double[ ] step)
public void nelderMead(MaximisationFunction mf, double[ ] start, double ftol)
public void nelderMead(MaximisationFunction mf, double[ ] start, int nmax)
public void nelderMead(MaximisationFunction mf, double[ ] start)
Usage: max.nelderMead(mf, start, step, ftol, nmax);
This method implements the Nelder and Mead heuristic simplex optimization procedure to maximize the function coded in the interface MaximizationFunction (or MaximisationFunction), 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 maximization. This argument is optional [see below]
The maximization is terminated if the standard deviation, of the values of the function being maximized, 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 maximum
values of the parameters, a[0], a[1], a[2] ..., at the maximum
simplex termination details

Usage: max.nelderMead(mf, start, step, ftol);
As max.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: max.nelderMead(mf, start, step, nmax);
As max.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: max.nelderMead(mf, start, ftol, nmax);
As max.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: max.nelderMead(mf, start, step);
As max.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: max.nelderMead(mf, start, ftol);
As max.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: max.nelderMead(mf, start, nmax);
As max.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: max.nelderMead(mf, start);
As max.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 MAXIMIZED
The mathematical function to maximized, f(a[0], a[1], a[2]), where the array a[] contains the current estimates the parameters for which we require values at the maximum, 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, MaximizationFunction (or MaximisationFunction). The name of this class is the user's choice.
Any constants in the function, to be maximized, that are not included in the set of parameters for which we require a value at the maximum, 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 maximization method, Maximisation.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 Maximisation.

CONSTRAINED MAXIMIZATION
Add a constraint applied to individual parameters
public void addConstraint(int pIndex, int direction, double boundary)
Usage: max.addConstraint(pIndex, direction, boundary);
This method allows the addition of a simple, but often effective constraint, to the maximization. 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 maximization 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 maximized 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 maximized, 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: max.addConstraint(pIndices, plusOrMinus, direction, boundary);
This method allows the addition of a simple, but often effective constraint, to the maximization. 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 maximization procedure will attempt to constrain aa + bb − dd to the interval 2.1*(1 − 10⁻⁴) to 2.1*(1 + 10⁻⁴). Whether the maximization 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 maximization 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 maximized, f, 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:                      max.removeConstraints();
This method removes all constraints.

Reset the penalty weight
public void setPenaltyWeight(double pWeight)
Usage:                      max.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 = max.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: max.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 maximization method is called.

Get the scaling factors
public double[ ] getScale()
Usage: scale = max.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 = max.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:                      max.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 = max.getTolerance();
Returns the tolerance [fTol in the above usages] used in testing for convergence.

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

RESTARTS
Reset the maximum number of restarts
public void setNrestartsMax(int nrm)
Usage:                      max.setNrestartsMax(nrm);
Resets the maximum number of restarts allowed in the Nelder and Mead Simplex procedure. On reaching a maximum 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 = max.getNrestartsMax();
Returns the maximum number of restarts allowed.

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

NUMBER OF ITERATIONS
Reset the maximum number of iterations allowed
public void setNmax(double tol)
Usage:                      max.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:                      nax = max.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 = max.getNiter();
Returns the number of iterations taken.

THE NELDER AND MEAD SIMPLEX COEFFICIENTS
Reset the reflection coefficient
public void setNMreflect(doublereflectC)
Usage:                      max.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 = max.getNMreflect();
Returns the Nelder and Mead simplex reflection coefficient. The default value is 1.0D.

Reset the extension coefficient
public void setNMextend(doubleextendC)
Usage:                      max.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 = max.getNMextend();
Returns the Nelder and Mead simplex extension coefficient. The default value is 2.0D.

Reset the contraction coefficient
public void setNMcontract(doublecontractC)
Usage:                      max.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 = max.getNMcontract();
Returns the Nelder and Mead simplex contraction coefficient. The default value is 0.5D.

PRINT THE MAXIMIZATION RESULTS
public void print( String filename, int prec)
public void print( String filename)
public void print(int prec)
public void print()
Usage: max.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 maximum
the values of the parameters, a[0], a[1], a[2] ... , at the maximum
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 maximum
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:                      max.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:                      max.print(prec);
Outputs a time and date stamped text file, called MaximizationOutputN, 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:                      max.print();
Outputs a time and date stamped text file, called MaximizationOutputN, 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 MAXIMUM
public double getMaximum()
Usage: maxim = max.getMaximum();
Returns the value of the function, f(a[0], a[1], a[2] ... ), at its maximum.

RETURN THE VALUES OF THE FUNCTION PARAMETERS AT THE MAXIMUM
public double[] getParamValues()
Usage: param = max.getParamValues();
Returns the values, at the maximum 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: max.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