You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2012/04/26 12:02:49 UTC
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
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);
}
}
}