commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From er...@apache.org
Subject svn commit: r1382070 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java test/java/org/apache/commons/math3/optimization/univariate/BrentOptimizerTest.java
Date Fri, 07 Sep 2012 15:43:40 GMT
Author: erans
Date: Fri Sep  7 15:43:40 2012
New Revision: 1382070

URL: http://svn.apache.org/viewvc?rev=1382070&view=rev
Log:
MATH-855 (second take).
Best point must be returned.

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/univariate/BrentOptimizerTest.java

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java?rev=1382070&r1=1382069&r2=1382070&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/univariate/BrentOptimizer.java
Fri Sep  7 15:43:40 2012
@@ -24,13 +24,19 @@ import org.apache.commons.math3.optimiza
 import org.apache.commons.math3.optimization.GoalType;
 
 /**
- * Implements Richard Brent's algorithm (from his book "Algorithms for
+ * For a function defined on some interval {@code (lo, hi)}, this class
+ * finds an approximation {@code x} to the point at which the function
+ * attains its minimum.
+ * It implements Richard Brent's algorithm (from his book "Algorithms for
  * Minimization without Derivatives", p. 79) for finding minima of real
- * univariate functions. This implementation is an adaptation partly
- * based on the Python code from SciPy (module "optimize.py" v0.5).
- * If the function is defined on some interval {@code (lo, hi)}, then
- * this method finds an approximation {@code x} to the point at which
- * the function attains its minimum.
+ * univariate functions.
+ * <br/>
+ * This code is an adaptation, partly based on the Python code from SciPy
+ * (module "optimize.py" v0.5); the original algorithm is also modified
+ * <ul>
+ *  <li>to use an initial guess provided by the user,</li>
+ *  <li>to ensure that the best point encountered is the one returned.</li>
+ * </ul>
  *
  * @version $Id$
  * @since 2.0
@@ -141,6 +147,8 @@ public class BrentOptimizer extends Base
         UnivariatePointValuePair previous = null;
         UnivariatePointValuePair current
             = new UnivariatePointValuePair(x, isMinim ? fx : -fx);
+        // Best point encountered so far (which is the initial guess).
+        UnivariatePointValuePair best = current;
 
         int iter = 0;
         while (true) {
@@ -224,10 +232,15 @@ public class BrentOptimizer extends Base
                 // User-defined convergence checker.
                 previous = current;
                 current = new UnivariatePointValuePair(u, isMinim ? fu : -fu);
+                best = best(best,
+                            best(current,
+                                 previous,
+                                 isMinim),
+                            isMinim);
 
                 if (checker != null) {
                     if (checker.converged(iter, previous, current)) {
-                        return best(current, previous, isMinim);
+                        return best;
                     }
                 }
 
@@ -264,7 +277,11 @@ public class BrentOptimizer extends Base
                     }
                 }
             } else { // Default termination (Brent's criterion).
-                return best(current, previous, isMinim);
+                return best(best,
+                            best(current,
+                                 previous,
+                                 isMinim),
+                            isMinim);
             }
             ++iter;
         }
@@ -278,7 +295,8 @@ public class BrentOptimizer extends Base
      * @param isMinim {@code true} if the selected point must be the one with
      * the lowest value.
      * @return the best point, or {@code null} if {@code a} and {@code b} are
-     * both {@code null}.
+     * both {@code null}. When {@code a} and {@code b} have the same function
+     * value, {@code a} is returned.
      */
     private UnivariatePointValuePair best(UnivariatePointValuePair a,
                                           UnivariatePointValuePair b,
@@ -291,9 +309,9 @@ public class BrentOptimizer extends Base
         }
 
         if (isMinim) {
-            return a.getValue() < b.getValue() ? a : b;
+            return a.getValue() <= b.getValue() ? a : b;
         } else {
-            return a.getValue() > b.getValue() ? a : b;
+            return a.getValue() >= b.getValue() ? a : b;
         }
     }
 }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/univariate/BrentOptimizerTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/univariate/BrentOptimizerTest.java?rev=1382070&r1=1382069&r2=1382070&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/univariate/BrentOptimizerTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/univariate/BrentOptimizerTest.java
Fri Sep  7 15:43:40 2012
@@ -185,6 +185,43 @@ public final class BrentOptimizerTest {
     }
 
     /**
+     * Contrived example showing that prior to the resolution of MATH-855
+     * (second revision), the algorithm would not return the best point if
+     * it happened to be the initial guess.
+     */
+    @Test
+    public void testKeepInitIfBest() {
+        final double minSin = 3 * Math.PI / 2;
+        final double offset = 1e-8;
+        final double delta = 1e-7;
+        final UnivariateFunction f1 = new Sin();
+        final UnivariateFunction f2 = new StepFunction(new double[] { minSin, minSin + offset,
minSin + 2 * offset},
+                                                       new double[] { 0, -1, 0 });
+        final UnivariateFunction f = FunctionUtils.add(f1, f2);
+        // A slightly less stringent tolerance would make the test pass
+        // even with the previous implementation.
+        final double relTol = 1e-8;
+        final UnivariateOptimizer optimizer = new BrentOptimizer(relTol, 1e-100);
+        final double init = minSin + 1.5 * offset;
+        final UnivariatePointValuePair result
+            = optimizer.optimize(200, f, GoalType.MINIMIZE,
+                                 minSin - 6.789 * delta,
+                                 minSin + 9.876 * delta,
+                                 init);
+        final int numEval = optimizer.getEvaluations();
+
+        final double sol = result.getPoint();
+        final double expected = init;
+
+//         System.out.println("numEval=" + numEval);
+//         System.out.println("min=" + init + " f=" + f.value(init));
+//         System.out.println("sol=" + sol + " f=" + f.value(sol));
+//         System.out.println("exp=" + expected + " f=" + f.value(expected));
+
+        Assert.assertTrue("Best point not reported", f.value(sol) <= f.value(expected));
+    }
+
+    /**
      * Contrived example showing that prior to the resolution of MATH-855,
      * the algorithm, by always returning the last evaluated point, would
      * sometimes not report the best point it had found.
@@ -200,7 +237,9 @@ public final class BrentOptimizerTest {
         final UnivariateFunction f = FunctionUtils.add(f1, f2);
         final UnivariateOptimizer optimizer = new BrentOptimizer(1e-8, 1e-100);
         final UnivariatePointValuePair result
-            = optimizer.optimize(200, f, GoalType.MINIMIZE, minSin - 6.789 * delta, minSin
+ 9.876 * delta);
+            = optimizer.optimize(200, f, GoalType.MINIMIZE,
+                                 minSin - 6.789 * delta,
+                                 minSin + 9.876 * delta);
         final int numEval = optimizer.getEvaluations();
 
         final double sol = result.getPoint();



Mime
View raw message