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());
}
}
