internal/ceres/system_test.cc

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2015 Google Inc. All rights reserved.
   3 // http://ceres-solver.org/
   4 //
   5 // Redistribution and use in source and binary forms, with or without
   6 // modification, are permitted provided that the following conditions are met:
   7 //
   8 // * Redistributions of source code must retain the above copyright notice,
   9 //   this list of conditions and the following disclaimer.
  10 // * Redistributions in binary form must reproduce the above copyright notice,
  11 //   this list of conditions and the following disclaimer in the documentation
  12 //   and/or other materials provided with the distribution.
  13 // * Neither the name of Google Inc. nor the names of its contributors may be
  14 //   used to endorse or promote products derived from this software without
  15 //   specific prior written permission.
  16 //
  17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27 // POSSIBILITY OF SUCH DAMAGE.
  28 //
  29 // Author: keir@google.com (Keir Mierle)
  30 //         sameeragarwal@google.com (Sameer Agarwal)
  31 //
  32 // End-to-end tests for Ceres using Powell's function.
  33
  34 #include <cmath>
  35 #include <cstdlib>
  36
  37 #include "ceres/autodiff_cost_function.h"
  38 #include "ceres/problem.h"
  39 #include "ceres/solver.h"
  40 #include "ceres/test_util.h"
  41 #include "ceres/types.h"
  42 #include "glog/logging.h"
  43 #include "gtest/gtest.h"
  44
  45 namespace ceres {
  46 namespace internal {
  47
  48 // This class implements the SystemTestProblem interface and provides
  49 // access to an implementation of Powell's singular function.
  50 //
  51 //   F = 1/2 (f1^2 + f2^2 + f3^2 + f4^2)
  52 //
  53 //   f1 = x1 + 10*x2;
  54 //   f2 = sqrt(5) * (x3 - x4)
  55 //   f3 = (x2 - 2*x3)^2
  56 //   f4 = sqrt(10) * (x1 - x4)^2
  57 //
  58 // The starting values are x1 = 3, x2 = -1, x3 = 0, x4 = 1.
  59 // The minimum is 0 at (x1, x2, x3, x4) = 0.
  60 //
  61 // From: Testing Unconstrained Optimization Software by Jorge J. More, Burton S.
  62 // Garbow and Kenneth E. Hillstrom in ACM Transactions on Mathematical Software,
  63 // Vol 7(1), March 1981.
  64 class PowellsFunction {
  65  public:
  66   PowellsFunction() {
  67     x_[0] =  3.0;
  68     x_[1] = -1.0;
  69     x_[2] =  0.0;
  70     x_[3] =  1.0;
  71
  72     problem_.AddResidualBlock(
  73         new AutoDiffCostFunction<F1, 1, 1, 1>(new F1), NULL, &x_[0], &x_[1]);
  74     problem_.AddResidualBlock(
  75         new AutoDiffCostFunction<F2, 1, 1, 1>(new F2), NULL, &x_[2], &x_[3]);
  76     problem_.AddResidualBlock(
  77         new AutoDiffCostFunction<F3, 1, 1, 1>(new F3), NULL, &x_[1], &x_[2]);
  78     problem_.AddResidualBlock(
  79         new AutoDiffCostFunction<F4, 1, 1, 1>(new F4), NULL, &x_[0], &x_[3]);
  80
  81     // Settings for the reference solution.
  82     options_.linear_solver_type = ceres::DENSE_QR;
  83     options_.max_num_iterations = 10;
  84     options_.num_threads = 1;
  85   }
  86
  87   Problem* mutable_problem() { return &problem_; }
  88   Solver::Options* mutable_solver_options() { return &options_; }
  89
  90   static double kResidualTolerance;
  91
  92  private:
  93   // Templated functions used for automatically differentiated cost
  94   // functions.
  95   class F1 {
  96    public:
  97     template <typename T> bool operator()(const T* const x1,
  98                                           const T* const x2,
  99                                           T* residual) const {
 100       // f1 = x1 + 10 * x2;
 101       *residual = *x1 + 10.0 * *x2;
 102       return true;
 103     }
 104   };
 105
 106   class F2 {
 107    public:
 108     template <typename T> bool operator()(const T* const x3,
 109                                           const T* const x4,
 110                                           T* residual) const {
 111       // f2 = sqrt(5) (x3 - x4)
 112       *residual = sqrt(5.0) * (*x3 - *x4);
 113       return true;
 114     }
 115   };
 116
 117   class F3 {
 118    public:
 119     template <typename T> bool operator()(const T* const x2,
 120                                           const T* const x4,
 121                                           T* residual) const {
 122       // f3 = (x2 - 2 x3)^2
 123       residual[0] = (x2[0] - 2.0 * x4[0]) * (x2[0] - 2.0 * x4[0]);
 124       return true;
 125     }
 126   };
 127
 128   class F4 {
 129    public:
 130     template <typename T> bool operator()(const T* const x1,
 131                                           const T* const x4,
 132                                           T* residual) const {
 133       // f4 = sqrt(10) (x1 - x4)^2
 134       residual[0] = sqrt(10.0) * (x1[0] - x4[0]) * (x1[0] - x4[0]);
 135       return true;
 136     }
 137   };
 138
 139   double x_[4];
 140   Problem problem_;
 141   Solver::Options options_;
 142 };
 143
 144 double PowellsFunction::kResidualTolerance = 1e-8;
 145
 146 typedef SystemTest<PowellsFunction> PowellTest;
 147 const bool kAutomaticOrdering = true;
 148
 149 TEST_F(PowellTest, DenseQR) {
 150   RunSolverForConfigAndExpectResidualsMatch(
 151       SolverConfig(DENSE_QR, NO_SPARSE));
 152 }
 153
 154 TEST_F(PowellTest, DenseNormalCholesky) {
 155   RunSolverForConfigAndExpectResidualsMatch(
 156       SolverConfig(DENSE_NORMAL_CHOLESKY));
 157 }
 158
 159 TEST_F(PowellTest, DenseSchur) {
 160   RunSolverForConfigAndExpectResidualsMatch(
 161       SolverConfig(DENSE_SCHUR));
 162 }
 163
 164 TEST_F(PowellTest, IterativeSchurWithJacobi) {
 165   RunSolverForConfigAndExpectResidualsMatch(
 166       SolverConfig(ITERATIVE_SCHUR, NO_SPARSE, kAutomaticOrdering, JACOBI));
 167 }
 168
 169 #ifndef CERES_NO_SUITESPARSE
 170 TEST_F(PowellTest, SparseNormalCholeskyUsingSuiteSparse) {
 171   RunSolverForConfigAndExpectResidualsMatch(
 172       SolverConfig(SPARSE_NORMAL_CHOLESKY, SUITE_SPARSE, kAutomaticOrdering));
 173 }
 174 #endif  // CERES_NO_SUITESPARSE
 175
 176 #ifndef CERES_NO_CXSPARSE
 177 TEST_F(PowellTest, SparseNormalCholeskyUsingCXSparse) {
 178   RunSolverForConfigAndExpectResidualsMatch(
 179       SolverConfig(SPARSE_NORMAL_CHOLESKY, CX_SPARSE, kAutomaticOrdering));
 180 }
 181 #endif  // CERES_NO_CXSPARSE
 182
 183 #ifdef CERES_USE_EIGEN_SPARSE
 184 TEST_F(PowellTest, SparseNormalCholeskyUsingEigenSparse) {
 185   RunSolverForConfigAndExpectResidualsMatch(
 186       SolverConfig(SPARSE_NORMAL_CHOLESKY, EIGEN_SPARSE, kAutomaticOrdering));
 187 }
 188 #endif  // CERES_USE_EIGEN_SPARSE
 189
 190 }  // namespace internal
 191 }  // namespace ceres