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; or 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 Maximisation - maximisation 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 Minimization() 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, 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); 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−4) to 2.1*(1 + 10−4). Whether the minimization can achieve this will depend on the tolerance, 10−4, 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, li, r parameters constrained to lay below upper boundaries, ui and s parameters constrained to fixed values, fi 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, Pw is the penalty weight and fmprevious 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−4) to 2.1*(1 + 10−4). Whether the minimization can achieve this will depend on the tolerance, 10−4, exceeding the rounding error. This tolerance may be reset using the setConstraintTolerance method. boundary: the boundary value, i.e. the value of the current estimate of the parameter beyond which the constraint applies. 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, li, r parameters constrained to lay below upper boundaries, ui and s parameters constrained to fixed values, fi 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, Pw is the penalty weight and fmprevious 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−4. 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: Fmath FileOutput 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
