commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From er...@apache.org
Subject svn commit: r1330739 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/optimization/direct/PowellOptimizer.java test/java/org/apache/commons/math3/optimization/direct/PowellOptimizerTest.java
Date Thu, 26 Apr 2012 10:02:49 GMT
Author: erans
Date: Thu Apr 26 10:02:48 2012
New Revision: 1330739

URL: http://svn.apache.org/viewvc?rev=1330739&view=rev
Log:
MATH-783
Made the internal "line" search use a stopping criterion based on function
values instead of domain values (as is the default in "BrentOptimizer").

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/direct/PowellOptimizer.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/direct/PowellOptimizerTest.java

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/direct/PowellOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/direct/PowellOptimizer.java?rev=1330739&r1=1330738&r2=1330739&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/direct/PowellOptimizer.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/direct/PowellOptimizer.java
Thu Apr 26 10:02:48 2012
@@ -26,10 +26,12 @@ import org.apache.commons.math3.exceptio
 import org.apache.commons.math3.optimization.GoalType;
 import org.apache.commons.math3.optimization.PointValuePair;
 import org.apache.commons.math3.optimization.ConvergenceChecker;
+import org.apache.commons.math3.optimization.AbstractConvergenceChecker;
 import org.apache.commons.math3.optimization.MultivariateOptimizer;
 import org.apache.commons.math3.optimization.univariate.BracketFinder;
 import org.apache.commons.math3.optimization.univariate.BrentOptimizer;
 import org.apache.commons.math3.optimization.univariate.UnivariatePointValuePair;
+import org.apache.commons.math3.optimization.univariate.SimpleUnivariateValueChecker;
 
 /**
  * Powell algorithm.
@@ -90,12 +92,9 @@ public class PowellOptimizer
         relativeThreshold = rel;
         absoluteThreshold = abs;
 
-        // Line search tolerances can be much lower than the tolerances
-        // required for the optimizer itself.
-        final double minTol = 1e-4;
-        final double lsRel = Math.min(FastMath.sqrt(relativeThreshold), minTol);
-        final double lsAbs = Math.min(FastMath.sqrt(absoluteThreshold), minTol);
-        line = new LineSearch(lsRel, lsAbs);
+        // Line search tolerances can be much less stringent than the tolerances
+        // required for the optimizer itself. XXX Is it still true with the new checker?
+        line = new LineSearch(rel, abs);
     }
 
     /**
@@ -240,17 +239,35 @@ public class PowellOptimizer
      */
     private class LineSearch extends BrentOptimizer {
         /**
+         * Value that will pass the precondition check for {@link BrentOptimizer}
+         * but will not pass the convergence check, so that the custom checker
+         * will always decide when to stop the line search.
+         */
+        private static final double REL_TOL_UNUSED = 1e-15;
+        /**
+         * Value that will pass the precondition check for {@link BrentOptimizer}
+         * but will not pass the convergence check, so that the custom checker
+         * will always decide when to stop the line search.
+         */
+        private static final double ABS_TOL_UNUSED = Double.MIN_VALUE;
+        /**
          * Automatic bracketing.
          */
         private final BracketFinder bracket = new BracketFinder();
 
         /**
+         * The "BrentOptimizer" default stopping criterion uses the tolerances
+         * to check the domain (point) values, not the function values.
+         * We thus create a custom checker to use function values.
+         *
          * @param rel Relative threshold.
          * @param abs Absolute threshold.
          */
         LineSearch(double rel,
                    double abs) {
-            super(rel, abs);
+            super(REL_TOL_UNUSED,
+                  ABS_TOL_UNUSED,
+                  new SimpleUnivariateValueChecker(rel, abs));
         }
 
         /**

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/direct/PowellOptimizerTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/direct/PowellOptimizerTest.java?rev=1330739&r1=1330738&r2=1330739&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/direct/PowellOptimizerTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/direct/PowellOptimizerTest.java
Thu Apr 26 10:02:48 2012
@@ -21,6 +21,7 @@ import org.apache.commons.math3.analysis
 import org.apache.commons.math3.optimization.GoalType;
 import org.apache.commons.math3.optimization.MultivariateOptimizer;
 import org.apache.commons.math3.optimization.PointValuePair;
+import org.apache.commons.math3.util.FastMath;
 import org.junit.Assert;
 import org.junit.Test;
 
@@ -117,6 +118,65 @@ public class PowellOptimizerTest {
     }
 
     /**
+     * Ensure that we do not increase the number of function evaluations when
+     * the function values are scaled up.
+     * Note that the tolerances parameters passed to the constructor must
+     * still hold sensible values because they are used to set the line search
+     * tolerances.
+     */
+    @Test
+    public void testRelativeToleranceOnScaledValues() {
+        final MultivariateFunction func = new MultivariateFunction() {
+                public double value(double[] x) {
+                    final double a = x[0] - 1;
+                    final double b = x[1] - 1;
+                    return a * a * FastMath.sqrt(FastMath.abs(a)) + b * b + 1;
+                }
+            };
+
+        int dim = 2;
+        final double[] minPoint = new double[dim];
+        for (int i = 0; i < dim; i++) {
+            minPoint[i] = 1;
+        }
+
+        double[] init = new double[dim];
+        // Initial is far from minimum.
+        for (int i = 0; i < dim; i++) {
+            init[i] = minPoint[i] - 20;
+        }
+
+        final double relTol = 1e-10;
+
+        final int maxEval = 1000;
+        // Very small absolute tolerance to rely solely on the relative
+        // tolerance as a stopping criterion
+        final MultivariateOptimizer optim = new PowellOptimizer(relTol, 1e-100);
+
+        final PointValuePair funcResult = optim.optimize(maxEval, func, GoalType.MINIMIZE,
init);
+        final double funcValue = func.value(funcResult.getPoint());
+        final int funcEvaluations = optim.getEvaluations();
+
+        final double scale = 1e10;
+        final MultivariateFunction funcScaled = new MultivariateFunction() {
+                public double value(double[] x) {
+                    return scale * func.value(x);
+                }
+            };
+
+        final PointValuePair funcScaledResult = optim.optimize(maxEval, funcScaled, GoalType.MINIMIZE,
init);
+        final double funcScaledValue = funcScaled.value(funcScaledResult.getPoint());
+        final int funcScaledEvaluations = optim.getEvaluations();
+
+        // Check that both minima provide the same objective funciton values,
+        // within the relative function tolerance.
+        Assert.assertEquals(1, funcScaledValue / (scale * funcValue), relTol);
+
+        // Check that the numbers of evaluations are the same.
+        Assert.assertEquals(funcEvaluations, funcScaledEvaluations);
+    }
+
+    /**
      * @param func Function to optimize.
      * @param optimum Expected optimum.
      * @param init Starting point.
@@ -134,10 +194,11 @@ public class PowellOptimizerTest {
         final MultivariateOptimizer optim = new PowellOptimizer(fTol, Math.ulp(1d));
 
         final PointValuePair result = optim.optimize(1000, func, goal, init);
-        final double[] found = result.getPoint();
+        final double[] point = result.getPoint();
 
         for (int i = 0, dim = optimum.length; i < dim; i++) {
-            Assert.assertEquals(optimum[i], found[i], pointTol);
+            Assert.assertEquals("found[" + i + "]=" + point[i] + " value=" + result.getValue(),
+                                optimum[i], point[i], pointTol);
         }
     }
 }



Mime
View raw message