Return-Path: Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: (qmail 64236 invoked from network); 28 Jul 2010 12:05:03 -0000 Received: from unknown (HELO mail.apache.org) (140.211.11.3) by 140.211.11.9 with SMTP; 28 Jul 2010 12:05:03 -0000 Received: (qmail 86619 invoked by uid 500); 28 Jul 2010 12:05:03 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 86259 invoked by uid 500); 28 Jul 2010 12:05:00 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 86246 invoked by uid 99); 28 Jul 2010 12:04:59 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 28 Jul 2010 12:04:59 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 28 Jul 2010 12:04:58 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id D9C4723889C5; Wed, 28 Jul 2010 12:03:41 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: commits@commons.apache.org From: erans@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20100728120341.D9C4723889C5@eris.apache.org> 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.
- * {@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 2 macheps and preferable not - * much less than sqrt(macheps), where macheps 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.
+ * {@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 2 macheps and + * preferable not much less than sqrt(macheps), where + * macheps 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()); } }