internal/ceres/trust_region_preprocessor_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: sameeragarwal@google.com (Sameer Agarwal)
  30
  31 #include <map>
  32
  33 #include "ceres/ordered_groups.h"
  34 #include "ceres/problem_impl.h"
  35 #include "ceres/sized_cost_function.h"
  36 #include "ceres/solver.h"
  37 #include "ceres/trust_region_preprocessor.h"
  38 #include "gtest/gtest.h"
  39
  40 namespace ceres {
  41 namespace internal {
  42
  43 TEST(TrustRegionPreprocessor, ZeroProblem) {
  44   ProblemImpl problem;
  45   Solver::Options options;
  46   TrustRegionPreprocessor preprocessor;
  47   PreprocessedProblem pp;
  48   EXPECT_TRUE(preprocessor.Preprocess(options, &problem, &pp));
  49 }
  50
  51 TEST(TrustRegionPreprocessor, ProblemWithInvalidParameterBlock) {
  52   ProblemImpl problem;
  53   double x = std::numeric_limits<double>::quiet_NaN();
  54   problem.AddParameterBlock(&x, 1);
  55   Solver::Options options;
  56   TrustRegionPreprocessor preprocessor;
  57   PreprocessedProblem pp;
  58   EXPECT_FALSE(preprocessor.Preprocess(options, &problem, &pp));
  59 }
  60
  61 TEST(TrustRegionPreprocessor, ParameterBlockBoundsAreInvalid) {
  62   ProblemImpl problem;
  63   double x = 1.0;
  64   problem.AddParameterBlock(&x, 1);
  65   problem.SetParameterUpperBound(&x, 0, 1.0);
  66   problem.SetParameterLowerBound(&x, 0, 2.0);
  67   Solver::Options options;
  68   TrustRegionPreprocessor preprocessor;
  69   PreprocessedProblem pp;
  70   EXPECT_FALSE(preprocessor.Preprocess(options, &problem, &pp));
  71 }
  72
  73 TEST(TrustRegionPreprocessor, ParamterBlockIsInfeasible) {
  74   ProblemImpl problem;
  75   double x = 3.0;
  76   problem.AddParameterBlock(&x, 1);
  77   problem.SetParameterUpperBound(&x, 0, 1.0);
  78   problem.SetParameterLowerBound(&x, 0, 2.0);
  79   problem.SetParameterBlockConstant(&x);
  80   Solver::Options options;
  81   TrustRegionPreprocessor preprocessor;
  82   PreprocessedProblem pp;
  83   EXPECT_FALSE(preprocessor.Preprocess(options, &problem, &pp));
  84 }
  85
  86 class FailingCostFunction : public SizedCostFunction<1, 1> {
  87  public:
  88   bool Evaluate(double const* const* parameters,
  89                 double* residuals,
  90                 double** jacobians) const {
  91     return false;
  92   }
  93 };
  94
  95 TEST(TrustRegionPreprocessor, RemoveParameterBlocksFailed) {
  96   ProblemImpl problem;
  97   double x = 3.0;
  98   problem.AddResidualBlock(new FailingCostFunction, NULL, &x);
  99   problem.SetParameterBlockConstant(&x);
 100   Solver::Options options;
 101   TrustRegionPreprocessor preprocessor;
 102   PreprocessedProblem pp;
 103   EXPECT_FALSE(preprocessor.Preprocess(options, &problem, &pp));
 104 }
 105
 106 TEST(TrustRegionPreprocessor, RemoveParameterBlocksSucceeds) {
 107   ProblemImpl problem;
 108   double x = 3.0;
 109   problem.AddParameterBlock(&x, 1);
 110   Solver::Options options;
 111   TrustRegionPreprocessor preprocessor;
 112   PreprocessedProblem pp;
 113   EXPECT_TRUE(preprocessor.Preprocess(options, &problem, &pp));
 114 }
 115
 116 template<int kNumResiduals, int N1 = 0, int N2 = 0, int N3 = 0>
 117 class DummyCostFunction : public SizedCostFunction<kNumResiduals, N1, N2, N3> {
 118  public:
 119   bool Evaluate(double const* const* parameters,
 120                 double* residuals,
 121                 double** jacobians) const {
 122     for (int i = 0; i < kNumResiduals; ++i) {
 123       residuals[i] = kNumResiduals * kNumResiduals + i;
 124     }
 125
 126     if (jacobians == NULL) {
 127       return true;
 128     }
 129
 130     if (jacobians[0] != NULL) {
 131       MatrixRef j(jacobians[0], kNumResiduals, N1);
 132       j.setOnes();
 133       j *= kNumResiduals * N1;
 134     }
 135
 136     if (N2 == 0) {
 137       return true;
 138     }
 139
 140     if (jacobians[1] != NULL) {
 141       MatrixRef j(jacobians[1], kNumResiduals, N2);
 142       j.setOnes();
 143       j *= kNumResiduals * N2;
 144     }
 145
 146     if (N3 == 0) {
 147       return true;
 148     }
 149
 150     if (jacobians[2] != NULL) {
 151       MatrixRef j(jacobians[2], kNumResiduals, N3);
 152       j.setOnes();
 153       j *= kNumResiduals * N3;
 154     }
 155
 156     return true;
 157   }
 158 };
 159
 160 class LinearSolverAndEvaluatorCreationTest : public ::testing::Test {
 161  public:
 162   virtual void SetUp() {
 163     x_ = 1.0;
 164     y_ = 1.0;
 165     z_ = 1.0;
 166     problem_.AddResidualBlock(new DummyCostFunction<1, 1, 1>, NULL, &x_, &y_);
 167     problem_.AddResidualBlock(new DummyCostFunction<1, 1, 1>, NULL, &y_, &z_);
 168   }
 169
 170   void PreprocessForGivenLinearSolverAndVerify(
 171       const LinearSolverType linear_solver_type) {
 172     Solver::Options options;
 173     options.linear_solver_type = linear_solver_type;
 174     TrustRegionPreprocessor preprocessor;
 175     PreprocessedProblem pp;
 176     EXPECT_TRUE(preprocessor.Preprocess(options, &problem_, &pp));
 177     EXPECT_EQ(pp.options.linear_solver_type, linear_solver_type);
 178     EXPECT_EQ(pp.linear_solver_options.type, linear_solver_type);
 179     EXPECT_EQ(pp.evaluator_options.linear_solver_type, linear_solver_type);
 180     EXPECT_TRUE(pp.linear_solver.get() != NULL);
 181     EXPECT_TRUE(pp.evaluator.get() != NULL);
 182   }
 183
 184  protected:
 185   ProblemImpl problem_;
 186   double x_;
 187   double y_;
 188   double z_;
 189 };
 190
 191 TEST_F(LinearSolverAndEvaluatorCreationTest, DenseQR) {
 192   PreprocessForGivenLinearSolverAndVerify(DENSE_QR);
 193 }
 194
 195 TEST_F(LinearSolverAndEvaluatorCreationTest, DenseNormalCholesky) {
 196   PreprocessForGivenLinearSolverAndVerify(DENSE_NORMAL_CHOLESKY);
 197 }
 198
 199 TEST_F(LinearSolverAndEvaluatorCreationTest, DenseSchur) {
 200   PreprocessForGivenLinearSolverAndVerify(DENSE_SCHUR);
 201 }
 202
 203 #if defined(CERES_USE_EIGEN_SPARSE) || \
 204   !defined(CERES_NO_SUITESPARSE) ||   \
 205   !defined(CERES_NO_CXSPARSE)
 206 TEST_F(LinearSolverAndEvaluatorCreationTest, SparseNormalCholesky) {
 207   PreprocessForGivenLinearSolverAndVerify(SPARSE_NORMAL_CHOLESKY);
 208 }
 209 #endif
 210
 211 #if defined(CERES_USE_EIGEN_SPARSE) || \
 212   !defined(CERES_NO_SUITESPARSE) ||   \
 213   !defined(CERES_NO_CXSPARSE)
 214 TEST_F(LinearSolverAndEvaluatorCreationTest, SparseSchur) {
 215   PreprocessForGivenLinearSolverAndVerify(SPARSE_SCHUR);
 216 }
 217 #endif
 218
 219 TEST_F(LinearSolverAndEvaluatorCreationTest, CGNR) {
 220   PreprocessForGivenLinearSolverAndVerify(CGNR);
 221 }
 222
 223 TEST_F(LinearSolverAndEvaluatorCreationTest, IterativeSchur) {
 224   PreprocessForGivenLinearSolverAndVerify(ITERATIVE_SCHUR);
 225 }
 226
 227 TEST_F(LinearSolverAndEvaluatorCreationTest, MinimizerIsAwareOfBounds) {
 228   problem_.SetParameterLowerBound(&x_, 0, 0.0);
 229   Solver::Options options;
 230   TrustRegionPreprocessor preprocessor;
 231   PreprocessedProblem pp;
 232   EXPECT_TRUE(preprocessor.Preprocess(options, &problem_, &pp));
 233   EXPECT_EQ(pp.options.linear_solver_type, options.linear_solver_type);
 234   EXPECT_EQ(pp.linear_solver_options.type, options.linear_solver_type);
 235   EXPECT_EQ(pp.evaluator_options.linear_solver_type,
 236             options.linear_solver_type);
 237   EXPECT_TRUE(pp.linear_solver.get() != NULL);
 238   EXPECT_TRUE(pp.evaluator.get() != NULL);
 239   EXPECT_TRUE(pp.minimizer_options.is_constrained);
 240 }
 241
 242 TEST_F(LinearSolverAndEvaluatorCreationTest, SchurTypeSolverWithBadOrdering) {
 243   Solver::Options options;
 244   options.linear_solver_type = DENSE_SCHUR;
 245   options.linear_solver_ordering.reset(new ParameterBlockOrdering);
 246   options.linear_solver_ordering->AddElementToGroup(&x_, 0);
 247   options.linear_solver_ordering->AddElementToGroup(&y_, 0);
 248   options.linear_solver_ordering->AddElementToGroup(&z_, 1);
 249
 250   TrustRegionPreprocessor preprocessor;
 251   PreprocessedProblem pp;
 252   EXPECT_FALSE(preprocessor.Preprocess(options, &problem_, &pp));
 253 }
 254
 255 TEST_F(LinearSolverAndEvaluatorCreationTest, SchurTypeSolverWithGoodOrdering) {
 256   Solver::Options options;
 257   options.linear_solver_type = DENSE_SCHUR;
 258   options.linear_solver_ordering.reset(new ParameterBlockOrdering);
 259   options.linear_solver_ordering->AddElementToGroup(&x_, 0);
 260   options.linear_solver_ordering->AddElementToGroup(&z_, 0);
 261   options.linear_solver_ordering->AddElementToGroup(&y_, 1);
 262
 263   TrustRegionPreprocessor preprocessor;
 264   PreprocessedProblem pp;
 265   EXPECT_TRUE(preprocessor.Preprocess(options, &problem_, &pp));
 266   EXPECT_EQ(pp.options.linear_solver_type, DENSE_SCHUR);
 267   EXPECT_EQ(pp.linear_solver_options.type, DENSE_SCHUR);
 268   EXPECT_EQ(pp.evaluator_options.linear_solver_type, DENSE_SCHUR);
 269   EXPECT_TRUE(pp.linear_solver.get() != NULL);
 270   EXPECT_TRUE(pp.evaluator.get() != NULL);
 271 }
 272
 273 TEST_F(LinearSolverAndEvaluatorCreationTest,
 274        SchurTypeSolverWithEmptyFirstEliminationGroup) {
 275   problem_.SetParameterBlockConstant(&x_);
 276   problem_.SetParameterBlockConstant(&z_);
 277
 278   Solver::Options options;
 279   options.linear_solver_type = DENSE_SCHUR;
 280   options.linear_solver_ordering.reset(new ParameterBlockOrdering);
 281   options.linear_solver_ordering->AddElementToGroup(&x_, 0);
 282   options.linear_solver_ordering->AddElementToGroup(&z_, 0);
 283   options.linear_solver_ordering->AddElementToGroup(&y_, 1);
 284
 285   TrustRegionPreprocessor preprocessor;
 286   PreprocessedProblem pp;
 287   EXPECT_TRUE(preprocessor.Preprocess(options, &problem_, &pp));
 288   EXPECT_EQ(pp.options.linear_solver_type, DENSE_QR);
 289   EXPECT_EQ(pp.linear_solver_options.type, DENSE_QR);
 290   EXPECT_EQ(pp.evaluator_options.linear_solver_type, DENSE_QR);
 291   EXPECT_TRUE(pp.linear_solver.get() != NULL);
 292   EXPECT_TRUE(pp.evaluator.get() != NULL);
 293 }
 294
 295 TEST_F(LinearSolverAndEvaluatorCreationTest,
 296        SchurTypeSolverWithEmptySecondEliminationGroup) {
 297   problem_.SetParameterBlockConstant(&y_);
 298
 299   Solver::Options options;
 300   options.linear_solver_type = DENSE_SCHUR;
 301   options.linear_solver_ordering.reset(new ParameterBlockOrdering);
 302   options.linear_solver_ordering->AddElementToGroup(&x_, 0);
 303   options.linear_solver_ordering->AddElementToGroup(&z_, 0);
 304   options.linear_solver_ordering->AddElementToGroup(&y_, 1);
 305
 306   TrustRegionPreprocessor preprocessor;
 307   PreprocessedProblem pp;
 308   EXPECT_TRUE(preprocessor.Preprocess(options, &problem_, &pp));
 309   EXPECT_EQ(pp.options.linear_solver_type, DENSE_SCHUR);
 310   EXPECT_EQ(pp.linear_solver_options.type, DENSE_SCHUR);
 311   EXPECT_EQ(pp.evaluator_options.linear_solver_type, DENSE_SCHUR);
 312   EXPECT_TRUE(pp.linear_solver.get() != NULL);
 313   EXPECT_TRUE(pp.evaluator.get() != NULL);
 314 }
 315
 316 TEST(TrustRegionPreprocessorTest, InnerIterationsWithOneParameterBlock) {
 317   ProblemImpl problem;
 318   double x = 1.0;
 319   problem.AddResidualBlock(new DummyCostFunction<1, 1>, NULL, &x);
 320
 321   Solver::Options options;
 322   options.use_inner_iterations = true;
 323
 324   TrustRegionPreprocessor preprocessor;
 325   PreprocessedProblem pp;
 326   EXPECT_TRUE(preprocessor.Preprocess(options, &problem, &pp));
 327   EXPECT_TRUE(pp.linear_solver.get() != NULL);
 328   EXPECT_TRUE(pp.evaluator.get() != NULL);
 329   EXPECT_TRUE(pp.inner_iteration_minimizer.get() == NULL);
 330 }
 331
 332 TEST_F(LinearSolverAndEvaluatorCreationTest,
 333        InnerIterationsWithTwoParameterBlocks) {
 334   Solver::Options options;
 335   options.use_inner_iterations = true;
 336
 337   TrustRegionPreprocessor preprocessor;
 338   PreprocessedProblem pp;
 339   EXPECT_TRUE(preprocessor.Preprocess(options, &problem_, &pp));
 340   EXPECT_TRUE(pp.linear_solver.get() != NULL);
 341   EXPECT_TRUE(pp.evaluator.get() != NULL);
 342   EXPECT_TRUE(pp.inner_iteration_minimizer.get() != NULL);
 343 }
 344
 345 TEST_F(LinearSolverAndEvaluatorCreationTest,
 346        InvalidInnerIterationsOrdering) {
 347   Solver::Options options;
 348   options.use_inner_iterations = true;
 349   options.inner_iteration_ordering.reset(new ParameterBlockOrdering);
 350   options.inner_iteration_ordering->AddElementToGroup(&x_, 0);
 351   options.inner_iteration_ordering->AddElementToGroup(&z_, 0);
 352   options.inner_iteration_ordering->AddElementToGroup(&y_, 0);
 353
 354   TrustRegionPreprocessor preprocessor;
 355   PreprocessedProblem pp;
 356   EXPECT_FALSE(preprocessor.Preprocess(options, &problem_, &pp));
 357 }
 358
 359 TEST_F(LinearSolverAndEvaluatorCreationTest, ValidInnerIterationsOrdering) {
 360   Solver::Options options;
 361   options.use_inner_iterations = true;
 362   options.inner_iteration_ordering.reset(new ParameterBlockOrdering);
 363   options.inner_iteration_ordering->AddElementToGroup(&x_, 0);
 364   options.inner_iteration_ordering->AddElementToGroup(&z_, 0);
 365   options.inner_iteration_ordering->AddElementToGroup(&y_, 1);
 366
 367   TrustRegionPreprocessor preprocessor;
 368   PreprocessedProblem pp;
 369   EXPECT_TRUE(preprocessor.Preprocess(options, &problem_, &pp));
 370   EXPECT_TRUE(pp.linear_solver.get() != NULL);
 371   EXPECT_TRUE(pp.evaluator.get() != NULL);
 372   EXPECT_TRUE(pp.inner_iteration_minimizer.get() != NULL);
 373 }
 374
 375 }  // namespace internal
 376 }  // namespace ceres