Class BrentOptimizer


  • final class BrentOptimizer
    extends java.lang.Object
    For a function defined on some interval (lo, hi), this class finds an approximation x to the point at which the function attains its minimum. It implements Richard Brent's algorithm (from his book "Algorithms for Minimization without Derivatives", p. 79) for finding minima of real univariate functions.

    This code is an adaptation, partly based on the Python code from SciPy (module "optimize.py" v0.5); the original algorithm is also modified:

    • to use an initial guess provided by the user,
    • to ensure that the best point encountered is the one returned.

    This class has been extracted from o.a.c.math4.optim.univariate and simplified to remove support for the UnivariateOptimizer interface. This removed the options: to find the maximum; use a custom convergence checker on the function value; and remove the maximum function evaluation count. The class now implements a single optimize method within the provided bracket from the given start position (with value).

    Since:
    1.1
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) static class  BrentOptimizer.PointValuePair
      This class holds a point and the value of an objective function at this point.
    • Constructor Summary

      Constructors 
      Constructor Description
      BrentOptimizer​(double rel, double abs)
      The arguments are used to implement the original stopping criterion of Brent's algorithm.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) int getEvaluations()
      Gets the number of function evaluations from the most recent call to optimize.
      (package private) BrentOptimizer.PointValuePair optimize​(java.util.function.DoubleUnaryOperator func, double lo, double hi, double mid, double fMid)
      Search for the minimum inside the provided interval.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • GOLDEN_SECTION

        private static final double GOLDEN_SECTION
        Golden section. (3 - sqrt(5)) / 2.
        See Also:
        Constant Field Values
      • MIN_RELATIVE_TOLERANCE

        private static final double MIN_RELATIVE_TOLERANCE
        Minimum relative tolerance. 2 * eps = 2^-51.
        See Also:
        Constant Field Values
      • relativeThreshold

        private final double relativeThreshold
        Relative threshold.
      • absoluteThreshold

        private final double absoluteThreshold
        Absolute threshold.
      • evaluations

        private int evaluations
        The number of function evaluations from the most recent call to optimize.
    • Constructor Detail

      • BrentOptimizer

        BrentOptimizer​(double rel,
                       double abs)
        The arguments are used to implement the original stopping criterion of Brent's algorithm. abs and rel define a tolerance tol = rel |x| + abs. rel should be no smaller than 2 macheps and preferably not much less than sqrt(macheps), where macheps is the relative machine precision. abs must be positive.
        Parameters:
        rel - Relative threshold.
        abs - Absolute threshold.
        Throws:
        java.lang.IllegalArgumentException - if abs <= 0; or if rel < 2 * Math.ulp(1.0)
    • Method Detail

      • getEvaluations

        int getEvaluations()
        Gets the number of function evaluations from the most recent call to optimize.
        Returns:
        the function evaluations
      • optimize

        BrentOptimizer.PointValuePair optimize​(java.util.function.DoubleUnaryOperator func,
                                               double lo,
                                               double hi,
                                               double mid,
                                               double fMid)
        Search for the minimum inside the provided interval. The bracket must satisfy the equalities lo < mid < hi or hi < mid < lo.

        Note: This function accepts the initial guess and the function value at that point. This is done for convenience as this internal class is used where the caller already knows the function value.

        Parameters:
        func - Function to solve.
        lo - Lower bound of the search interval.
        hi - Higher bound of the search interval.
        mid - Start point.
        fMid - Function value at the start point.
        Returns:
        the value where the function is minimum.
        Throws:
        java.lang.IllegalArgumentException - if start point is not within the search interval
        java.lang.IllegalStateException - if the maximum number of iterations is exceeded