Preprocessor for the LineSearchMinimizer. Change-Id: Ieb5dfe1c0b96ef323c1130edd0c3a8a8b2c644cc
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt index 5e1fe0f..227f091 100644 --- a/internal/ceres/CMakeLists.txt +++ b/internal/ceres/CMakeLists.txt
@@ -72,6 +72,7 @@ line_search.cc line_search_direction.cc line_search_minimizer.cc + line_search_preprocessor.cc linear_least_squares_problems.cc linear_operator.cc linear_solver.cc @@ -258,6 +259,7 @@ CERES_TEST(jet) CERES_TEST(levenberg_marquardt_strategy) CERES_TEST(dogleg_strategy) + CERES_TEST(line_search_preprocessor) CERES_TEST(local_parameterization) CERES_TEST(loss_function) CERES_TEST(minimizer)
diff --git a/internal/ceres/line_search_preprocessor.cc b/internal/ceres/line_search_preprocessor.cc new file mode 100644 index 0000000..bf17dee --- /dev/null +++ b/internal/ceres/line_search_preprocessor.cc
@@ -0,0 +1,106 @@ +// Ceres Solver - A fast non-linear least squares minimizer +// Copyright 2014 Google Inc. All rights reserved. +// http://code.google.com/p/ceres-solver/ +// +// 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/line_search_preprocessor.h" + +#include <numeric> +#include <string> +#include "ceres/evaluator.h" +#include "ceres/minimizer.h" +#include "ceres/problem_impl.h" +#include "ceres/program.h" +#include "ceres/wall_time.h" + +namespace ceres { +namespace internal { +namespace { + +bool IsProgramValid(const Program& program, string* error) { + if (program.IsBoundsConstrained()) { + *error = "LINE_SEARCH Minimizer does not support bounds."; + return false; + } + return program.ParameterBlocksAreFinite(error); +} + +bool SetupEvaluator(PreprocessedProblem* pp) { + pp->evaluator_options = Evaluator::Options(); + // This ensures that we get a Block Jacobian Evaluator without any + // requirement on orderings. + pp->evaluator_options.linear_solver_type = CGNR; + pp->evaluator_options.num_eliminate_blocks = 0; + pp->evaluator_options.num_threads = pp->options.num_threads; + pp->evaluator.reset(Evaluator::Create(pp->evaluator_options, + pp->reduced_program.get(), + &pp->error)); + return (pp->evaluator.get() != NULL); +} + +} // namespace + +LineSearchPreprocessor::~LineSearchPreprocessor() { +} + +bool LineSearchPreprocessor::Preprocess(const Solver::Options& options, + ProblemImpl* problem, + PreprocessedProblem* pp) { + CHECK_NOTNULL(pp); + pp->options = options; + ChangeNumThreadsIfNeeded(&pp->options); + + pp->problem = problem; + Program* program = problem->mutable_program(); + if (!IsProgramValid(*program, &pp->error)) { + return false; + } + + pp->reduced_program.reset( + program->CreateReducedProgram(&pp->removed_parameter_blocks, + &pp->fixed_cost, + &pp->error)); + + if (pp->reduced_program.get() == NULL) { + return false; + } + + if (pp->reduced_program->NumParameterBlocks() == 0) { + return true; + } + + if (!SetupEvaluator(pp)) { + return false; + } + + SetupCommonMinimizerOptions(pp); + return true; +} + +} // namespace internal +} // namespace ceres
diff --git a/internal/ceres/line_search_preprocessor.h b/internal/ceres/line_search_preprocessor.h new file mode 100644 index 0000000..54b968b --- /dev/null +++ b/internal/ceres/line_search_preprocessor.h
@@ -0,0 +1,50 @@ +// Ceres Solver - A fast non-linear least squares minimizer +// Copyright 2014 Google Inc. All rights reserved. +// http://code.google.com/p/ceres-solver/ +// +// 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: sameragarwal@google.com (Sameer Agarwal) + +#ifndef CERES_INTERNAL_LINE_SEARCH_PREPROCESSOR_H_ +#define CERES_INTERNAL_LINE_SEARCH_PREPROCESSOR_H_ + +#include "ceres/preprocessor.h" + +namespace ceres { +namespace internal { + +class LineSearchPreprocessor : public Preprocessor { + public: + virtual ~LineSearchPreprocessor(); + virtual bool Preprocess(const Solver::Options& options, + ProblemImpl* problem, + PreprocessedProblem* preprocessed_problem); +}; + +} // namespace internal +} // namespace ceres + +#endif // CERES_INTERNAL_LINE_SEARCH_PREPROCESSOR_H_
diff --git a/internal/ceres/line_search_preprocessor_test.cc b/internal/ceres/line_search_preprocessor_test.cc new file mode 100644 index 0000000..211ceef --- /dev/null +++ b/internal/ceres/line_search_preprocessor_test.cc
@@ -0,0 +1,136 @@ +// Ceres Solver - A fast non-linear least squares minimizer +// Copyright 2014 Google Inc. All rights reserved. +// http://code.google.com/p/ceres-solver/ +// +// 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 <map> + +#include "ceres/problem_impl.h" +#include "ceres/sized_cost_function.h" +#include "ceres/solver.h" +#include "ceres/line_search_preprocessor.h" +#include "gtest/gtest.h" + +namespace ceres { +namespace internal { + +TEST(LineSearchPreprocessor, ZeroProblem) { + ProblemImpl problem; + Solver::Options options; + options.minimizer_type = LINE_SEARCH; + LineSearchPreprocessor preprocessor; + PreprocessedProblem pp; + EXPECT_TRUE(preprocessor.Preprocess(options, &problem, &pp)); +} + +TEST(LineSearchPreprocessor, ProblemWithInvalidParameterBlock) { + ProblemImpl problem; + double x = 1.0/0.0; + problem.AddParameterBlock(&x, 1); + Solver::Options options; + options.minimizer_type = LINE_SEARCH; + LineSearchPreprocessor preprocessor; + PreprocessedProblem pp; + EXPECT_FALSE(preprocessor.Preprocess(options, &problem, &pp)); +} + +TEST(LineSearchPreprocessor, ParameterBlockHasBounds) { + ProblemImpl problem; + double x = 1.0; + problem.AddParameterBlock(&x, 1); + problem.SetParameterUpperBound(&x, 0, 1.0); + problem.SetParameterLowerBound(&x, 0, 2.0); + Solver::Options options; + options.minimizer_type = LINE_SEARCH; + LineSearchPreprocessor preprocessor; + PreprocessedProblem pp; + EXPECT_FALSE(preprocessor.Preprocess(options, &problem, &pp)); +} + +class FailingCostFunction : public SizedCostFunction<1, 1> { + public: + bool Evaluate(double const* const* parameters, + double* residuals, + double** jacobians) const { + return false; + } +}; + +TEST(LineSearchPreprocessor, RemoveParameterBlocksFailed) { + ProblemImpl problem; + double x = 3.0; + problem.AddResidualBlock(new FailingCostFunction, NULL, &x); + problem.SetParameterBlockConstant(&x); + Solver::Options options; + options.minimizer_type = LINE_SEARCH; + LineSearchPreprocessor preprocessor; + PreprocessedProblem pp; + EXPECT_FALSE(preprocessor.Preprocess(options, &problem, &pp)); +} + +TEST(LineSearchPreprocessor, RemoveParameterBlocksSucceeds) { + ProblemImpl problem; + double x = 3.0; + problem.AddParameterBlock(&x, 1); + Solver::Options options; + options.minimizer_type = LINE_SEARCH; + LineSearchPreprocessor preprocessor; + PreprocessedProblem pp; + EXPECT_TRUE(preprocessor.Preprocess(options, &problem, &pp)); +} + +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 { + return true; + } +}; + +TEST(LineSearchPreprocessor, NormalOperation) { + ProblemImpl problem; + double x = 1.0; + double y = 1.0; + double z = 1.0; + problem.AddResidualBlock(new DummyCostFunction<1, 1, 1>, NULL, &x, &y); + problem.AddResidualBlock(new DummyCostFunction<1, 1, 1>, NULL, &y, &z); + + Solver::Options options; + options.minimizer_type = LINE_SEARCH; + + LineSearchPreprocessor preprocessor; + PreprocessedProblem pp; + EXPECT_TRUE(preprocessor.Preprocess(options, &problem, &pp)); + EXPECT_EQ(pp.evaluator_options.linear_solver_type, CGNR); + EXPECT_TRUE(pp.evaluator.get() != NULL); +} + +} // namespace internal +} // namespace ceres
diff --git a/internal/ceres/preprocessor.cc b/internal/ceres/preprocessor.cc index a572d2b..318c5e2 100644 --- a/internal/ceres/preprocessor.cc +++ b/internal/ceres/preprocessor.cc
@@ -30,6 +30,7 @@ #include "ceres/callbacks.h" #include "ceres/gradient_checking_cost_function.h" +#include "ceres/line_search_preprocessor.h" #include "ceres/preprocessor.h" #include "ceres/problem_impl.h" #include "ceres/solver.h" @@ -43,8 +44,9 @@ return new TrustRegionPreprocessor; } - // TODO(sameeragarwal): Add the LineSearchPreprocessor when it is - // ready. + if (minimizer_type == LINE_SEARCH) { + return new LineSearchPreprocessor; + } LOG(FATAL) << "Unknown minimizer_type: " << minimizer_type; return NULL;