You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2009/08/14 21:23:27 UTC
svn commit: r804328 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math/optimization/direct/MultiDirectional.java
site/xdoc/changes.xml
test/java/org/apache/commons/math/optimization/direct/MultiDirectionalTest.java
Author: luc
Date: Fri Aug 14 19:23:27 2009
New Revision: 804328
URL: http://svn.apache.org/viewvc?rev=804328&view=rev
Log:
Prevent infinite loops in multi-directional direct optimization method when the start point is exactly at the optimal point
JIRA: MATH-283
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/direct/MultiDirectional.java
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/direct/MultiDirectionalTest.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/direct/MultiDirectional.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/direct/MultiDirectional.java?rev=804328&r1=804327&r2=804328&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/direct/MultiDirectional.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/direct/MultiDirectional.java Fri Aug 14 19:23:27 2009
@@ -21,6 +21,7 @@
import org.apache.commons.math.FunctionEvaluationException;
import org.apache.commons.math.optimization.OptimizationException;
+import org.apache.commons.math.optimization.RealConvergenceChecker;
import org.apache.commons.math.optimization.RealPointValuePair;
/**
@@ -60,6 +61,7 @@
protected void iterateSimplex(final Comparator<RealPointValuePair> comparator)
throws FunctionEvaluationException, OptimizationException, IllegalArgumentException {
+ final RealConvergenceChecker checker = getConvergenceChecker();
while (true) {
incrementIterationsCounter();
@@ -91,6 +93,16 @@
return;
}
+ // check convergence
+ final int iter = getIterations();
+ boolean converged = true;
+ for (int i = 0; i < simplex.length; ++i) {
+ converged &= checker.converged(iter, original[i], simplex[i]);
+ }
+ if (converged) {
+ return;
+ }
+
}
}
Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=804328&r1=804327&r2=804328&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Fri Aug 14 19:23:27 2009
@@ -38,6 +38,12 @@
<title>Commons Math Release Notes</title>
</properties>
<body>
+ <release version="2.1" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-283" due-to="Michael Nischt">
+ Prevent infinite loops in multi-directional direct optimization method when
+ the start point is exactly at the optimal point
+ </action>
+ </release>
<release version="2.0" date="2009-08-03" description="
This is a major release. It combines bug fixes, new features and
changes to existing features. Most notable among the new features are:
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/direct/MultiDirectionalTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/direct/MultiDirectionalTest.java?rev=804328&r1=804327&r2=804328&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/direct/MultiDirectionalTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/direct/MultiDirectionalTest.java Fri Aug 14 19:23:27 2009
@@ -17,24 +17,19 @@
package org.apache.commons.math.optimization.direct;
-import junit.framework.Test;
-import junit.framework.TestCase;
-import junit.framework.TestSuite;
-
import org.apache.commons.math.ConvergenceException;
import org.apache.commons.math.FunctionEvaluationException;
import org.apache.commons.math.analysis.MultivariateRealFunction;
import org.apache.commons.math.optimization.GoalType;
+import org.apache.commons.math.optimization.OptimizationException;
import org.apache.commons.math.optimization.RealPointValuePair;
import org.apache.commons.math.optimization.SimpleScalarValueChecker;
+import org.junit.Assert;
+import org.junit.Test;
-public class MultiDirectionalTest
- extends TestCase {
-
- public MultiDirectionalTest(String name) {
- super(name);
- }
+public class MultiDirectionalTest {
+ @Test
public void testFunctionEvaluationExceptions() {
MultivariateRealFunction wrong =
new MultivariateRealFunction() {
@@ -52,25 +47,26 @@
try {
MultiDirectional optimizer = new MultiDirectional(0.9, 1.9);
optimizer.optimize(wrong, GoalType.MINIMIZE, new double[] { -1.0 });
- fail("an exception should have been thrown");
+ Assert.fail("an exception should have been thrown");
} catch (FunctionEvaluationException ce) {
// expected behavior
- assertNull(ce.getCause());
+ Assert.assertNull(ce.getCause());
} catch (Exception e) {
- fail("wrong exception caught: " + e.getMessage());
+ Assert.fail("wrong exception caught: " + e.getMessage());
}
try {
MultiDirectional optimizer = new MultiDirectional(0.9, 1.9);
optimizer.optimize(wrong, GoalType.MINIMIZE, new double[] { +2.0 });
- fail("an exception should have been thrown");
+ Assert.fail("an exception should have been thrown");
} catch (FunctionEvaluationException ce) {
// expected behavior
- assertNotNull(ce.getCause());
+ Assert.assertNotNull(ce.getCause());
} catch (Exception e) {
- fail("wrong exception caught: " + e.getMessage());
+ Assert.fail("wrong exception caught: " + e.getMessage());
}
}
+ @Test
public void testMinimizeMaximize()
throws FunctionEvaluationException, ConvergenceException {
@@ -93,43 +89,45 @@
};
MultiDirectional optimizer = new MultiDirectional();
- optimizer.setConvergenceChecker(new SimpleScalarValueChecker(1.0e-10, 1.0e-30));
+ optimizer.setConvergenceChecker(new SimpleScalarValueChecker(1.0e-11, 1.0e-30));
optimizer.setMaxIterations(200);
optimizer.setStartConfiguration(new double[] { 0.2, 0.2 });
RealPointValuePair optimum;
// minimization
optimum = optimizer.optimize(fourExtrema, GoalType.MINIMIZE, new double[] { -3.0, 0 });
- assertEquals(xM, optimum.getPoint()[0], 4.0e-6);
- assertEquals(yP, optimum.getPoint()[1], 3.0e-6);
- assertEquals(valueXmYp, optimum.getValue(), 8.0e-13);
- assertTrue(optimizer.getEvaluations() > 120);
- assertTrue(optimizer.getEvaluations() < 150);
+ Assert.assertEquals(xM, optimum.getPoint()[0], 4.0e-6);
+ Assert.assertEquals(yP, optimum.getPoint()[1], 3.0e-6);
+ Assert.assertEquals(valueXmYp, optimum.getValue(), 8.0e-13);
+ Assert.assertTrue(optimizer.getEvaluations() > 120);
+ Assert.assertTrue(optimizer.getEvaluations() < 150);
optimum = optimizer.optimize(fourExtrema, GoalType.MINIMIZE, new double[] { +1, 0 });
- assertEquals(xP, optimum.getPoint()[0], 2.0e-8);
- assertEquals(yM, optimum.getPoint()[1], 3.0e-6);
- assertEquals(valueXpYm, optimum.getValue(), 2.0e-12);
- assertTrue(optimizer.getEvaluations() > 120);
- assertTrue(optimizer.getEvaluations() < 150);
+ Assert.assertEquals(xP, optimum.getPoint()[0], 2.0e-8);
+ Assert.assertEquals(yM, optimum.getPoint()[1], 3.0e-6);
+ Assert.assertEquals(valueXpYm, optimum.getValue(), 2.0e-12);
+ Assert.assertTrue(optimizer.getEvaluations() > 120);
+ Assert.assertTrue(optimizer.getEvaluations() < 150);
// maximization
optimum = optimizer.optimize(fourExtrema, GoalType.MAXIMIZE, new double[] { -3.0, 0.0 });
- assertEquals(xM, optimum.getPoint()[0], 7.0e-7);
- assertEquals(yM, optimum.getPoint()[1], 3.0e-7);
- assertEquals(valueXmYm, optimum.getValue(), 2.0e-14);
- assertTrue(optimizer.getEvaluations() > 120);
- assertTrue(optimizer.getEvaluations() < 150);
+ Assert.assertEquals(xM, optimum.getPoint()[0], 7.0e-7);
+ Assert.assertEquals(yM, optimum.getPoint()[1], 3.0e-7);
+ Assert.assertEquals(valueXmYm, optimum.getValue(), 2.0e-14);
+ Assert.assertTrue(optimizer.getEvaluations() > 120);
+ Assert.assertTrue(optimizer.getEvaluations() < 150);
+ optimizer.setConvergenceChecker(new SimpleScalarValueChecker(1.0e-15, 1.0e-30));
optimum = optimizer.optimize(fourExtrema, GoalType.MAXIMIZE, new double[] { +1, 0 });
- assertEquals(xP, optimum.getPoint()[0], 2.0e-8);
- assertEquals(yP, optimum.getPoint()[1], 3.0e-6);
- assertEquals(valueXpYp, optimum.getValue(), 2.0e-12);
- assertTrue(optimizer.getEvaluations() > 120);
- assertTrue(optimizer.getEvaluations() < 150);
+ Assert.assertEquals(xP, optimum.getPoint()[0], 2.0e-8);
+ Assert.assertEquals(yP, optimum.getPoint()[1], 3.0e-6);
+ Assert.assertEquals(valueXpYp, optimum.getValue(), 2.0e-12);
+ Assert.assertTrue(optimizer.getEvaluations() > 180);
+ Assert.assertTrue(optimizer.getEvaluations() < 220);
}
+ @Test
public void testRosenbrock()
throws FunctionEvaluationException, ConvergenceException {
@@ -154,13 +152,14 @@
RealPointValuePair optimum =
optimizer.optimize(rosenbrock, GoalType.MINIMIZE, new double[] { -1.2, 1.0 });
- assertEquals(count, optimizer.getEvaluations());
- assertTrue(optimizer.getEvaluations() > 70);
- assertTrue(optimizer.getEvaluations() < 100);
- assertTrue(optimum.getValue() > 1.0e-2);
+ Assert.assertEquals(count, optimizer.getEvaluations());
+ Assert.assertTrue(optimizer.getEvaluations() > 50);
+ Assert.assertTrue(optimizer.getEvaluations() < 100);
+ Assert.assertTrue(optimum.getValue() > 1.0e-2);
}
+ @Test
public void testPowell()
throws FunctionEvaluationException, ConvergenceException {
@@ -183,15 +182,64 @@
optimizer.setMaxIterations(1000);
RealPointValuePair optimum =
optimizer.optimize(powell, GoalType.MINIMIZE, new double[] { 3.0, -1.0, 0.0, 1.0 });
- assertEquals(count, optimizer.getEvaluations());
- assertTrue(optimizer.getEvaluations() > 800);
- assertTrue(optimizer.getEvaluations() < 900);
- assertTrue(optimum.getValue() > 1.0e-2);
+ Assert.assertEquals(count, optimizer.getEvaluations());
+ Assert.assertTrue(optimizer.getEvaluations() > 800);
+ Assert.assertTrue(optimizer.getEvaluations() < 900);
+ Assert.assertTrue(optimum.getValue() > 1.0e-2);
}
- public static Test suite() {
- return new TestSuite(MultiDirectionalTest.class);
+ @Test
+ public void testMath283()
+ throws FunctionEvaluationException, OptimizationException {
+ // fails because MultiDirectional.iterateSimplex is looping forever
+ // the while(true) should be replaced with a convergence check
+ MultiDirectional multiDirectional = new MultiDirectional();
+ multiDirectional.setMaxIterations(100);
+ multiDirectional.setMaxEvaluations(1000);
+
+ final Gaussian2D function = new Gaussian2D(0.0, 0.0, 1.0);
+
+ RealPointValuePair estimate = multiDirectional.optimize(function,
+ GoalType.MAXIMIZE, function.getMaximumPosition());
+
+ final double EPSILON = 1e-5;
+
+ final double expectedMaximum = function.getMaximum();
+ final double actualMaximum = estimate.getValue();
+ Assert.assertEquals(expectedMaximum, actualMaximum, EPSILON);
+
+ final double[] expectedPosition = function.getMaximumPosition();
+ final double[] actualPosition = estimate.getPoint();
+ Assert.assertEquals(expectedPosition[0], actualPosition[0], EPSILON );
+ Assert.assertEquals(expectedPosition[1], actualPosition[1], EPSILON );
+
+ }
+
+ private static class Gaussian2D implements MultivariateRealFunction {
+
+ private final double[] maximumPosition;
+
+ private final double std;
+
+ public Gaussian2D(double xOpt, double yOpt, double std) {
+ maximumPosition = new double[] { xOpt, yOpt };
+ this.std = std;
+ }
+
+ public double getMaximum() {
+ return value(maximumPosition);
+ }
+
+ public double[] getMaximumPosition() {
+ return maximumPosition.clone();
+ }
+
+ public double value(double[] point) {
+ final double x = point[0], y = point[1];
+ final double twoS2 = 2.0 * std * std;
+ return 1.0 / (twoS2 * Math.PI) * Math.exp(-(x * x + y * y) / twoS2);
+ }
}
private int count;