 java.lang.Object

 ij.measure.Minimizer

public class Minimizer extends java.lang.Object
Minimizer based on NelderMead simplex method (also known as polytope method), including the 'outside contraction' as described in: J.C. Lagarias, J.A. Reeds, M.H. Wright, P. Wright: Convergence properties of the NelderMead simplex algorithm in low dimensions. SIAM J. Optim. 9, 112147 (1998). Differences w.r.t. this publication:  If outside contraction is rejected, instead of shrinking the whole simplex, an inside contraction is tried first. Own experiments show that this results in slightly better performance for some test functions (Perm, Mc Kinnon's function with tau=2, theta=6, Osborne1 curvefitting problem). In most cases, there is no difference, however.  This implementation does not include any 'ordering rules' in case of equal function values.  When checking for convergence, a special iteration step may be performed, improving the best vertex of the simplex. Reinitialization within a minimization run: In some cases, the simplex algorithm may fail to find the minimum or the convergence check might stop it prematurely. Therefore, the search is initialized again, keeping the best vertex of the simplex and setting the other vertices to random values, but keeping variations of the parameters w.r.t. the best vertex at a similar value. If reinitializing the simplex does not lead to a significant improvement, the value is accepted as true (local) minimum. Multiple minimization runs: In spite of reinitializing (see above), there are rare cases where minimization is stopped too early. Also, minimization may result in a local minimum. Therefore, unless determined otherwise by setting 'setRestarts', two minimization runs with different initialization of the simplex are started in parallel threads. If the results don't agree within the error limit, two more minimization runs are started. This is repeated until the two best results agree within the error limits or the number of restarts (determined by 'setRestarts'; default 2, i.e., up to 3 runs with two threads each) is exceeded. This does not guarantee that the minimum is a global minimum, however: A local minimum will be accepted if the minimizer finds a local minimum twice (or two different local minima with the same function value within the error bounds), but no better minimum has been found at that time. The usersupplied target function should return NaN for outofbounds parameters instead of a high (penalty) value (minimization is faster and more reliable with NaNs). The region where the function is defined (e.g. not returning NaN) must be convex. Sharp corners of the region where the function value is defined (especially in higher dimensions) may cause a problem with finding suitable test points when (re)initializing the simplex. If all attempts to find initial points result in NaN, the status returned is INITIALIZATION_FAILURE. Versions: Michael Schmid 20120130: first version, based on previous CurveFitter 20121120: mor tries to find initial params not leading to NaN 20130924: 50% higher maximum iteration count, and never uses more than 0.4*maxIter iterations per minimization to avoid trying too few sets of initial params 20131013: setStatusAndEscape to show iterations and enable abort by ESC 20140916: normalization bug fixed. makeNewParamVariations checks for paramResolutions


Field Summary
Fields Modifier and Type Field Description static int
ABORTED
Status returned: aborted by call to abort method.static int
INITIALIZATION_FAILURE
Status returned: Could not initialize the simplex because either the initialParams resulted in the target function returning NaN or all attempts to find starting parameters for the other simplex points resulted in the target function returning NaN.static int
MAX_ITERATIONS_EXCEEDED
Status returned: no convergence detected after maximum iteration countstatic int
MAX_RESTARTS_EXCEEDED
Status returned: not two equal solutions after maximum number of restartsstatic int
REINITIALIZATION_FAILURE
Status returned: Could not reinitialize the simplex because all attempts to find restarting parameters resulted in the target function returning NaN.static java.lang.String[]
STATUS_STRING
Strings describing the status codesstatic int
SUCCESS
Status returned: successful completion

Constructor Summary
Constructors Constructor Description Minimizer()

Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
abort()
Aborts minimization.int
getCompletedMinimizations()
Get number of minimizations completed (i.e.double
getFunctionValue()
Get the value of the minimum, i.e.int
getIterations()
Get number of iterations performed (includes all restarts).int
getMaxIterations()
Get maximum number of iterations allowed.int
getMaxRestarts()
Get maximum number of minimization restarts to dodouble[]
getParams()
Get the result, i.e., the set of parameter values (i.e., variable values) from the best corner of the simplex.int
minimize(double[] initialParams, double[] initialParamVariations)
Perform minimization with the gradientenhanced simplex method once or a few times, depending on the value of 'restarts'.int
minimizeOnce(double[] initialParams, double[] initialParamVariations)
Perform minimization with the simplex method once, including reinitialization until we have a stable solution.void
setExtraArrayElements(int numExtraArrayElements)
Add a given number of extra elements to array of parameters (independent vaiables) for private use in the user function.void
setFunction(UserFunction userFunction, int numParams)
Set the the target function, i.e.void
setMaxError(double maxRelError)
Sets the accuracy of convergence.void
setMaxError(double maxRelError, double maxAbsError)
Sets the accuracy of convergence.void
setMaximumThreads(int numThreads)
Call setMaximuThreads(1) to avoid multithreaded execution (in case the userprovided target function does not allow moultithreading).void
setMaxIterations(int x)
Set maximum number of iterations allowed (including all restarts and all threads).void
setMaxRestarts(int n)
Set maximum number of minimization restarts to do.void
setParamResolutions(double[] paramResolutions)
Set the resolution of the parameters, for problems where the target function is not smooth but suffers from numerical noise.void
setRandomSeed(int n)
Set a seed to initialize the random number generator, which is used for initialization of the simplex.void
setStatusAndEsc(java.lang.String ijStatusString, boolean checkEscape)
Create output on the number of iterations in the ImageJ Status line, e.g.



Field Detail

SUCCESS
public static final int SUCCESS
Status returned: successful completion See Also:
 Constant Field Values

INITIALIZATION_FAILURE
public static final int INITIALIZATION_FAILURE
Status returned: Could not initialize the simplex because either the initialParams resulted in the target function returning NaN or all attempts to find starting parameters for the other simplex points resulted in the target function returning NaN. No minimization was possible. See Also:
 Constant Field Values

ABORTED
public static final int ABORTED
Status returned: aborted by call to abort method. See Also:
 Constant Field Values

REINITIALIZATION_FAILURE
public static final int REINITIALIZATION_FAILURE
Status returned: Could not reinitialize the simplex because all attempts to find restarting parameters resulted in the target function returning NaN. Reinitialization is needed to obtain a reliable result; so the result may be inaccurate or wrong. See Also:
 Constant Field Values

MAX_ITERATIONS_EXCEEDED
public static final int MAX_ITERATIONS_EXCEEDED
Status returned: no convergence detected after maximum iteration count See Also:
 Constant Field Values

MAX_RESTARTS_EXCEEDED
public static final int MAX_RESTARTS_EXCEEDED
Status returned: not two equal solutions after maximum number of restarts See Also:
 Constant Field Values

STATUS_STRING
public static final java.lang.String[] STATUS_STRING
Strings describing the status codes


Method Detail

setFunction
public void setFunction(UserFunction userFunction, int numParams)
Set the the target function, i.e. function whose value should be minimized. Parameters:
userFunction
 The class having a function to minimize (implementing the UserFunction interface). This function must allow simultaneous calls in multiple threads unless setMaximumThreads(1); has been called. Note that the function will be called with at least numParams+1 array elements; the last one is needed to store the function value. Further array elements for private use in the user function may be added by calling setExtraArrayElements.numParams
 Number of independent variables (also called parameters) of the function.

minimize
public int minimize(double[] initialParams, double[] initialParamVariations)
Perform minimization with the gradientenhanced simplex method once or a few times, depending on the value of 'restarts'. Running it several times helps to reduce the probability of finding local minima or accepting one of the rare results where the minimizer has got stuck before finding the true minimum. We are using two threads and terminate after two equal results. Thus, apart from the overhead of starting a new thread (typically < 1 ms), for unproblematic minimization problems on a dualcore machine this is almost as fast as running it once. Use 'setFunction' first to define the function and number of parameters. Afterwards, use the 'getParams' method to access the result. Parameters:
initialParams
 Array with starting values of the parameters (variables). When null, the starting values are assumed to be 0. The target function must be defined (not returning NaN) for the values specified as initialParams.initialParamVariations
 Parameters (variables) are initially varied by up to +/ this value. If not given (null), initial variations are taken as 10% of initial parameter value or 0.01 for parameters that are zero. When this array is given, all elements must be positive (nonzero). If one or several initial parameters are zero, is advisable to set the initialParamVariations array to useful values indicating the typical order of magnitude of the parameters. For target functions with only one minimum, convergence is fastest with large values of initialParamVariations, so that the expected value is within initialParam+/initialParamVariations. If local minima can occur, it is best to use a value close to the expected global minimum, and rather small initialParamVariations, much lower than the distance to the nearest local minimum. Returns:
 status code; SUCCESS if two attempts have found minima with the same value (within the error bounds); so a minimum has been found with very high probability.

minimizeOnce
public int minimizeOnce(double[] initialParams, double[] initialParamVariations)
Perform minimization with the simplex method once, including reinitialization until we have a stable solution. Use the 'getParams' method to access the result. Parameters:
initialParams
 Array with starting values of the parameters (variables). When null, the starting values are assumed to be 0. The target function must be defined (not returning NaN) for the values specified as initialParams.initialParamVariations
 Parameters (variables) are initially varied by up to +/ this value. If not given (null), iniital variations are taken as 10% of inial parameter value or 0.01 for parameters that are zero. When this array is given, all elements must be positive (nonzero). If one or several initial parameters are zero, is advisable to set the initialParamVariations array to useful values indicating the typical order of magnitude of the parameters. For target functions with only one minimum, convergence is fastest with large values of initialParamVariations, so that the expected value is within initialParam+/initialParamVariations. If local minima can occur, it is best to use a value close to the expected global minimum, and rather small initialParamVariations, much lower than the distance to the nearest local minimum. Returns:
 status code; SUCCESS if it is considered likely that a minimum of the target function has been found.

getParams
public double[] getParams()
Get the result, i.e., the set of parameter values (i.e., variable values) from the best corner of the simplex. Note that the array returned may have more elements than numParams; ignore the rest. May return an array with only NaN values in case the minimize call has returned an INITIALIZATION_FAILURE status or that abort() has been called at the very beginning of the minimization. Do not call this method before minimization.

getFunctionValue
public double getFunctionValue()
Get the value of the minimum, i.e. the value associated with the resulting parameters as obtained by getParams(). May return NaN in case the minimize call has returned an INITIALIZATION_FAILURE status or that abort() has been called at the very beginning of the minimization. Do not call this method before minimization.

getIterations
public int getIterations()
Get number of iterations performed (includes all restarts). One iteration needs between one and numParams+3 calls of the target function (typically two calls per iteration)

setMaxIterations
public void setMaxIterations(int x)
Set maximum number of iterations allowed (including all restarts and all threads). The number of function calls will be higher, up to about twice the number of iterations. Note that the number of iterations needed typically scales with the square of the dimensions (i.e., numParams^2). Default value is 1000 * numParams^2 (half that value if maxRestarts=0), which is enough for >99% of all cases (if the maximum number of restarts is set to 2); typical number of iterations are below 10 and 20% of this value.

getMaxIterations
public int getMaxIterations()
Get maximum number of iterations allowed. Unless given by 'setMaxIterations', this value is defined only after running 'setFunction'

setMaxRestarts
public void setMaxRestarts(int n)
Set maximum number of minimization restarts to do. With n=0, the minimizer is run once in a single thread. With n>0, two threads are used, and if the two results do not agree within the error bounds, additional optimizations are done up to n times, each with two threads. In any case, if the two best results are within the error bounds, the best result is accepted. Thus, on dualcore machines running no other jobs, values of n=1 or n=2 (default) do not cause a notable increase of computing time for 'easy' optimization problems, while greatly reducing the risk of running into spurious local minima or non optimal results due to the minimizer getting stuck. In problematic cases, the improved The 'n' value does not refer to the restarts within one minimization run (there, at least one restart is performed, and restart is repeated until the result does not change within the error bounds). This value does not affect the 'minimizeOnce' function call. When setting the maximum number of restarts to a value much higher than 3, remember to adjust the maximum number of iterations (see setMaxIterations).

getMaxRestarts
public int getMaxRestarts()
Get maximum number of minimization restarts to do

getCompletedMinimizations
public int getCompletedMinimizations()
Get number of minimizations completed (i.e. not aborted or stopped because the number of minimization was exceeded). After a minimize(..) call, typically 2 for unproblematic cases. Higher number indicate a functin that is difficult to minimize or the existence of more than one minimum.

setRandomSeed
public void setRandomSeed(int n)
Set a seed to initialize the random number generator, which is used for initialization of the simplex.

setMaxError
public void setMaxError(double maxRelError)
Sets the accuracy of convergence. Minimizing is done as long as the relative error of the function value is more than this number (Default: 1e10).

setMaxError
public void setMaxError(double maxRelError, double maxAbsError)
Sets the accuracy of convergence. Minimizing is done as long as the relative error of the function value is more than maxRelError (Default: 1e10) and the maximum absolute error is more than maxAbsError (i.e. it is enough to fulfil one of these two criteria)

setParamResolutions
public void setParamResolutions(double[] paramResolutions)
Set the resolution of the parameters, for problems where the target function is not smooth but suffers from numerical noise. If all parameters of all vertices are closer to the best value than the respective resolution value, minimization is finished, irrespective of the difference of the target function values at the vertices

setMaximumThreads
public void setMaximumThreads(int numThreads)
Call setMaximuThreads(1) to avoid multithreaded execution (in case the userprovided target function does not allow moultithreading). Currently a maximum of 2 thread is used irrespective of any higher value.

abort
public void abort()
Aborts minimization. Calls to getParams() will return the best solution found so far. This method may be called from the usersupplied target function. If displayStatusAndCheckEsc has been called before, the Minimizer itself checks for the ESC key.

setStatusAndEsc
public void setStatusAndEsc(java.lang.String ijStatusString, boolean checkEscape)
Create output on the number of iterations in the ImageJ Status line, e.g. "50 (max 750); ESC to stop"  Parameters:
ijStatusString
 Displayed in the beginning of the status message. No display if null. E.g. "Optimization: Iteration "checkEscape
 When true, the Minimizer stops if escape is pressed and the status becomes ABORTED. Note that checking for ESC does not work in the Event Queue thread.

setExtraArrayElements
public void setExtraArrayElements(int numExtraArrayElements)
Add a given number of extra elements to array of parameters (independent vaiables) for private use in the user function. Note that the first numParams+1 elements should not be touched.

