commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r1569906 - in /commons/proper/math/trunk/src: changes/ main/java/org/apache/commons/math3/fitting/leastsquares/ test/java/org/apache/commons/math3/fitting/leastsquares/
Date Wed, 19 Feb 2014 20:32:20 GMT
Author: luc
Date: Wed Feb 19 20:32:20 2014
New Revision: 1569906

URL: http://svn.apache.org/r1569906
Log:
Add Cholesky option to GaussNewtonOptimizer

Since the normal matrix is symmetric positive (semi-)definite, the
Cholesky decomposition is theoretically faster.

Added:
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizerWithCholeskyTest.java
  (with props)
Modified:
    commons/proper/math/trunk/src/changes/changes.xml
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizer.java

Modified: commons/proper/math/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1569906&r1=1569905&r2=1569906&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Wed Feb 19 20:32:20 2014
@@ -52,6 +52,9 @@ If the output is not quite correct, chec
   <body>
     <release version="3.3" date="TBD" description="TBD">
       <action dev="luc" type="update" issue="MATH-1099" due-to="Evan Ward">
+	    Add Cholesky option to GaussNewtonOptimizer.
+	  </action>
+	  <action dev="luc" type="update" issue="MATH-1099" due-to="Evan Ward">
         Make QR in GaussNewton faster and more accurate.
       </action>
       <action dev="luc" type="update" issue="MATH-870">

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizer.java?rev=1569906&r1=1569905&r2=1569906&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizer.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizer.java
Wed Feb 19 20:32:20 2014
@@ -21,8 +21,10 @@ import org.apache.commons.math3.exceptio
 import org.apache.commons.math3.exception.util.LocalizedFormats;
 import org.apache.commons.math3.fitting.leastsquares.LeastSquaresProblem.Evaluation;
 import org.apache.commons.math3.linear.ArrayRealVector;
+import org.apache.commons.math3.linear.CholeskyDecomposition;
 import org.apache.commons.math3.linear.LUDecomposition;
 import org.apache.commons.math3.linear.MatrixUtils;
+import org.apache.commons.math3.linear.NonPositiveDefiniteMatrixException;
 import org.apache.commons.math3.linear.QRDecomposition;
 import org.apache.commons.math3.linear.RealMatrix;
 import org.apache.commons.math3.linear.RealVector;
@@ -50,7 +52,7 @@ public class GaussNewtonOptimizer implem
          * Solve by forming the normal equations (J<sup>T</sup>Jx=J<sup>T</sup>r)
and
          * using the {@link LUDecomposition}.
          *
-         * <p> Theoretically this method takes mn<sup>2></sup>/2 operations
to compute the
+         * <p> Theoretically this method takes mn<sup>2</sup>/2 operations
to compute the
          * normal matrix and n<sup>3</sup>/3 operations (m > n) to solve the
system using
          * the LU decomposition. </p>
          */
@@ -91,6 +93,32 @@ public class GaussNewtonOptimizer implem
                     throw new ConvergenceException(LocalizedFormats.UNABLE_TO_SOLVE_SINGULAR_PROBLEM);
                 }
             }
+        },
+        /**
+         * Solve by forming the normal equations (J<sup>T</sup>Jx=J<sup>T</sup>r)
and
+         * using the {@link CholeskyDecomposition}.
+         *
+         * <p> Theoretically this method takes mn<sup>2</sup>/2 operations
to compute the
+         * normal matrix and n<sup>3</sup>/6 operations (m > n) to solve the
system using
+         * the Cholesky decomposition. </p>
+         */
+        CHOLESKY {
+            @Override
+            protected RealVector solve(final RealMatrix jacobian,
+                                       final RealVector residuals) {
+                try {
+                    final Pair<RealMatrix, RealVector> normalEquation =
+                            computeNormalMatrix(jacobian, residuals);
+                    final RealMatrix normal = normalEquation.getFirst();
+                    final RealVector jTr = normalEquation.getSecond();
+                    return new CholeskyDecomposition(
+                            normal, SINGULARITY_THRESHOLD, SINGULARITY_THRESHOLD)
+                            .getSolver()
+                            .solve(jTr);
+                } catch (NonPositiveDefiniteMatrixException e) {
+                    throw new ConvergenceException(LocalizedFormats.UNABLE_TO_SOLVE_SINGULAR_PROBLEM);
+                }
+            }
         };
 
         /**

Added: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizerWithCholeskyTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizerWithCholeskyTest.java?rev=1569906&view=auto
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizerWithCholeskyTest.java
(added)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizerWithCholeskyTest.java
Wed Feb 19 20:32:20 2014
@@ -0,0 +1,134 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.commons.math3.fitting.leastsquares;
+
+import org.apache.commons.math3.exception.ConvergenceException;
+import org.apache.commons.math3.exception.TooManyEvaluationsException;
+import org.apache.commons.math3.fitting.leastsquares.GaussNewtonOptimizer.Decomposition;
+import org.apache.commons.math3.optim.SimpleVectorValueChecker;
+import org.junit.Test;
+
+import java.io.IOException;
+
+/**
+ * <p>Some of the unit tests are re-implementations of the MINPACK <a
+ * href="http://www.netlib.org/minpack/ex/file17">file17</a> and <a
+ * href="http://www.netlib.org/minpack/ex/file22">file22</a> test files.
+ * The redistribution policy for MINPACK is available <a
+ * href="http://www.netlib.org/minpack/disclaimer">here</a>/
+ *
+ * @version $Id$
+ */
+public class GaussNewtonOptimizerWithCholeskyTest
+    extends AbstractLeastSquaresOptimizerAbstractTest {
+
+    @Override
+    public int getMaxIterations() {
+        return 1000;
+    }
+
+    @Override
+    public LeastSquaresOptimizer getOptimizer() {
+        return new GaussNewtonOptimizer(Decomposition.CHOLESKY);
+    }
+
+    @Override
+    @Test
+    public void testMoreEstimatedParametersSimple() {
+        /*
+         * Exception is expected with this optimizer
+         */
+        try {
+            super.testMoreEstimatedParametersSimple();
+            fail(optimizer);
+        } catch (ConvergenceException e) {
+            //expected
+        }
+    }
+
+    @Override
+    @Test
+    public void testMoreEstimatedParametersUnsorted() {
+        /*
+         * Exception is expected with this optimizer
+         */
+        try{
+            super.testMoreEstimatedParametersUnsorted();
+            fail(optimizer);
+        }catch (ConvergenceException e){
+            //expected
+        }
+    }
+
+    @Test
+    public void testMaxEvaluations() throws Exception {
+        try{
+        CircleVectorial circle = new CircleVectorial();
+        circle.addPoint( 30.0,  68.0);
+        circle.addPoint( 50.0,  -6.0);
+        circle.addPoint(110.0, -20.0);
+        circle.addPoint( 35.0,  15.0);
+        circle.addPoint( 45.0,  97.0);
+
+        LeastSquaresProblem lsp = builder(circle)
+                .checkerPair(new SimpleVectorValueChecker(1e-30, 1e-30))
+                .maxIterations(Integer.MAX_VALUE)
+                .start(new double[]{98.680, 47.345})
+                .build();
+
+        optimizer.optimize(lsp);
+
+            fail(optimizer);
+        }catch (TooManyEvaluationsException e){
+            //expected
+        }
+    }
+
+    @Override
+    @Test
+    public void testCircleFittingBadInit() {
+        /*
+         * This test does not converge with this optimizer.
+         */
+        try{
+            super.testCircleFittingBadInit();
+            fail(optimizer);
+        }catch (ConvergenceException e){
+            //expected
+        }
+    }
+
+    @Override
+    @Test
+    public void testHahn1()
+        throws IOException {
+        /*
+         * TODO This test leads to a singular problem with the Gauss-Newton
+         * optimizer. This should be inquired.
+         */
+        try{
+            super.testHahn1();
+            fail(optimizer);
+        } catch (ConvergenceException e){
+            //expected for LU
+        } catch (TooManyEvaluationsException e){
+            //expected for QR
+        }
+    }
+
+}

Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizerWithCholeskyTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/fitting/leastsquares/GaussNewtonOptimizerWithCholeskyTest.java
------------------------------------------------------------------------------
    svn:keywords = "Author Date Id Revision"



Mime
View raw message