blob: 8f68fec4c466feb65abc86d4a4c3a10e45032bf4 [file] [log] [blame]
// Ceres Solver - A fast non-linear least squares minimizer
// Copyright 2015 Google Inc. All rights reserved.
// http://ceres-solver.org/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
// * Neither the name of Google Inc. nor the names of its contributors may be
// used to endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
// Author: sameeragarwal@google.com (Sameer Agarwal)
#include "ceres/solver.h"
#include <limits>
#include <memory>
#include <cmath>
#include <vector>
#include "gtest/gtest.h"
#include "ceres/evaluation_callback.h"
#include "ceres/autodiff_cost_function.h"
#include "ceres/sized_cost_function.h"
#include "ceres/problem.h"
#include "ceres/problem_impl.h"
namespace ceres {
namespace internal {
using std::string;
TEST(SolverOptions, DefaultTrustRegionOptionsAreValid) {
Solver::Options options;
options.minimizer_type = TRUST_REGION;
string error;
EXPECT_TRUE(options.IsValid(&error)) << error;
}
TEST(SolverOptions, DefaultLineSearchOptionsAreValid) {
Solver::Options options;
options.minimizer_type = LINE_SEARCH;
string error;
EXPECT_TRUE(options.IsValid(&error)) << error;
}
struct QuadraticCostFunctor {
template <typename T> bool operator()(const T* const x,
T* residual) const {
residual[0] = T(5.0) - *x;
return true;
}
static CostFunction* Create() {
return new AutoDiffCostFunction<QuadraticCostFunctor, 1, 1>(
new QuadraticCostFunctor);
}
};
struct RememberingCallback : public IterationCallback {
explicit RememberingCallback(double *x) : calls(0), x(x) {}
virtual ~RememberingCallback() {}
virtual CallbackReturnType operator()(const IterationSummary& summary) {
x_values.push_back(*x);
return SOLVER_CONTINUE;
}
int calls;
double *x;
std::vector<double> x_values;
};
struct NoOpEvaluationCallback : EvaluationCallback {
virtual ~NoOpEvaluationCallback() {}
virtual void PrepareForEvaluation(bool evaluate_jacobians,
bool new_evaluation_point) {
(void) evaluate_jacobians;
(void) new_evaluation_point;
}
};
TEST(Solver, UpdateStateEveryIterationOption) {
double x = 50.0;
const double original_x = x;
std::unique_ptr<CostFunction> cost_function(QuadraticCostFunctor::Create());
Problem::Options problem_options;
problem_options.cost_function_ownership = DO_NOT_TAKE_OWNERSHIP;
Problem problem(problem_options);
problem.AddResidualBlock(cost_function.get(), NULL, &x);
Solver::Options options;
options.linear_solver_type = DENSE_QR;
RememberingCallback callback(&x);
options.callbacks.push_back(&callback);
Solver::Summary summary;
int num_iterations;
// There are four cases that need to be checked:
//
// (update_state_every_iteration = true|false) X
// (evaluation_callback = NULL|provided)
//
// These need to get checked since there is some interaction between them.
// First: update_state_every_iteration=false, evaluation_callback=NULL.
Solve(options, &problem, &summary);
num_iterations = summary.num_successful_steps +
summary.num_unsuccessful_steps;
EXPECT_GT(num_iterations, 1);
for (int i = 0; i < callback.x_values.size(); ++i) {
EXPECT_EQ(50.0, callback.x_values[i]);
}
// Second: update_state_every_iteration=true, evaluation_callback=NULL.
x = 50.0;
options.update_state_every_iteration = true;
callback.x_values.clear();
Solve(options, &problem, &summary);
num_iterations = summary.num_successful_steps +
summary.num_unsuccessful_steps;
EXPECT_GT(num_iterations, 1);
EXPECT_EQ(original_x, callback.x_values[0]);
EXPECT_NE(original_x, callback.x_values[1]);
NoOpEvaluationCallback evaluation_callback;
// Third: update_state_every_iteration=true, evaluation_callback=!NULL.
x = 50.0;
options.update_state_every_iteration = true;
options.evaluation_callback = &evaluation_callback;
callback.x_values.clear();
Solve(options, &problem, &summary);
num_iterations = summary.num_successful_steps +
summary.num_unsuccessful_steps;
EXPECT_GT(num_iterations, 1);
EXPECT_EQ(original_x, callback.x_values[0]);
EXPECT_NE(original_x, callback.x_values[1]);
// Fourth: update_state_every_iteration=false, evaluation_callback=!NULL.
x = 50.0;
options.update_state_every_iteration = false;
options.evaluation_callback = &evaluation_callback;
callback.x_values.clear();
Solve(options, &problem, &summary);
num_iterations = summary.num_successful_steps +
summary.num_unsuccessful_steps;
EXPECT_GT(num_iterations, 1);
EXPECT_EQ(original_x, callback.x_values[0]);
EXPECT_NE(original_x, callback.x_values[1]);
}
// The parameters must be in separate blocks so that they can be individually
// set constant or not.
struct Quadratic4DCostFunction {
template <typename T> bool operator()(const T* const x,
const T* const y,
const T* const z,
const T* const w,
T* residual) const {
// A 4-dimension axis-aligned quadratic.
residual[0] = T(10.0) - *x +
T(20.0) - *y +
T(30.0) - *z +
T(40.0) - *w;
return true;
}
static CostFunction* Create() {
return new AutoDiffCostFunction<Quadratic4DCostFunction, 1, 1, 1, 1, 1>(
new Quadratic4DCostFunction);
}
};
// A cost function that simply returns its argument.
class UnaryIdentityCostFunction : public SizedCostFunction<1, 1> {
public:
virtual bool Evaluate(double const* const* parameters,
double* residuals,
double** jacobians) const {
residuals[0] = parameters[0][0];
if (jacobians != NULL && jacobians[0] != NULL) {
jacobians[0][0] = 1.0;
}
return true;
}
};
TEST(Solver, TrustRegionProblemHasNoParameterBlocks) {
Problem problem;
Solver::Options options;
options.minimizer_type = TRUST_REGION;
Solver::Summary summary;
Solve(options, &problem, &summary);
EXPECT_EQ(summary.termination_type, CONVERGENCE);
EXPECT_EQ(summary.message,
"Function tolerance reached. "
"No non-constant parameter blocks found.");
}
TEST(Solver, LineSearchProblemHasNoParameterBlocks) {
Problem problem;
Solver::Options options;
options.minimizer_type = LINE_SEARCH;
Solver::Summary summary;
Solve(options, &problem, &summary);
EXPECT_EQ(summary.termination_type, CONVERGENCE);
EXPECT_EQ(summary.message,
"Function tolerance reached. "
"No non-constant parameter blocks found.");
}
TEST(Solver, TrustRegionProblemHasZeroResiduals) {
Problem problem;
double x = 1;
problem.AddParameterBlock(&x, 1);
Solver::Options options;
options.minimizer_type = TRUST_REGION;
Solver::Summary summary;
Solve(options, &problem, &summary);
EXPECT_EQ(summary.termination_type, CONVERGENCE);
EXPECT_EQ(summary.message,
"Function tolerance reached. "
"No non-constant parameter blocks found.");
}
TEST(Solver, LineSearchProblemHasZeroResiduals) {
Problem problem;
double x = 1;
problem.AddParameterBlock(&x, 1);
Solver::Options options;
options.minimizer_type = LINE_SEARCH;
Solver::Summary summary;
Solve(options, &problem, &summary);
EXPECT_EQ(summary.termination_type, CONVERGENCE);
EXPECT_EQ(summary.message,
"Function tolerance reached. "
"No non-constant parameter blocks found.");
}
TEST(Solver, TrustRegionProblemIsConstant) {
Problem problem;
double x = 1;
problem.AddResidualBlock(new UnaryIdentityCostFunction, NULL, &x);
problem.SetParameterBlockConstant(&x);
Solver::Options options;
options.minimizer_type = TRUST_REGION;
Solver::Summary summary;
Solve(options, &problem, &summary);
EXPECT_EQ(summary.termination_type, CONVERGENCE);
EXPECT_EQ(summary.initial_cost, 1.0 / 2.0);
EXPECT_EQ(summary.final_cost, 1.0 / 2.0);
}
TEST(Solver, LineSearchProblemIsConstant) {
Problem problem;
double x = 1;
problem.AddResidualBlock(new UnaryIdentityCostFunction, NULL, &x);
problem.SetParameterBlockConstant(&x);
Solver::Options options;
options.minimizer_type = LINE_SEARCH;
Solver::Summary summary;
Solve(options, &problem, &summary);
EXPECT_EQ(summary.termination_type, CONVERGENCE);
EXPECT_EQ(summary.initial_cost, 1.0 / 2.0);
EXPECT_EQ(summary.final_cost, 1.0 / 2.0);
}
#if defined(CERES_NO_SUITESPARSE)
TEST(Solver, SparseNormalCholeskyNoSuiteSparse) {
Solver::Options options;
options.sparse_linear_algebra_library_type = SUITE_SPARSE;
options.linear_solver_type = SPARSE_NORMAL_CHOLESKY;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, SparseSchurNoSuiteSparse) {
Solver::Options options;
options.sparse_linear_algebra_library_type = SUITE_SPARSE;
options.linear_solver_type = SPARSE_SCHUR;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
#endif
#if defined(CERES_NO_CXSPARSE)
TEST(Solver, SparseNormalCholeskyNoCXSparse) {
Solver::Options options;
options.sparse_linear_algebra_library_type = CX_SPARSE;
options.linear_solver_type = SPARSE_NORMAL_CHOLESKY;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, SparseSchurNoCXSparse) {
Solver::Options options;
options.sparse_linear_algebra_library_type = CX_SPARSE;
options.linear_solver_type = SPARSE_SCHUR;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
#endif
#if !defined(CERES_USE_EIGEN_SPARSE)
TEST(Solver, SparseNormalCholeskyNoEigenSparse) {
Solver::Options options;
options.sparse_linear_algebra_library_type = EIGEN_SPARSE;
options.linear_solver_type = SPARSE_NORMAL_CHOLESKY;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, SparseSchurNoEigenSparse) {
Solver::Options options;
options.sparse_linear_algebra_library_type = EIGEN_SPARSE;
options.linear_solver_type = SPARSE_SCHUR;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
#endif
TEST(Solver, SparseNormalCholeskyNoSparseLibrary) {
Solver::Options options;
options.sparse_linear_algebra_library_type = NO_SPARSE;
options.linear_solver_type = SPARSE_NORMAL_CHOLESKY;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, SparseSchurNoSparseLibrary) {
Solver::Options options;
options.sparse_linear_algebra_library_type = NO_SPARSE;
options.linear_solver_type = SPARSE_SCHUR;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, IterativeSchurWithClusterJacobiPerconditionerNoSparseLibrary) {
Solver::Options options;
options.sparse_linear_algebra_library_type = NO_SPARSE;
options.linear_solver_type = ITERATIVE_SCHUR;
// Requires SuiteSparse.
options.preconditioner_type = CLUSTER_JACOBI;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, IterativeSchurWithClusterTridiagonalPerconditionerNoSparseLibrary) {
Solver::Options options;
options.sparse_linear_algebra_library_type = NO_SPARSE;
options.linear_solver_type = ITERATIVE_SCHUR;
// Requires SuiteSparse.
options.preconditioner_type = CLUSTER_TRIDIAGONAL;
string message;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, IterativeLinearSolverForDogleg) {
Solver::Options options;
options.trust_region_strategy_type = DOGLEG;
string message;
options.linear_solver_type = ITERATIVE_SCHUR;
EXPECT_FALSE(options.IsValid(&message));
options.linear_solver_type = CGNR;
EXPECT_FALSE(options.IsValid(&message));
}
TEST(Solver, LinearSolverTypeNormalOperation) {
Solver::Options options;
options.linear_solver_type = DENSE_QR;
string message;
EXPECT_TRUE(options.IsValid(&message));
options.linear_solver_type = DENSE_NORMAL_CHOLESKY;
EXPECT_TRUE(options.IsValid(&message));
options.linear_solver_type = DENSE_SCHUR;
EXPECT_TRUE(options.IsValid(&message));
options.linear_solver_type = SPARSE_SCHUR;
#if defined(CERES_NO_SUITESPARSE) && \
defined(CERES_NO_CXSPARSE) && \
!defined(CERES_USE_EIGEN_SPARSE)
EXPECT_FALSE(options.IsValid(&message));
#else
EXPECT_TRUE(options.IsValid(&message));
#endif
options.linear_solver_type = ITERATIVE_SCHUR;
EXPECT_TRUE(options.IsValid(&message));
}
TEST(Solver, CantMixEvaluationCallbackWithInnerIterations) {
Solver::Options options;
NoOpEvaluationCallback evaluation_callback;
string message;
// Can't combine them.
options.use_inner_iterations = true;
options.evaluation_callback = &evaluation_callback;
EXPECT_FALSE(options.IsValid(&message));
// Either or none is OK.
options.use_inner_iterations = false;
options.evaluation_callback = &evaluation_callback;
EXPECT_TRUE(options.IsValid(&message));
options.use_inner_iterations = true;
options.evaluation_callback = NULL;
EXPECT_TRUE(options.IsValid(&message));
options.use_inner_iterations = false;
options.evaluation_callback = NULL;
EXPECT_TRUE(options.IsValid(&message));
}
template<int kNumResiduals, int N1 = 0, int N2 = 0, int N3 = 0>
class DummyCostFunction : public SizedCostFunction<kNumResiduals, N1, N2, N3> {
public:
bool Evaluate(double const* const* parameters,
double* residuals,
double** jacobians) const {
for (int i = 0; i < kNumResiduals; ++i) {
residuals[i] = kNumResiduals * kNumResiduals + i;
}
return true;
}
};
TEST(Solver, FixedCostForConstantProblem) {
double x = 1.0;
Problem problem;
problem.AddResidualBlock(new DummyCostFunction<2, 1>(), NULL, &x);
problem.SetParameterBlockConstant(&x);
const double expected_cost = 41.0 / 2.0; // 1/2 * ((4 + 0)^2 + (4 + 1)^2)
Solver::Options options;
Solver::Summary summary;
Solve(options, &problem, &summary);
EXPECT_TRUE(summary.IsSolutionUsable());
EXPECT_EQ(summary.fixed_cost, expected_cost);
EXPECT_EQ(summary.initial_cost, expected_cost);
EXPECT_EQ(summary.final_cost, expected_cost);
EXPECT_EQ(summary.iterations.size(), 0);
}
} // namespace internal
} // namespace ceres