commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From er...@apache.org
Subject svn commit: r980032 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math/ main/java/org/apache/commons/math/optimization/univariate/ test/java/org/apache/commons/math/optimization/ test/java/org/apache/commons/math/optimization/univar...
Date Wed, 28 Jul 2010 12:03:41 GMT
Author: erans
Date: Wed Jul 28 12:03:41 2010
New Revision: 980032

URL: http://svn.apache.org/viewvc?rev=980032&view=rev
Log:
MATH-395: Another bug uncovered; all things being equal, the code now behaves
like the Puthon implementation.
MATH-397: Modified "BrentOptimizer" following the changes in
"AbstractUnivariateRealOptimizer".

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/ConvergingAlgorithmImpl.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/AbstractUnivariateRealOptimizer.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/BrentOptimizer.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/MultiStartUnivariateRealOptimizerTest.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/univariate/BrentOptimizerTest.java

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/ConvergingAlgorithmImpl.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/ConvergingAlgorithmImpl.java?rev=980032&r1=980031&r2=980032&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/ConvergingAlgorithmImpl.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/ConvergingAlgorithmImpl.java
Wed Jul 28 12:03:41 2010
@@ -139,14 +139,14 @@ public abstract class ConvergingAlgorith
     /**
      * Increment the iterations counter by 1.
      *
-     * @throws OptimizationException if the maximal number
+     * @throws MaxIterationsExceededException if the maximal number
      * of iterations is exceeded.
      * @since 2.2
      */
     protected void incrementIterationsCounter()
-        throws ConvergenceException {
+        throws MaxIterationsExceededException {
         if (++iterationCount > maximalIterationCount) {
-            throw new ConvergenceException(new MaxIterationsExceededException(maximalIterationCount));
+            throw new MaxIterationsExceededException(maximalIterationCount);
         }
     }
 }

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/AbstractUnivariateRealOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/AbstractUnivariateRealOptimizer.java?rev=980032&r1=980031&r2=980032&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/AbstractUnivariateRealOptimizer.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/AbstractUnivariateRealOptimizer.java
Wed Jul 28 12:03:41 2010
@@ -260,5 +260,6 @@ public abstract class AbstractUnivariate
      *
      * @return the optimum.
      */
-    protected abstract double doOptimize();
+    protected abstract double doOptimize()
+        throws MaxIterationsExceededException, FunctionEvaluationException;
 }

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/BrentOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/BrentOptimizer.java?rev=980032&r1=980031&r2=980032&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/BrentOptimizer.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/univariate/BrentOptimizer.java
Wed Jul 28 12:03:41 2010
@@ -41,39 +41,37 @@ public class BrentOptimizer extends Abst
      * Construct a solver.
      */
     public BrentOptimizer() {
-        super(100, 1E-10);
+        setMaxEvaluations(1000);
+        setMaximalIterationCount(100);
+        setAbsoluteAccuracy(1e-11);
+        setRelativeAccuracy(1e-9);
     }
 
-    /** {@inheritDoc} */
-    public double optimize(final UnivariateRealFunction f, final GoalType goalType,
-                           final double min, final double max, final double startValue)
+    /**
+     * Perform the optimization.
+     *
+     * @return the optimum.
+     */
+    protected double doOptimize()
         throws MaxIterationsExceededException, FunctionEvaluationException {
-        clearResult();
-        return localMin(f, goalType, min, startValue, max,
+        return localMin(getGoalType() == GoalType.MINIMIZE,
+                        getMin(), getStartValue(), getMax(),
                         getRelativeAccuracy(), getAbsoluteAccuracy());
     }
 
-    /** {@inheritDoc} */
-    public double optimize(final UnivariateRealFunction f, final GoalType goalType,
-                           final double min, final double max)
-        throws MaxIterationsExceededException, FunctionEvaluationException {
-        return optimize(f, goalType, min, max, min + GOLDEN_SECTION * (max - min));
-    }
-
     /**
-     * Find the minimum of the function {@code f} within the interval {@code (a, b)}.
+     * Find the minimum of the function within the interval {@code (lo, hi)}.
      *
-     * If the function {@code f} is defined on the interval {@code (a, b)}, then
-     * this method finds an approximation {@code x} to the point at which {@code f}
-     * attains its minimum.<br/>
-     * {@code t} and {@code eps} define a tolerance {@code tol = eps |x| + t} and
-     * {@code f} is never evaluated at two points closer together than {@code tol}.
-     * {@code eps} should be no smaller than <em>2 macheps</em> and preferable
not
-     * much less than <em>sqrt(macheps)</em>, where <em>macheps</em>
is the relative
-     * machine precision. {@code t} should be positive.
-     * @param f the function to solve.
-     * @param goalType type of optimization goal: either {@link GoalType#MAXIMIZE}
-     * or {@link GoalType#MINIMIZE}.
+     * If the function is defined on the interval {@code (lo, hi)}, then
+     * this method finds an approximation {@code x} to the point at which
+     * the function attains its minimum.<br/>
+     * {@code t} and {@code eps} define a tolerance {@code tol = eps |x| + t}
+     * and the function is never evaluated at two points closer together than
+     * {@code tol}. {@code eps} should be no smaller than <em>2 macheps</em>
and
+     * preferable not much less than <em>sqrt(macheps)</em>, where
+     * <em>macheps</em> is the relative machine precision. {@code t} should be
+     * positive.
+     * @param isMinim {@code true} when minimizing the function.
      * @param lo Lower bound of the interval.
      * @param mid Point inside the interval {@code [lo, hi]}.
      * @param hi Higher bound of the interval.
@@ -85,8 +83,7 @@ public class BrentOptimizer extends Abst
      * @throws FunctionEvaluationException if an error occurs evaluating
      * the function.
      */
-    private double localMin(UnivariateRealFunction f,
-                            GoalType goalType,
+    private double localMin(boolean isMinim,
                             double lo, double mid, double hi,
                             double eps, double t)
         throws MaxIterationsExceededException, FunctionEvaluationException {
@@ -108,16 +105,16 @@ public class BrentOptimizer extends Abst
         double x = mid;
         double v = x;
         double w = x;
+        double d = 0;
         double e = 0;
-        double fx = computeObjectiveValue(f, x);
-        if (goalType == GoalType.MAXIMIZE) {
+        double fx = computeObjectiveValue(x);
+        if (!isMinim) {
             fx = -fx;
         }
         double fv = fx;
         double fw = fx;
 
-        int count = 0;
-        while (count < maximalIterationCount) {
+        while (true) {
             double m = 0.5 * (a + b);
             final double tol1 = eps * Math.abs(x) + t;
             final double tol2 = 2 * tol1;
@@ -127,7 +124,6 @@ public class BrentOptimizer extends Abst
                 double p = 0;
                 double q = 0;
                 double r = 0;
-                double d = 0;
                 double u = 0;
 
                 if (Math.abs(e) > tol1) { // Fit parabola.
@@ -191,8 +187,8 @@ public class BrentOptimizer extends Abst
                     u = x + d;
                 }
 
-                double fu = computeObjectiveValue(f, u);
-                if (goalType == GoalType.MAXIMIZE) {
+                double fu = computeObjectiveValue(u);
+                if (!isMinim) {
                     fu = -fu;
                 }
 
@@ -229,16 +225,10 @@ public class BrentOptimizer extends Abst
                     }
                 }
             } else { // termination
-                setResult(x, (goalType == GoalType.MAXIMIZE) ? -fx : fx, count);
+                setFunctionValue(isMinim ? fx : -fx);
                 return x;
             }
-            ++count;
+            incrementIterationsCounter();
         }
-        throw new MaxIterationsExceededException(maximalIterationCount);
-    }
-
-    /** Temporary workaround. */
-    protected double doOptimize() {
-        throw new UnsupportedOperationException();
     }
 }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/MultiStartUnivariateRealOptimizerTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/MultiStartUnivariateRealOptimizerTest.java?rev=980032&r1=980031&r2=980032&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/MultiStartUnivariateRealOptimizerTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/MultiStartUnivariateRealOptimizerTest.java
Wed Jul 28 12:03:41 2010
@@ -48,8 +48,8 @@ public class MultiStartUnivariateRealOpt
             assertEquals(-1.0, f.value(optima[i]), 1.0e-10);
             assertEquals(f.value(optima[i]), optimaValues[i], 1.0e-10);
         }
-        assertTrue(minimizer.getEvaluations() > 1500);
-        assertTrue(minimizer.getEvaluations() < 1700);
+        assertTrue(minimizer.getEvaluations() > 150);
+        assertTrue(minimizer.getEvaluations() < 250);
     }
 
     @Test
@@ -84,8 +84,8 @@ public class MultiStartUnivariateRealOpt
         }
 
         double result = minimizer.optimize(f, GoalType.MINIMIZE, -0.3, -0.2);
-        assertEquals(-0.27195612525275803, result, 1.0e-13);
-        assertEquals(-0.27195612525275803, minimizer.getResult(), 1.0e-13);
+        assertEquals(-0.2719561270319131, result, 1.0e-13);
+        assertEquals(-0.2719561270319131, minimizer.getResult(), 1.0e-13);
         assertEquals(-0.04433426954946637, minimizer.getFunctionValue(), 1.0e-13);
 
         double[] optima = minimizer.getOptima();
@@ -93,10 +93,9 @@ public class MultiStartUnivariateRealOpt
         for (int i = 0; i < optima.length; ++i) {
             assertEquals(f.value(optima[i]), optimaValues[i], 1.0e-10);
         }
-
-        assertTrue(minimizer.getEvaluations()    >= 300);
-        assertTrue(minimizer.getEvaluations()    <= 420);
-        assertTrue(minimizer.getIterationCount() >= 100);
-        assertTrue(minimizer.getIterationCount() <= 140);
+        assertTrue(minimizer.getEvaluations()    >= 120);
+        assertTrue(minimizer.getEvaluations()    <= 170);
+        assertTrue(minimizer.getIterationCount() >= 120);
+        assertTrue(minimizer.getIterationCount() <= 170);
     }
 }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/univariate/BrentOptimizerTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/univariate/BrentOptimizerTest.java?rev=980032&r1=980031&r2=980032&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/univariate/BrentOptimizerTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/univariate/BrentOptimizerTest.java
Wed Jul 28 12:03:41 2010
@@ -29,6 +29,7 @@ import org.apache.commons.math.analysis.
 import org.apache.commons.math.analysis.UnivariateRealFunction;
 import org.apache.commons.math.optimization.GoalType;
 import org.apache.commons.math.optimization.UnivariateRealOptimizer;
+import org.apache.commons.math.stat.descriptive.DescriptiveStatistics;
 import org.junit.Test;
 
 /**
@@ -50,13 +51,13 @@ public final class BrentOptimizerTest {
         } catch (Exception e) {
             fail("wrong exception caught");
         }
-        assertEquals(3 * Math.PI / 2, minimizer.optimize(f, GoalType.MINIMIZE, 4, 5), 70
* minimizer.getAbsoluteAccuracy());
+        assertEquals(3 * Math.PI / 2, minimizer.optimize(f, GoalType.MINIMIZE, 4, 5), 10
* minimizer.getRelativeAccuracy());
         assertTrue(minimizer.getIterationCount() <= 50);
-        assertEquals(3 * Math.PI / 2, minimizer.optimize(f, GoalType.MINIMIZE, 1, 5), 70
* minimizer.getAbsoluteAccuracy());
+        assertEquals(3 * Math.PI / 2, minimizer.optimize(f, GoalType.MINIMIZE, 1, 5), 10
* minimizer.getRelativeAccuracy());
         assertTrue(minimizer.getIterationCount() <= 50);
         assertTrue(minimizer.getEvaluations()    <= 100);
-        assertTrue(minimizer.getEvaluations()    >=  30);
-        minimizer.setMaxEvaluations(50);
+        assertTrue(minimizer.getEvaluations()    >=  15);
+        minimizer.setMaxEvaluations(10);
         try {
             minimizer.optimize(f, GoalType.MINIMIZE, 4, 5);
             fail("an exception should have been thrown");
@@ -82,35 +83,35 @@ public final class BrentOptimizerTest {
     }
 
     @Test
-    public void testQuinticMinPythonComparison() throws MathException {
+    public void testQuinticMinStatistics() throws MathException {
         // The function has local minima at -0.27195613 and 0.82221643.
         UnivariateRealFunction f = new QuinticFunction();
         UnivariateRealOptimizer minimizer = new BrentOptimizer();
-        minimizer.setRelativeAccuracy(1e-12);
+        minimizer.setRelativeAccuracy(1e-10);
         minimizer.setAbsoluteAccuracy(1e-11);
 
-        double result;
-        int nIter, nEval;
+        final DescriptiveStatistics[] stat = new DescriptiveStatistics[3];
+        for (int i = 0; i < stat.length; i++) {
+            stat[i] = new DescriptiveStatistics();
+        }
+
+        final double min = -0.75;
+        final double max = 0.25;
+        final int nSamples = 200;
+        final double delta = (max - min) / nSamples;
+        for (int i = 0; i < nSamples; i++) {
+            final double start = min + i * delta;
+            stat[0].addValue(minimizer.optimize(f, GoalType.MINIMIZE, min, max, start));
+            stat[1].addValue(minimizer.getIterationCount());
+            stat[2].addValue(minimizer.getEvaluations());
+        }
 
-        result = minimizer.optimize(f, GoalType.MINIMIZE, -0.3, -0.2, -0.25);
-        nIter = minimizer.getIterationCount();
-        nEval = minimizer.getEvaluations();
-        // XXX Python: -0.27195612805911351 (instead of -0.2719561279558559).
-        assertEquals(-0.2719561279558559, result, 1e-12);
-        // XXX Python: 15 (instead of 18).
-        assertEquals(18, nEval);
-        // XXX Python: 11 (instead of 17).
-        assertEquals(17, nIter);
-
-        result = minimizer.optimize(f, GoalType.MINIMIZE, 0.7, 0.9, 0.8);
-        nIter = minimizer.getIterationCount();
-        nEval = minimizer.getEvaluations();
-        // XXX Python: 0.82221643488363705 (instead of 0.8222164326561908).
-        assertEquals(0.8222164326561908, result, 1e-12);
-        // XXX Python: 25 (instead of 43).
-        assertEquals(43, nEval);
-        // XXX Python: 21 (instead of 24).
-        assertEquals(24, nIter);
+        final double meanOptValue = stat[0].getMean();
+        final double medianIter = stat[1].getPercentile(50);
+        final double medianEval = stat[2].getPercentile(50);
+        assertTrue(meanOptValue > -0.27195612812 && meanOptValue < -0.27195612811);
+        assertEquals(medianIter, 17, Math.ulp(1d));
+        assertEquals(medianEval, 18, Math.ulp(1d));
     }
 
     @Test
@@ -120,7 +121,7 @@ public final class BrentOptimizerTest {
         UnivariateRealFunction f = new QuinticFunction();
         UnivariateRealOptimizer minimizer = new BrentOptimizer();
         assertEquals(0.27195613, minimizer.optimize(f, GoalType.MAXIMIZE, 0.2, 0.3), 1.0e-8);
-        minimizer.setMaximalIterationCount(20);
+        minimizer.setMaximalIterationCount(5);
         try {
             minimizer.optimize(f, GoalType.MAXIMIZE, 0.2, 0.3);
             fail("an exception should have been thrown");
@@ -136,11 +137,13 @@ public final class BrentOptimizerTest {
         UnivariateRealFunction f = new SinFunction();
         UnivariateRealOptimizer solver = new BrentOptimizer();
 
+        solver.setRelativeAccuracy(1e-8);
+
         // endpoint is minimum
         double result = solver.optimize(f, GoalType.MINIMIZE, 3 * Math.PI / 2, 5);
-        assertEquals(3 * Math.PI / 2, result, 70 * solver.getAbsoluteAccuracy());
+        assertEquals(3 * Math.PI / 2, result, 10 * solver.getRelativeAccuracy());
 
         result = solver.optimize(f, GoalType.MINIMIZE, 4, 3 * Math.PI / 2);
-        assertEquals(3 * Math.PI / 2, result, 80 * solver.getAbsoluteAccuracy());
+        assertEquals(3 * Math.PI / 2, result, 10 * solver.getRelativeAccuracy());
     }
 }



Mime
View raw message