Module ij
Package ij.measure

Class Minimizer


  • public class Minimizer
    extends java.lang.Object
    Minimizer based on Nelder-Mead 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 Nelder-Mead simplex algorithm in low dimensions. SIAM J. Optim. 9, 112-147 (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 curve-fitting 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. Re-initialization 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 re-initializing the simplex does not lead to a significant improvement, the value is accepted as true (local) minimum. Multiple minimization runs: In spite of re-initializing (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 user-supplied target function should return NaN for out-of-bounds 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 2012-01-30: first version, based on previous CurveFitter 2012-11-20: mor tries to find initial params not leading to NaN 2013-09-24: 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 2013-10-13: setStatusAndEscape to show iterations and enable abort by ESC 2014-09-16: 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 count
      static int MAX_RESTARTS_EXCEEDED
      Status returned: not two equal solutions after maximum number of restarts
      static 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 codes
      static 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 do
      double[] 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 gradient-enhanced 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 re-initialization 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 multi-threaded execution (in case the user-provided 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 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
    • Constructor Detail

      • Minimizer

        public Minimizer()
    • 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 gradient-enhanced 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 dual-core 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 re-initialization 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 dual-core 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: 1e-10).
      • 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: 1e-10) 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 multi-threaded execution (in case the user-provided 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 user-supplied 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.