Refactor SolverImpl.
Replace SolverImpl with
a. A minimizer specific preprocessor class.
b. A generic Solve function inside solver.cc
c. Presummarize and Postsummarize functions to handle
updates to the summary object.
The existing SolverImpl class was a mixture of the above three
things and was increasingly complicated code to follow. This change,
breaks it into its three separate constituents, with the aims of
better separation of concerns and thus better testability and
reliability.
The call to Solver::Solve() now consists of
1. Presummarize - summarize the given state of the problem and solver
options.
2. Preprocess - Setup everything that is needed to call the minimizer.
This includes, removing redundant parameter and residual blocks,
setting up the reordering for the linear solver, creating the
linear solver, evaluator, inner iteration minimizer etc.
3. Minimize.
4. Post summarize - summarize the result of the preprocessing and the
solve.
Change-Id: I80f35cfc9f2cbf78f1df4aceace27075779d8a3a
diff --git a/docs/source/version_history.rst b/docs/source/version_history.rst
index a52ab30..8853fb7 100644
--- a/docs/source/version_history.rst
+++ b/docs/source/version_history.rst
@@ -17,16 +17,20 @@
---------------------------------
#. ``Solver::Options::solver_log`` has been removed. If needed this
- iteration callback can easily be implemented in user code.
+ iteration callback can easily be implemented in user code.
#. The ``SPARSE_CHOLESKY`` algorithm for covariance estimation has
- been removed. It is not rank revealing and numerically poorly
- behaved. Sparse QR factorization is a much better way to do this.
+ been removed. It is not rank revealing and numerically poorly
+ behaved. Sparse QR factorization is a much better way to do this.
#. The ``SPARSE_QR`` algorithm for covariance estimation has been
- renamed to ``SUITE_SPARSE_QR`` to be consistent with
- ``EIGEN_SPARSE_QR``.
+ renamed to ``SUITE_SPARSE_QR`` to be consistent with
+ ``EIGEN_SPARSE_QR``.
+# ``Solver::Summary::preconditioner_type`` has been replaced with
+ ``Solver::Summary::preconditioner_type_given`` and
+ ``Solver::Summary::preconditioner_type_used`` to be more consistent
+ with how information about the linear solver is communicated.
1.9.0
=====
diff --git a/include/ceres/solver.h b/include/ceres/solver.h
index fdc5457..ef391a7 100644
--- a/include/ceres/solver.h
+++ b/include/ceres/solver.h
@@ -910,9 +910,15 @@
// parameter blocks.
vector<int> inner_iteration_ordering_used;
- // Type of preconditioner used for solving the trust region
- // step. Only meaningful when an iterative linear solver is used.
- PreconditionerType preconditioner_type;
+ // Type of the preconditioner requested by the user.
+ PreconditionerType preconditioner_type_given;
+
+ // Type of the preconditioner actually used. This may be different
+ // from linear_solver_type_given if Ceres determines that the
+ // problem structure is not compatible with the linear solver
+ // requested or if the linear solver requested by the user is not
+ // available.
+ PreconditionerType preconditioner_type_used;
// Type of clustering algorithm used for visibility based
// preconditioning. Only meaningful when the preconditioner_type
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index 227f091..85b4906 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -85,10 +85,10 @@
partitioned_matrix_view.cc
polynomial.cc
preconditioner.cc
+ preprocessor.cc
problem.cc
problem_impl.cc
program.cc
- preprocessor.cc
reorder_program.cc
residual_block.cc
residual_block_utils.cc
@@ -98,13 +98,11 @@
scratch_evaluate_preparer.cc
single_linkage_clustering.cc
solver.cc
- solver_impl.cc
sparse_matrix.cc
sparse_normal_cholesky_solver.cc
split.cc
stringprintf.cc
suitesparse.cc
- summary_utils.cc
triplet_sparse_matrix.cc
trust_region_preprocessor.cc
trust_region_minimizer.cc
@@ -282,7 +280,6 @@
CERES_TEST(single_linkage_clustering)
CERES_TEST(small_blas)
CERES_TEST(solver)
- CERES_TEST(solver_impl)
# TODO(sameeragarwal): This test should ultimately be made
# independent of SuiteSparse.
diff --git a/internal/ceres/preprocessor.h b/internal/ceres/preprocessor.h
index 7a875b3..b4ca5b1 100644
--- a/internal/ceres/preprocessor.h
+++ b/internal/ceres/preprocessor.h
@@ -105,8 +105,7 @@
// Common functions used by various preprocessors.
// If OpenMP support is not available and user has requested more than
-// one threads, then set the *_num_threads options as needed to one
-// thread.
+// one thread, then set the *_num_threads options as needed to 1.
void ChangeNumThreadsIfNeeded(Solver::Options* options);
// Extract the effective parameter vector from the preprocessed
diff --git a/internal/ceres/solver.cc b/internal/ceres/solver.cc
index 3a57084..d49abef 100644
--- a/internal/ceres/solver.cc
+++ b/internal/ceres/solver.cc
@@ -29,16 +29,18 @@
// Author: keir@google.com (Keir Mierle)
// sameeragarwal@google.com (Sameer Agarwal)
-#include "ceres/internal/port.h"
#include "ceres/solver.h"
+#include <algorithm>
#include <sstream> // NOLINT
#include <vector>
-
+#include "ceres/internal/port.h"
+#include "ceres/parameter_block_ordering.h"
+#include "ceres/preprocessor.h"
+#include "ceres/gradient_checking_cost_function.h"
#include "ceres/problem.h"
#include "ceres/problem_impl.h"
#include "ceres/program.h"
-#include "ceres/solver_impl.h"
#include "ceres/stringprintf.h"
#include "ceres/types.h"
#include "ceres/version.h"
@@ -292,6 +294,136 @@
internal::StringAppendF(report, "%d", ordering.back());
}
+void SetSummaryFinalCost(Solver::Summary* summary) {
+ summary->final_cost = summary->initial_cost;
+ // We need the loop here, instead of just looking at the last
+ // iteration because the minimizer maybe making non-monotonic steps.
+ for (int i = 0; i < summary->iterations.size(); ++i) {
+ const IterationSummary& iteration_summary = summary->iterations[i];
+ summary->final_cost = min(iteration_summary.cost, summary->final_cost);
+ }
+}
+
+void SummarizeGivenProgram(const internal::Program& program,
+ Solver::Summary* summary) {
+ summary->num_parameter_blocks = program.NumParameterBlocks();
+ summary->num_parameters = program.NumParameters();
+ summary->num_effective_parameters = program.NumEffectiveParameters();
+ summary->num_residual_blocks = program.NumResidualBlocks();
+ summary->num_residuals = program.NumResiduals();
+}
+
+void SummarizeReducedProgram(const internal::Program& program,
+ Solver::Summary* summary) {
+ summary->num_parameter_blocks_reduced = program.NumParameterBlocks();
+ summary->num_parameters_reduced = program.NumParameters();
+ summary->num_effective_parameters_reduced = program.NumEffectiveParameters();
+ summary->num_residual_blocks_reduced = program.NumResidualBlocks();
+ summary->num_residuals_reduced = program.NumResiduals();
+}
+
+void PreSolveSummarize(const Solver::Options& options,
+ const internal::ProblemImpl* problem,
+ Solver::Summary* summary) {
+ SummarizeGivenProgram(problem->program(), summary);
+ internal::OrderingToGroupSizes(options.linear_solver_ordering.get(),
+ &(summary->linear_solver_ordering_given));
+ internal::OrderingToGroupSizes(options.inner_iteration_ordering.get(),
+ &(summary->inner_iteration_ordering_given));
+
+ summary->dense_linear_algebra_library_type = options.dense_linear_algebra_library_type;
+ summary->dogleg_type = options.dogleg_type;
+ summary->inner_iteration_time_in_seconds = 0.0;
+ summary->inner_iterations_given = options.use_inner_iterations;
+ summary->line_search_direction_type = options.line_search_direction_type;
+ summary->line_search_interpolation_type = options.line_search_interpolation_type;
+ summary->line_search_type = options.line_search_type;
+ summary->linear_solver_type_given = options.linear_solver_type;
+ summary->max_lbfgs_rank = options.max_lbfgs_rank;
+ summary->minimizer_type = options.minimizer_type;
+ summary->nonlinear_conjugate_gradient_type = options.nonlinear_conjugate_gradient_type;
+ summary->num_linear_solver_threads_given = options.num_linear_solver_threads;
+ summary->num_threads_given = options.num_threads;
+ summary->preconditioner_type_given = options.preconditioner_type;
+ summary->sparse_linear_algebra_library_type = options.sparse_linear_algebra_library_type;
+ summary->trust_region_strategy_type = options.trust_region_strategy_type;
+ summary->visibility_clustering_type = options.visibility_clustering_type;
+}
+
+void PostSolveSummarize(const internal::PreprocessedProblem& pp,
+ Solver::Summary* summary) {
+ internal::OrderingToGroupSizes(pp.options.linear_solver_ordering.get(),
+ &(summary->linear_solver_ordering_used));
+ internal::OrderingToGroupSizes(pp.options.inner_iteration_ordering.get(),
+ &(summary->inner_iteration_ordering_used));
+
+ summary->inner_iterations_used = pp.inner_iteration_minimizer.get() != NULL;
+ summary->linear_solver_type_used = pp.options.linear_solver_type;
+ summary->num_linear_solver_threads_used = pp.options.num_linear_solver_threads;
+ summary->num_threads_used = pp.options.num_threads;
+ summary->preconditioner_type_used = pp.options.preconditioner_type;
+
+ SetSummaryFinalCost(summary);
+
+ if (pp.reduced_program.get() != NULL) {
+ SummarizeReducedProgram(*pp.reduced_program, summary);
+ }
+
+ // It is possible that no evaluator was created. This would be the
+ // case if the preprocessor failed, or if the reduced problem did
+ // not contain any parameter blocks. Thus, only extract the
+ // evaluator statistics if one exists.
+ if (pp.evaluator.get() != NULL) {
+ const map<string, double>& evaluator_time_statistics =
+ pp.evaluator->TimeStatistics();
+ summary->residual_evaluation_time_in_seconds =
+ FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0);
+ summary->jacobian_evaluation_time_in_seconds =
+ FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0);
+ }
+
+ // Again, like the evaluator, there may or may not be a linear
+ // solver from which we can extract run time statistics. In
+ // particular the line search solver does not use a linear solver.
+ if (pp.linear_solver.get() != NULL) {
+ const map<string, double>& linear_solver_time_statistics =
+ pp.linear_solver->TimeStatistics();
+ summary->linear_solver_time_in_seconds =
+ FindWithDefault(linear_solver_time_statistics,
+ "LinearSolver::Solve",
+ 0.0);
+ }
+}
+
+void Minimize(internal::PreprocessedProblem* pp,
+ Solver::Summary* summary) {
+ using internal::Program;
+ using internal::scoped_ptr;
+ using internal::Minimizer;
+
+ Program* program = pp->reduced_program.get();
+ if (pp->reduced_program->NumParameterBlocks() == 0) {
+ summary->message = "Function tolerance reached. "
+ "No non-constant parameter blocks found.";
+ summary->termination_type = CONVERGENCE;
+ VLOG_IF(1, pp->options.logging_type != SILENT) << summary->message;
+ summary->initial_cost = summary->fixed_cost;
+ summary->final_cost = summary->fixed_cost;
+ return;
+ }
+
+ scoped_ptr<Minimizer> minimizer(
+ Minimizer::Create(pp->options.minimizer_type));
+ minimizer->Minimize(pp->minimizer_options,
+ pp->reduced_parameters.data(),
+ summary);
+
+ if (summary->IsSolutionUsable()) {
+ program->StateVectorToParameterBlocks(pp->reduced_parameters.data());
+ program->CopyParameterBlockStateToUserState();
+ }
+}
+
} // namespace
bool Solver::Options::IsValid(string* error) const {
@@ -312,20 +444,71 @@
void Solver::Solve(const Solver::Options& options,
Problem* problem,
Solver::Summary* summary) {
- double start_time_seconds = internal::WallTimeInSeconds();
+ using internal::PreprocessedProblem;
+ using internal::Preprocessor;
+ using internal::ProblemImpl;
+ using internal::Program;
+ using internal::scoped_ptr;
+ using internal::WallTimeInSeconds;
+
CHECK_NOTNULL(problem);
CHECK_NOTNULL(summary);
+ double start_time = WallTimeInSeconds();
*summary = Summary();
if (!options.IsValid(&summary->message)) {
LOG(ERROR) << "Terminating: " << summary->message;
return;
}
- internal::ProblemImpl* problem_impl = problem->problem_impl_.get();
- internal::SolverImpl::Solve(options, problem_impl, summary);
- summary->total_time_in_seconds =
- internal::WallTimeInSeconds() - start_time_seconds;
+ ProblemImpl* problem_impl = problem->problem_impl_.get();
+ Program* program = problem_impl->mutable_program();
+ PreSolveSummarize(options, problem_impl, summary);
+
+ // Make sure that all the parameter blocks states are set to the
+ // values provided by the user.
+ program->SetParameterBlockStatePtrsToUserStatePtrs();
+
+ scoped_ptr<internal::ProblemImpl> gradient_checking_problem;
+ if (options.check_gradients) {
+ gradient_checking_problem.reset(
+ CreateGradientCheckingProblemImpl(
+ problem_impl,
+ options.numeric_derivative_relative_step_size,
+ options.gradient_check_relative_precision));
+ problem_impl = gradient_checking_problem.get();
+ program = problem_impl->mutable_program();
+ }
+
+ scoped_ptr<Preprocessor> preprocessor(
+ Preprocessor::Create(options.minimizer_type));
+ PreprocessedProblem pp;
+ const bool status = preprocessor->Preprocess(options, problem_impl, &pp);
+ summary->fixed_cost = pp.fixed_cost;
+ summary->preprocessor_time_in_seconds = WallTimeInSeconds() - start_time;
+
+ if (status) {
+ const double minimizer_start_time = WallTimeInSeconds();
+ Minimize(&pp, summary);
+ summary->minimizer_time_in_seconds =
+ WallTimeInSeconds() - minimizer_start_time;
+ } else {
+ summary->message = pp.error;
+ }
+
+ const double postprocessor_start_time = WallTimeInSeconds();
+ problem_impl = problem->problem_impl_.get();
+ program = problem_impl->mutable_program();
+ // On exit, ensure that the parameter blocks again point at the user
+ // provided values and the parameter blocks are numbered according
+ // to their position in the original user provided program.
+ program->SetParameterBlockStatePtrsToUserStatePtrs();
+ program->SetParameterOffsetsAndIndex();
+ PostSolveSummarize(pp, summary);
+ summary->postprocessor_time_in_seconds =
+ WallTimeInSeconds() - postprocessor_start_time;
+
+ summary->total_time_in_seconds = WallTimeInSeconds() - start_time;
}
void Solve(const Solver::Options& options,
@@ -373,7 +556,8 @@
linear_solver_type_used(SPARSE_NORMAL_CHOLESKY),
inner_iterations_given(false),
inner_iterations_used(false),
- preconditioner_type(IDENTITY),
+ preconditioner_type_given(IDENTITY),
+ preconditioner_type_used(IDENTITY),
visibility_clustering_type(CANONICAL_VIEWS),
trust_region_strategy_type(LEVENBERG_MARQUARDT),
dense_linear_algebra_library_type(EIGEN),
@@ -436,8 +620,8 @@
if (linear_solver_type_used == SPARSE_NORMAL_CHOLESKY ||
linear_solver_type_used == SPARSE_SCHUR ||
(linear_solver_type_used == ITERATIVE_SCHUR &&
- (preconditioner_type == CLUSTER_JACOBI ||
- preconditioner_type == CLUSTER_TRIDIAGONAL))) {
+ (preconditioner_type_used == CLUSTER_JACOBI ||
+ preconditioner_type_used == CLUSTER_TRIDIAGONAL))) {
StringAppendF(&report, "\nSparse linear algebra library %15s\n",
SparseLinearAlgebraLibraryTypeToString(
sparse_linear_algebra_library_type));
@@ -464,12 +648,12 @@
if (linear_solver_type_given == CGNR ||
linear_solver_type_given == ITERATIVE_SCHUR) {
StringAppendF(&report, "Preconditioner %25s%25s\n",
- PreconditionerTypeToString(preconditioner_type),
- PreconditionerTypeToString(preconditioner_type));
+ PreconditionerTypeToString(preconditioner_type_given),
+ PreconditionerTypeToString(preconditioner_type_used));
}
- if (preconditioner_type == CLUSTER_JACOBI ||
- preconditioner_type == CLUSTER_TRIDIAGONAL) {
+ if (preconditioner_type_used == CLUSTER_JACOBI ||
+ preconditioner_type_used == CLUSTER_TRIDIAGONAL) {
StringAppendF(&report, "Visibility clustering%24s%25s\n",
VisibilityClusteringTypeToString(
visibility_clustering_type),
diff --git a/internal/ceres/solver_impl.cc b/internal/ceres/solver_impl.cc
deleted file mode 100644
index 67bccda..0000000
--- a/internal/ceres/solver_impl.cc
+++ /dev/null
@@ -1,944 +0,0 @@
-// 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: keir@google.com (Keir Mierle)
-
-#include "ceres/solver_impl.h"
-
-#include <cstdio>
-#include <iostream> // NOLINT
-#include <numeric>
-#include <string>
-#include "ceres/array_utils.h"
-#include "ceres/callbacks.h"
-#include "ceres/coordinate_descent_minimizer.h"
-#include "ceres/cxsparse.h"
-#include "ceres/evaluator.h"
-#include "ceres/gradient_checking_cost_function.h"
-#include "ceres/iteration_callback.h"
-#include "ceres/levenberg_marquardt_strategy.h"
-#include "ceres/line_search_minimizer.h"
-#include "ceres/linear_solver.h"
-#include "ceres/map_util.h"
-#include "ceres/minimizer.h"
-#include "ceres/ordered_groups.h"
-#include "ceres/parameter_block.h"
-#include "ceres/parameter_block_ordering.h"
-#include "ceres/preconditioner.h"
-#include "ceres/problem.h"
-#include "ceres/problem_impl.h"
-#include "ceres/program.h"
-#include "ceres/reorder_program.h"
-#include "ceres/residual_block.h"
-#include "ceres/stringprintf.h"
-#include "ceres/suitesparse.h"
-#include "ceres/summary_utils.h"
-#include "ceres/trust_region_minimizer.h"
-#include "ceres/wall_time.h"
-
-namespace ceres {
-namespace internal {
-
-void SolverImpl::TrustRegionMinimize(
- const Solver::Options& options,
- Program* program,
- shared_ptr<CoordinateDescentMinimizer> inner_iteration_minimizer,
- shared_ptr<Evaluator> evaluator,
- LinearSolver* linear_solver,
- Solver::Summary* summary) {
- Minimizer::Options minimizer_options(options);
- minimizer_options.is_constrained = program->IsBoundsConstrained();
-
- // The optimizer works on contiguous parameter vectors; allocate
- // some.
- Vector parameters(program->NumParameters());
-
- // Collect the discontiguous parameters into a contiguous state
- // vector.
- program->ParameterBlocksToStateVector(parameters.data());
-
- LoggingCallback logging_callback(TRUST_REGION,
- options.minimizer_progress_to_stdout);
- if (options.logging_type != SILENT) {
- minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(),
- &logging_callback);
- }
-
- StateUpdatingCallback updating_callback(program, parameters.data());
- if (options.update_state_every_iteration) {
- // This must get pushed to the front of the callbacks so that it is run
- // before any of the user callbacks.
- minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(),
- &updating_callback);
- }
-
- minimizer_options.evaluator = evaluator;
- minimizer_options.jacobian.reset(evaluator->CreateJacobian());
- minimizer_options.inner_iteration_minimizer = inner_iteration_minimizer;
-
- TrustRegionStrategy::Options trust_region_strategy_options;
- trust_region_strategy_options.linear_solver = linear_solver;
- trust_region_strategy_options.initial_radius =
- options.initial_trust_region_radius;
- trust_region_strategy_options.max_radius = options.max_trust_region_radius;
- trust_region_strategy_options.min_lm_diagonal = options.min_lm_diagonal;
- trust_region_strategy_options.max_lm_diagonal = options.max_lm_diagonal;
- trust_region_strategy_options.trust_region_strategy_type =
- options.trust_region_strategy_type;
- trust_region_strategy_options.dogleg_type = options.dogleg_type;
- minimizer_options.trust_region_strategy.reset(
- TrustRegionStrategy::Create(trust_region_strategy_options));
-
- TrustRegionMinimizer minimizer;
- double minimizer_start_time = WallTimeInSeconds();
- minimizer.Minimize(minimizer_options, parameters.data(), summary);
-
- // If the user aborted mid-optimization or the optimization
- // terminated because of a numerical failure, then do not update
- // user state.
- if (summary->termination_type != USER_FAILURE &&
- summary->termination_type != FAILURE) {
- program->StateVectorToParameterBlocks(parameters.data());
- program->CopyParameterBlockStateToUserState();
- }
-
- summary->minimizer_time_in_seconds =
- WallTimeInSeconds() - minimizer_start_time;
-}
-
-void SolverImpl::LineSearchMinimize(
- const Solver::Options& options,
- Program* program,
- shared_ptr<Evaluator> evaluator,
- Solver::Summary* summary) {
- Minimizer::Options minimizer_options(options);
-
- // The optimizer works on contiguous parameter vectors; allocate some.
- Vector parameters(program->NumParameters());
-
- // Collect the discontiguous parameters into a contiguous state vector.
- program->ParameterBlocksToStateVector(parameters.data());
-
- LoggingCallback logging_callback(LINE_SEARCH,
- options.minimizer_progress_to_stdout);
- if (options.logging_type != SILENT) {
- minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(),
- &logging_callback);
- }
-
- StateUpdatingCallback updating_callback(program, parameters.data());
- if (options.update_state_every_iteration) {
- // This must get pushed to the front of the callbacks so that it is run
- // before any of the user callbacks.
- minimizer_options.callbacks.insert(minimizer_options.callbacks.begin(),
- &updating_callback);
- }
-
- minimizer_options.evaluator = evaluator;
-
- LineSearchMinimizer minimizer;
- double minimizer_start_time = WallTimeInSeconds();
- minimizer.Minimize(minimizer_options, parameters.data(), summary);
-
- // If the user aborted mid-optimization or the optimization
- // terminated because of a numerical failure, then do not update
- // user state.
- if (summary->termination_type != USER_FAILURE &&
- summary->termination_type != FAILURE) {
- program->StateVectorToParameterBlocks(parameters.data());
- program->CopyParameterBlockStateToUserState();
- }
-
- summary->minimizer_time_in_seconds =
- WallTimeInSeconds() - minimizer_start_time;
-}
-
-void SolverImpl::Solve(const Solver::Options& options,
- ProblemImpl* problem_impl,
- Solver::Summary* summary) {
- VLOG(2) << "Initial problem: "
- << problem_impl->NumParameterBlocks()
- << " parameter blocks, "
- << problem_impl->NumParameters()
- << " parameters, "
- << problem_impl->NumResidualBlocks()
- << " residual blocks, "
- << problem_impl->NumResiduals()
- << " residuals.";
- if (options.minimizer_type == TRUST_REGION) {
- TrustRegionSolve(options, problem_impl, summary);
- } else {
- LineSearchSolve(options, problem_impl, summary);
- }
-}
-
-void SolverImpl::TrustRegionSolve(const Solver::Options& original_options,
- ProblemImpl* original_problem_impl,
- Solver::Summary* summary) {
- EventLogger event_logger("TrustRegionSolve");
- double solver_start_time = WallTimeInSeconds();
-
- Program* original_program = original_problem_impl->mutable_program();
- ProblemImpl* problem_impl = original_problem_impl;
-
- summary->minimizer_type = TRUST_REGION;
-
- SummarizeGivenProgram(*original_program, summary);
- OrderingToGroupSizes(original_options.linear_solver_ordering.get(),
- &(summary->linear_solver_ordering_given));
- OrderingToGroupSizes(original_options.inner_iteration_ordering.get(),
- &(summary->inner_iteration_ordering_given));
-
- Solver::Options options(original_options);
-
-#ifndef CERES_USE_OPENMP
- if (options.num_threads > 1) {
- LOG(WARNING)
- << "OpenMP support is not compiled into this binary; "
- << "only options.num_threads=1 is supported. Switching "
- << "to single threaded mode.";
- options.num_threads = 1;
- }
- if (options.num_linear_solver_threads > 1) {
- LOG(WARNING)
- << "OpenMP support is not compiled into this binary; "
- << "only options.num_linear_solver_threads=1 is supported. Switching "
- << "to single threaded mode.";
- options.num_linear_solver_threads = 1;
- }
-#endif
-
- summary->num_threads_given = original_options.num_threads;
- summary->num_threads_used = options.num_threads;
-
- if (options.trust_region_minimizer_iterations_to_dump.size() > 0 &&
- options.trust_region_problem_dump_format_type != CONSOLE &&
- options.trust_region_problem_dump_directory.empty()) {
- summary->message =
- "Solver::Options::trust_region_problem_dump_directory is empty.";
- LOG(ERROR) << summary->message;
- return;
- }
-
- if (!original_program->ParameterBlocksAreFinite(&summary->message)) {
- LOG(ERROR) << "Terminating: " << summary->message;
- return;
- }
-
- if (!original_program->IsFeasible(&summary->message)) {
- LOG(ERROR) << "Terminating: " << summary->message;
- return;
- }
-
- event_logger.AddEvent("Init");
-
- original_program->SetParameterBlockStatePtrsToUserStatePtrs();
- event_logger.AddEvent("SetParameterBlockPtrs");
-
- // If the user requests gradient checking, construct a new
- // ProblemImpl by wrapping the CostFunctions of problem_impl inside
- // GradientCheckingCostFunction and replacing problem_impl with
- // gradient_checking_problem_impl.
- scoped_ptr<ProblemImpl> gradient_checking_problem_impl;
- if (options.check_gradients) {
- VLOG(1) << "Checking Gradients";
- gradient_checking_problem_impl.reset(
- CreateGradientCheckingProblemImpl(
- problem_impl,
- options.numeric_derivative_relative_step_size,
- options.gradient_check_relative_precision));
-
- // From here on, problem_impl will point to the gradient checking
- // version.
- problem_impl = gradient_checking_problem_impl.get();
- }
-
- if (options.linear_solver_ordering.get() != NULL) {
- if (!IsOrderingValid(options, problem_impl, &summary->message)) {
- LOG(ERROR) << summary->message;
- return;
- }
- event_logger.AddEvent("CheckOrdering");
- } else {
- options.linear_solver_ordering.reset(new ParameterBlockOrdering);
- const ProblemImpl::ParameterMap& parameter_map =
- problem_impl->parameter_map();
- for (ProblemImpl::ParameterMap::const_iterator it = parameter_map.begin();
- it != parameter_map.end();
- ++it) {
- options.linear_solver_ordering->AddElementToGroup(it->first, 0);
- }
- event_logger.AddEvent("ConstructOrdering");
- }
-
- // Create the three objects needed to minimize: the transformed program, the
- // evaluator, and the linear solver.
- scoped_ptr<Program> reduced_program(CreateReducedProgram(&options,
- problem_impl,
- &summary->fixed_cost,
- &summary->message));
-
- event_logger.AddEvent("CreateReducedProgram");
- if (reduced_program == NULL) {
- return;
- }
-
- OrderingToGroupSizes(options.linear_solver_ordering.get(),
- &(summary->linear_solver_ordering_used));
- SummarizeReducedProgram(*reduced_program, summary);
-
- if (summary->num_parameter_blocks_reduced == 0) {
- summary->preprocessor_time_in_seconds =
- WallTimeInSeconds() - solver_start_time;
-
- double post_process_start_time = WallTimeInSeconds();
-
- summary->message =
- "Function tolerance reached. "
- "No non-constant parameter blocks found.";
- summary->termination_type = CONVERGENCE;
- VLOG_IF(1, options.logging_type != SILENT) << summary->message;
-
- summary->initial_cost = summary->fixed_cost;
- summary->final_cost = summary->fixed_cost;
-
- // Ensure the program state is set to the user parameters on the way out.
- original_program->SetParameterBlockStatePtrsToUserStatePtrs();
- original_program->SetParameterOffsetsAndIndex();
-
- summary->postprocessor_time_in_seconds =
- WallTimeInSeconds() - post_process_start_time;
- return;
- }
-
- scoped_ptr<LinearSolver>
- linear_solver(CreateLinearSolver(&options, &summary->message));
- event_logger.AddEvent("CreateLinearSolver");
- if (linear_solver == NULL) {
- return;
- }
-
- summary->linear_solver_type_given = original_options.linear_solver_type;
- summary->linear_solver_type_used = options.linear_solver_type;
-
- summary->preconditioner_type = options.preconditioner_type;
- summary->visibility_clustering_type = options.visibility_clustering_type;
-
- summary->num_linear_solver_threads_given =
- original_options.num_linear_solver_threads;
- summary->num_linear_solver_threads_used = options.num_linear_solver_threads;
-
- summary->dense_linear_algebra_library_type =
- options.dense_linear_algebra_library_type;
- summary->sparse_linear_algebra_library_type =
- options.sparse_linear_algebra_library_type;
-
- summary->trust_region_strategy_type = options.trust_region_strategy_type;
- summary->dogleg_type = options.dogleg_type;
-
- shared_ptr<Evaluator> evaluator(CreateEvaluator(options,
- problem_impl->parameter_map(),
- reduced_program.get(),
- &summary->message));
-
- event_logger.AddEvent("CreateEvaluator");
-
- if (evaluator.get() == NULL) {
- return;
- }
-
- shared_ptr<CoordinateDescentMinimizer> inner_iteration_minimizer;
- if (options.use_inner_iterations) {
- if (reduced_program->parameter_blocks().size() < 2) {
- LOG(WARNING) << "Reduced problem only contains one parameter block."
- << "Disabling inner iterations.";
- } else {
- inner_iteration_minimizer.reset(
- CreateInnerIterationMinimizer(options,
- *reduced_program,
- problem_impl->parameter_map(),
- summary));
- if (inner_iteration_minimizer.get() == NULL) {
- LOG(ERROR) << summary->message;
- return;
- }
- }
- }
- event_logger.AddEvent("CreateInnerIterationMinimizer");
-
- double minimizer_start_time = WallTimeInSeconds();
- summary->preprocessor_time_in_seconds =
- minimizer_start_time - solver_start_time;
-
- // Run the optimization.
- TrustRegionMinimize(options,
- reduced_program.get(),
- inner_iteration_minimizer,
- evaluator,
- linear_solver.get(),
- summary);
- event_logger.AddEvent("Minimize");
-
- double post_process_start_time = WallTimeInSeconds();
-
- SetSummaryFinalCost(summary);
-
- // Ensure the program state is set to the user parameters on the way
- // out.
- original_program->SetParameterBlockStatePtrsToUserStatePtrs();
- original_program->SetParameterOffsetsAndIndex();
-
- const map<string, double>& linear_solver_time_statistics =
- linear_solver->TimeStatistics();
- summary->linear_solver_time_in_seconds =
- FindWithDefault(linear_solver_time_statistics,
- "LinearSolver::Solve",
- 0.0);
-
- const map<string, double>& evaluator_time_statistics =
- evaluator->TimeStatistics();
-
- summary->residual_evaluation_time_in_seconds =
- FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0);
- summary->jacobian_evaluation_time_in_seconds =
- FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0);
-
- // Stick a fork in it, we're done.
- summary->postprocessor_time_in_seconds =
- WallTimeInSeconds() - post_process_start_time;
- event_logger.AddEvent("PostProcess");
-}
-
-void SolverImpl::LineSearchSolve(const Solver::Options& original_options,
- ProblemImpl* original_problem_impl,
- Solver::Summary* summary) {
- double solver_start_time = WallTimeInSeconds();
-
- Program* original_program = original_problem_impl->mutable_program();
- ProblemImpl* problem_impl = original_problem_impl;
-
- SummarizeGivenProgram(*original_program, summary);
- summary->minimizer_type = LINE_SEARCH;
- summary->line_search_direction_type =
- original_options.line_search_direction_type;
- summary->max_lbfgs_rank = original_options.max_lbfgs_rank;
- summary->line_search_type = original_options.line_search_type;
- summary->line_search_interpolation_type =
- original_options.line_search_interpolation_type;
- summary->nonlinear_conjugate_gradient_type =
- original_options.nonlinear_conjugate_gradient_type;
-
- if (original_program->IsBoundsConstrained()) {
- summary->message = "LINE_SEARCH Minimizer does not support bounds.";
- LOG(ERROR) << "Terminating: " << summary->message;
- return;
- }
-
- Solver::Options options(original_options);
-
- // This ensures that we get a Block Jacobian Evaluator along with
- // none of the Schur nonsense. This file will have to be extensively
- // refactored to deal with the various bits of cleanups related to
- // line search.
- options.linear_solver_type = CGNR;
-
-
-#ifndef CERES_USE_OPENMP
- if (options.num_threads > 1) {
- LOG(WARNING)
- << "OpenMP support is not compiled into this binary; "
- << "only options.num_threads=1 is supported. Switching "
- << "to single threaded mode.";
- options.num_threads = 1;
- }
-#endif // CERES_USE_OPENMP
-
- summary->num_threads_given = original_options.num_threads;
- summary->num_threads_used = options.num_threads;
-
- if (!original_program->ParameterBlocksAreFinite(&summary->message)) {
- LOG(ERROR) << "Terminating: " << summary->message;
- return;
- }
-
- if (options.linear_solver_ordering.get() != NULL) {
- if (!IsOrderingValid(options, problem_impl, &summary->message)) {
- LOG(ERROR) << summary->message;
- return;
- }
- } else {
- options.linear_solver_ordering.reset(new ParameterBlockOrdering);
- const ProblemImpl::ParameterMap& parameter_map =
- problem_impl->parameter_map();
- for (ProblemImpl::ParameterMap::const_iterator it = parameter_map.begin();
- it != parameter_map.end();
- ++it) {
- options.linear_solver_ordering->AddElementToGroup(it->first, 0);
- }
- }
-
-
- original_program->SetParameterBlockStatePtrsToUserStatePtrs();
-
- // If the user requests gradient checking, construct a new
- // ProblemImpl by wrapping the CostFunctions of problem_impl inside
- // GradientCheckingCostFunction and replacing problem_impl with
- // gradient_checking_problem_impl.
- scoped_ptr<ProblemImpl> gradient_checking_problem_impl;
- if (options.check_gradients) {
- VLOG(1) << "Checking Gradients";
- gradient_checking_problem_impl.reset(
- CreateGradientCheckingProblemImpl(
- problem_impl,
- options.numeric_derivative_relative_step_size,
- options.gradient_check_relative_precision));
-
- // From here on, problem_impl will point to the gradient checking
- // version.
- problem_impl = gradient_checking_problem_impl.get();
- }
-
- // Create the three objects needed to minimize: the transformed program, the
- // evaluator, and the linear solver.
- scoped_ptr<Program> reduced_program(CreateReducedProgram(&options,
- problem_impl,
- &summary->fixed_cost,
- &summary->message));
- if (reduced_program == NULL) {
- return;
- }
-
- SummarizeReducedProgram(*reduced_program, summary);
- if (summary->num_parameter_blocks_reduced == 0) {
- summary->preprocessor_time_in_seconds =
- WallTimeInSeconds() - solver_start_time;
-
- summary->message =
- "Function tolerance reached. "
- "No non-constant parameter blocks found.";
- summary->termination_type = CONVERGENCE;
- VLOG_IF(1, options.logging_type != SILENT) << summary->message;
- summary->initial_cost = summary->fixed_cost;
- summary->final_cost = summary->fixed_cost;
-
- const double post_process_start_time = WallTimeInSeconds();
- SetSummaryFinalCost(summary);
-
- // Ensure the program state is set to the user parameters on the way out.
- original_program->SetParameterBlockStatePtrsToUserStatePtrs();
- original_program->SetParameterOffsetsAndIndex();
-
- summary->postprocessor_time_in_seconds =
- WallTimeInSeconds() - post_process_start_time;
- return;
- }
-
- shared_ptr<Evaluator> evaluator(CreateEvaluator(options,
- problem_impl->parameter_map(),
- reduced_program.get(),
- &summary->message));
- if (evaluator.get() == NULL) {
- return;
- }
-
- const double minimizer_start_time = WallTimeInSeconds();
- summary->preprocessor_time_in_seconds =
- minimizer_start_time - solver_start_time;
-
- // Run the optimization.
- LineSearchMinimize(options, reduced_program.get(), evaluator, summary);
-
- const double post_process_start_time = WallTimeInSeconds();
-
- SetSummaryFinalCost(summary);
-
- // Ensure the program state is set to the user parameters on the way out.
- original_program->SetParameterBlockStatePtrsToUserStatePtrs();
- original_program->SetParameterOffsetsAndIndex();
-
- const map<string, double>& evaluator_time_statistics =
- evaluator->TimeStatistics();
-
- summary->residual_evaluation_time_in_seconds =
- FindWithDefault(evaluator_time_statistics, "Evaluator::Residual", 0.0);
- summary->jacobian_evaluation_time_in_seconds =
- FindWithDefault(evaluator_time_statistics, "Evaluator::Jacobian", 0.0);
-
- // Stick a fork in it, we're done.
- summary->postprocessor_time_in_seconds =
- WallTimeInSeconds() - post_process_start_time;
-}
-
-bool SolverImpl::IsOrderingValid(const Solver::Options& options,
- const ProblemImpl* problem_impl,
- string* error) {
- if (options.linear_solver_ordering->NumElements() !=
- problem_impl->NumParameterBlocks()) {
- *error = "Number of parameter blocks in user supplied ordering "
- "does not match the number of parameter blocks in the problem";
- return false;
- }
-
- const Program& program = problem_impl->program();
- const vector<ParameterBlock*>& parameter_blocks = program.parameter_blocks();
- for (vector<ParameterBlock*>::const_iterator it = parameter_blocks.begin();
- it != parameter_blocks.end();
- ++it) {
- if (!options.linear_solver_ordering
- ->IsMember(const_cast<double*>((*it)->user_state()))) {
- *error = "Problem contains a parameter block that is not in "
- "the user specified ordering.";
- return false;
- }
- }
-
- if (IsSchurType(options.linear_solver_type) &&
- options.linear_solver_ordering->NumGroups() > 1) {
- const vector<ResidualBlock*>& residual_blocks = program.residual_blocks();
- const set<double*>& e_blocks =
- options.linear_solver_ordering->group_to_elements().begin()->second;
- if (!IsParameterBlockSetIndependent(e_blocks, residual_blocks)) {
- *error = "The user requested the use of a Schur type solver. "
- "But the first elimination group in the ordering is not an "
- "independent set.";
- return false;
- }
- }
- return true;
-}
-
-bool SolverImpl::IsParameterBlockSetIndependent(
- const set<double*>& parameter_block_ptrs,
- const vector<ResidualBlock*>& residual_blocks) {
- // Loop over each residual block and ensure that no two parameter
- // blocks in the same residual block are part of
- // parameter_block_ptrs as that would violate the assumption that it
- // is an independent set in the Hessian matrix.
- for (vector<ResidualBlock*>::const_iterator it = residual_blocks.begin();
- it != residual_blocks.end();
- ++it) {
- ParameterBlock* const* parameter_blocks = (*it)->parameter_blocks();
- const int num_parameter_blocks = (*it)->NumParameterBlocks();
- int count = 0;
- for (int i = 0; i < num_parameter_blocks; ++i) {
- count += parameter_block_ptrs.count(
- parameter_blocks[i]->mutable_user_state());
- }
- if (count > 1) {
- return false;
- }
- }
- return true;
-}
-
-Program* SolverImpl::CreateReducedProgram(Solver::Options* options,
- ProblemImpl* problem_impl,
- double* fixed_cost,
- string* error) {
- CHECK_NOTNULL(options->linear_solver_ordering.get());
- Program* original_program = problem_impl->mutable_program();
-
- vector<double*> removed_parameter_blocks;
- scoped_ptr<Program> reduced_program(
- original_program->CreateReducedProgram(&removed_parameter_blocks,
- fixed_cost,
- error));
- if (reduced_program.get() == NULL) {
- return NULL;
- }
-
- VLOG(2) << "Reduced problem: "
- << reduced_program->NumParameterBlocks()
- << " parameter blocks, "
- << reduced_program->NumParameters()
- << " parameters, "
- << reduced_program->NumResidualBlocks()
- << " residual blocks, "
- << reduced_program->NumResiduals()
- << " residuals.";
-
- if (reduced_program->NumParameterBlocks() == 0) {
- LOG(WARNING) << "No varying parameter blocks to optimize; "
- << "bailing early.";
- return reduced_program.release();
- }
-
- ParameterBlockOrdering* linear_solver_ordering =
- options->linear_solver_ordering.get();
- const int min_group_id =
- linear_solver_ordering->MinNonZeroGroup();
- linear_solver_ordering->Remove(removed_parameter_blocks);
-
- ParameterBlockOrdering* inner_iteration_ordering =
- options->inner_iteration_ordering.get();
- if (inner_iteration_ordering != NULL) {
- inner_iteration_ordering->Remove(removed_parameter_blocks);
- }
-
- if (IsSchurType(options->linear_solver_type) &&
- linear_solver_ordering->GroupSize(min_group_id) == 0) {
- // If the user requested the use of a Schur type solver, and
- // supplied a non-NULL linear_solver_ordering object with more than
- // one elimination group, then it can happen that after all the
- // parameter blocks which are fixed or unused have been removed from
- // the program and the ordering, there are no more parameter blocks
- // in the first elimination group.
- //
- // In such a case, the use of a Schur type solver is not possible,
- // as they assume there is at least one e_block. Thus, we
- // automatically switch to the closest solver to the one indicated
- // by the user.
- if (options->linear_solver_type == ITERATIVE_SCHUR) {
- options->preconditioner_type =
- Preconditioner::PreconditionerForZeroEBlocks(
- options->preconditioner_type);
- }
-
- options->linear_solver_type =
- LinearSolver::LinearSolverForZeroEBlocks(
- options->linear_solver_type);
- }
-
- if (IsSchurType(options->linear_solver_type)) {
- if (!ReorderProgramForSchurTypeLinearSolver(
- options->linear_solver_type,
- options->sparse_linear_algebra_library_type,
- problem_impl->parameter_map(),
- linear_solver_ordering,
- reduced_program.get(),
- error)) {
- return NULL;
- }
- return reduced_program.release();
- }
-
- if (options->linear_solver_type == SPARSE_NORMAL_CHOLESKY &&
- !options->dynamic_sparsity) {
- if (!ReorderProgramForSparseNormalCholesky(
- options->sparse_linear_algebra_library_type,
- *linear_solver_ordering,
- reduced_program.get(),
- error)) {
- return NULL;
- }
-
- return reduced_program.release();
- }
-
- reduced_program->SetParameterOffsetsAndIndex();
- return reduced_program.release();
-}
-
-LinearSolver* SolverImpl::CreateLinearSolver(Solver::Options* options,
- string* error) {
- CHECK_NOTNULL(options);
- CHECK_NOTNULL(options->linear_solver_ordering.get());
- CHECK_NOTNULL(error);
-
- if (options->trust_region_strategy_type == DOGLEG) {
- if (options->linear_solver_type == ITERATIVE_SCHUR ||
- options->linear_solver_type == CGNR) {
- *error = "DOGLEG only supports exact factorization based linear "
- "solvers. If you want to use an iterative solver please "
- "use LEVENBERG_MARQUARDT as the trust_region_strategy_type";
- return NULL;
- }
- }
-
-#ifdef CERES_NO_LAPACK
- if (options->linear_solver_type == DENSE_NORMAL_CHOLESKY &&
- options->dense_linear_algebra_library_type == LAPACK) {
- *error = "Can't use DENSE_NORMAL_CHOLESKY with LAPACK because "
- "LAPACK was not enabled when Ceres was built.";
- return NULL;
- }
-
- if (options->linear_solver_type == DENSE_QR &&
- options->dense_linear_algebra_library_type == LAPACK) {
- *error = "Can't use DENSE_QR with LAPACK because "
- "LAPACK was not enabled when Ceres was built.";
- return NULL;
- }
-
- if (options->linear_solver_type == DENSE_SCHUR &&
- options->dense_linear_algebra_library_type == LAPACK) {
- *error = "Can't use DENSE_SCHUR with LAPACK because "
- "LAPACK was not enabled when Ceres was built.";
- return NULL;
- }
-#endif
-
-#ifdef CERES_NO_SUITESPARSE
- if (options->linear_solver_type == SPARSE_NORMAL_CHOLESKY &&
- options->sparse_linear_algebra_library_type == SUITE_SPARSE) {
- *error = "Can't use SPARSE_NORMAL_CHOLESKY with SUITESPARSE because "
- "SuiteSparse was not enabled when Ceres was built.";
- return NULL;
- }
-
- if (options->preconditioner_type == CLUSTER_JACOBI) {
- *error = "CLUSTER_JACOBI preconditioner not suppored. Please build Ceres "
- "with SuiteSparse support.";
- return NULL;
- }
-
- if (options->preconditioner_type == CLUSTER_TRIDIAGONAL) {
- *error = "CLUSTER_TRIDIAGONAL preconditioner not suppored. Please build "
- "Ceres with SuiteSparse support.";
- return NULL;
- }
-#endif
-
-#ifdef CERES_NO_CXSPARSE
- if (options->linear_solver_type == SPARSE_NORMAL_CHOLESKY &&
- options->sparse_linear_algebra_library_type == CX_SPARSE) {
- *error = "Can't use SPARSE_NORMAL_CHOLESKY with CXSPARSE because "
- "CXSparse was not enabled when Ceres was built.";
- return NULL;
- }
-#endif
-
- if (options->max_linear_solver_iterations <= 0) {
- *error = "Solver::Options::max_linear_solver_iterations is not positive.";
- return NULL;
- }
- if (options->min_linear_solver_iterations <= 0) {
- *error = "Solver::Options::min_linear_solver_iterations is not positive.";
- return NULL;
- }
- if (options->min_linear_solver_iterations >
- options->max_linear_solver_iterations) {
- *error = "Solver::Options::min_linear_solver_iterations > "
- "Solver::Options::max_linear_solver_iterations.";
- return NULL;
- }
-
- LinearSolver::Options linear_solver_options;
- linear_solver_options.min_num_iterations =
- options->min_linear_solver_iterations;
- linear_solver_options.max_num_iterations =
- options->max_linear_solver_iterations;
- linear_solver_options.type = options->linear_solver_type;
- linear_solver_options.preconditioner_type = options->preconditioner_type;
- linear_solver_options.visibility_clustering_type =
- options->visibility_clustering_type;
- linear_solver_options.sparse_linear_algebra_library_type =
- options->sparse_linear_algebra_library_type;
- linear_solver_options.dense_linear_algebra_library_type =
- options->dense_linear_algebra_library_type;
- linear_solver_options.use_postordering = options->use_postordering;
- linear_solver_options.dynamic_sparsity = options->dynamic_sparsity;
-
- // Ignore user's postordering preferences and force it to be true if
- // cholmod_camd is not available. This ensures that the linear
- // solver does not assume that a fill-reducing pre-ordering has been
- // done.
-#if !defined(CERES_NO_SUITESPARSE) && defined(CERES_NO_CAMD)
- if (IsSchurType(linear_solver_options.type) &&
- options->sparse_linear_algebra_library_type == SUITE_SPARSE) {
- linear_solver_options.use_postordering = true;
- }
-#endif
-
- linear_solver_options.num_threads = options->num_linear_solver_threads;
- options->num_linear_solver_threads = linear_solver_options.num_threads;
-
- OrderingToGroupSizes(options->linear_solver_ordering.get(),
- &linear_solver_options.elimination_groups);
- // Schur type solvers, expect at least two elimination groups. If
- // there is only one elimination group, then CreateReducedProgram
- // guarantees that this group only contains e_blocks. Thus we add a
- // dummy elimination group with zero blocks in it.
- if (IsSchurType(linear_solver_options.type) &&
- linear_solver_options.elimination_groups.size() == 1) {
- linear_solver_options.elimination_groups.push_back(0);
- }
-
- return LinearSolver::Create(linear_solver_options);
-}
-
-Evaluator* SolverImpl::CreateEvaluator(
- const Solver::Options& options,
- const ProblemImpl::ParameterMap& parameter_map,
- Program* program,
- string* error) {
- Evaluator::Options evaluator_options;
- evaluator_options.linear_solver_type = options.linear_solver_type;
- evaluator_options.num_eliminate_blocks =
- (options.linear_solver_ordering->NumGroups() > 0 &&
- IsSchurType(options.linear_solver_type))
- ? (options.linear_solver_ordering
- ->group_to_elements().begin()
- ->second.size())
- : 0;
- evaluator_options.num_threads = options.num_threads;
- evaluator_options.dynamic_sparsity = options.dynamic_sparsity;
- return Evaluator::Create(evaluator_options, program, error);
-}
-
-CoordinateDescentMinimizer* SolverImpl::CreateInnerIterationMinimizer(
- const Solver::Options& options,
- const Program& program,
- const ProblemImpl::ParameterMap& parameter_map,
- Solver::Summary* summary) {
- summary->inner_iterations_given = true;
-
- scoped_ptr<CoordinateDescentMinimizer> inner_iteration_minimizer(
- new CoordinateDescentMinimizer);
- scoped_ptr<ParameterBlockOrdering> inner_iteration_ordering;
- ParameterBlockOrdering* ordering_ptr = NULL;
-
- if (options.inner_iteration_ordering.get() == NULL) {
- inner_iteration_ordering.reset(
- CoordinateDescentMinimizer::CreateOrdering(program));
- ordering_ptr = inner_iteration_ordering.get();
- } else {
- ordering_ptr = options.inner_iteration_ordering.get();
- if (!CoordinateDescentMinimizer::IsOrderingValid(program,
- *ordering_ptr,
- &summary->message)) {
- return NULL;
- }
- }
-
- if (!inner_iteration_minimizer->Init(program,
- parameter_map,
- *ordering_ptr,
- &summary->message)) {
- return NULL;
- }
-
- summary->inner_iterations_used = true;
- summary->inner_iteration_time_in_seconds = 0.0;
- OrderingToGroupSizes(ordering_ptr,
- &(summary->inner_iteration_ordering_used));
- return inner_iteration_minimizer.release();
-}
-
-} // namespace internal
-} // namespace ceres
diff --git a/internal/ceres/solver_impl.h b/internal/ceres/solver_impl.h
deleted file mode 100644
index 5cefdb1..0000000
--- a/internal/ceres/solver_impl.h
+++ /dev/null
@@ -1,127 +0,0 @@
-// Ceres Solver - A fast non-linear least squares minimizer
-// Copyright 2010, 2011, 2012 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: keir@google.com (Keir Mierle)
-
-#ifndef CERES_INTERNAL_SOLVER_IMPL_H_
-#define CERES_INTERNAL_SOLVER_IMPL_H_
-
-#include <set>
-#include <string>
-#include <vector>
-#include "ceres/internal/port.h"
-#include "ceres/ordered_groups.h"
-#include "ceres/problem_impl.h"
-#include "ceres/solver.h"
-
-namespace ceres {
-namespace internal {
-
-class CoordinateDescentMinimizer;
-class Evaluator;
-class LinearSolver;
-class Program;
-class TripletSparseMatrix;
-
-class SolverImpl {
- public:
- // Mirrors the interface in solver.h, but exposes implementation
- // details for testing internally.
- static void Solve(const Solver::Options& options,
- ProblemImpl* problem_impl,
- Solver::Summary* summary);
-
- static void TrustRegionSolve(const Solver::Options& options,
- ProblemImpl* problem_impl,
- Solver::Summary* summary);
-
- // Run the TrustRegionMinimizer for the given evaluator and configuration.
- static void TrustRegionMinimize(
- const Solver::Options &options,
- Program* program,
- shared_ptr<CoordinateDescentMinimizer> inner_iteration_minimizer,
- shared_ptr<Evaluator> evaluator,
- LinearSolver* linear_solver,
- Solver::Summary* summary);
-
- static void LineSearchSolve(const Solver::Options& options,
- ProblemImpl* problem_impl,
- Solver::Summary* summary);
-
- // Run the LineSearchMinimizer for the given evaluator and configuration.
- static void LineSearchMinimize(const Solver::Options &options,
- Program* program,
- shared_ptr<Evaluator> evaluator,
- Solver::Summary* summary);
-
- // Create the transformed Program, which has all the fixed blocks
- // and residuals eliminated, and in the case of automatic schur
- // ordering, has the E blocks first in the resulting program, with
- // options.num_eliminate_blocks set appropriately.
- //
- // If fixed_cost is not NULL, the residual blocks that are removed
- // are evaluated and the sum of their cost is returned in fixed_cost.
- static Program* CreateReducedProgram(Solver::Options* options,
- ProblemImpl* problem_impl,
- double* fixed_cost,
- string* message);
-
- // Create the appropriate linear solver, taking into account any
- // config changes decided by CreateTransformedProgram(). The
- // selected linear solver, which may be different from what the user
- // selected; consider the case that the remaining elimininated
- // blocks is zero after removing fixed blocks.
- static LinearSolver* CreateLinearSolver(Solver::Options* options,
- string* message);
-
- // Create the appropriate evaluator for the transformed program.
- static Evaluator* CreateEvaluator(
- const Solver::Options& options,
- const ProblemImpl::ParameterMap& parameter_map,
- Program* program,
- string* message);
-
- static bool IsOrderingValid(const Solver::Options& options,
- const ProblemImpl* problem_impl,
- string* message);
-
- static bool IsParameterBlockSetIndependent(
- const set<double*>& parameter_block_ptrs,
- const vector<ResidualBlock*>& residual_blocks);
-
- static CoordinateDescentMinimizer* CreateInnerIterationMinimizer(
- const Solver::Options& options,
- const Program& program,
- const ProblemImpl::ParameterMap& parameter_map,
- Solver::Summary* summary);
-};
-
-} // namespace internal
-} // namespace ceres
-
-#endif // CERES_INTERNAL_SOLVER_IMPL_H_
diff --git a/internal/ceres/solver_impl_test.cc b/internal/ceres/solver_impl_test.cc
deleted file mode 100644
index 2d517c6..0000000
--- a/internal/ceres/solver_impl_test.cc
+++ /dev/null
@@ -1,107 +0,0 @@
-// 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 "gtest/gtest.h"
-#include "ceres/autodiff_cost_function.h"
-#include "ceres/linear_solver.h"
-#include "ceres/ordered_groups.h"
-#include "ceres/parameter_block.h"
-#include "ceres/problem_impl.h"
-#include "ceres/program.h"
-#include "ceres/residual_block.h"
-#include "ceres/solver_impl.h"
-#include "ceres/sized_cost_function.h"
-
-namespace ceres {
-namespace internal {
-
-// 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;
- }
-};
-
-TEST(SolverImpl, ConstantParameterBlocksDoNotChangeAndStateInvariantKept) {
- double x = 50.0;
- double y = 50.0;
- double z = 50.0;
- double w = 50.0;
- const double original_x = 50.0;
- const double original_y = 50.0;
- const double original_z = 50.0;
- const double original_w = 50.0;
-
- scoped_ptr<CostFunction> cost_function(
- new AutoDiffCostFunction<Quadratic4DCostFunction, 1, 1, 1, 1, 1>(
- new Quadratic4DCostFunction));
-
- Problem::Options problem_options;
- problem_options.cost_function_ownership = DO_NOT_TAKE_OWNERSHIP;
-
- ProblemImpl problem(problem_options);
- problem.AddResidualBlock(cost_function.get(), NULL, &x, &y, &z, &w);
- problem.SetParameterBlockConstant(&x);
- problem.SetParameterBlockConstant(&w);
-
- Solver::Options options;
- options.linear_solver_type = DENSE_QR;
-
- Solver::Summary summary;
- SolverImpl::Solve(options, &problem, &summary);
-
- // Verify only the non-constant parameters were mutated.
- EXPECT_EQ(original_x, x);
- EXPECT_NE(original_y, y);
- EXPECT_NE(original_z, z);
- EXPECT_EQ(original_w, w);
-
- // Check that the parameter block state pointers are pointing back at the
- // user state, instead of inside a random temporary vector made by Solve().
- EXPECT_EQ(&x, problem.program().parameter_blocks()[0]->state());
- EXPECT_EQ(&y, problem.program().parameter_blocks()[1]->state());
- EXPECT_EQ(&z, problem.program().parameter_blocks()[2]->state());
- EXPECT_EQ(&w, problem.program().parameter_blocks()[3]->state());
-
- EXPECT_TRUE(problem.program().IsValid());
-}
-
-} // namespace internal
-} // namespace ceres
diff --git a/internal/ceres/solver_test.cc b/internal/ceres/solver_test.cc
index 2a136f7..f2ead06 100644
--- a/internal/ceres/solver_test.cc
+++ b/internal/ceres/solver_test.cc
@@ -294,5 +294,35 @@
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
diff --git a/internal/ceres/summary_utils.cc b/internal/ceres/summary_utils.cc
deleted file mode 100644
index 243030c..0000000
--- a/internal/ceres/summary_utils.cc
+++ /dev/null
@@ -1,66 +0,0 @@
-// 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 <algorithm>
-#include "ceres/summary_utils.h"
-#include "ceres/program.h"
-#include "ceres/solver.h"
-
-namespace ceres {
-namespace internal {
-
-void SetSummaryFinalCost(Solver::Summary* summary) {
- summary->final_cost = summary->initial_cost;
- // We need the loop here, instead of just looking at the last
- // iteration because the minimizer maybe making non-monotonic steps.
- for (int i = 0; i < summary->iterations.size(); ++i) {
- const IterationSummary& iteration_summary = summary->iterations[i];
- summary->final_cost = min(iteration_summary.cost, summary->final_cost);
- }
-}
-
-void SummarizeGivenProgram(const Program& program, Solver::Summary* summary) {
- summary->num_parameter_blocks = program.NumParameterBlocks();
- summary->num_parameters = program.NumParameters();
- summary->num_effective_parameters = program.NumEffectiveParameters();
- summary->num_residual_blocks = program.NumResidualBlocks();
- summary->num_residuals = program.NumResiduals();
-}
-
-void SummarizeReducedProgram(const Program& program, Solver::Summary* summary) {
- summary->num_parameter_blocks_reduced = program.NumParameterBlocks();
- summary->num_parameters_reduced = program.NumParameters();
- summary->num_effective_parameters_reduced = program.NumEffectiveParameters();
- summary->num_residual_blocks_reduced = program.NumResidualBlocks();
- summary->num_residuals_reduced = program.NumResiduals();
-}
-
-} // namespace internal
-} // namespace ceres
diff --git a/internal/ceres/summary_utils.h b/internal/ceres/summary_utils.h
deleted file mode 100644
index 9b07987..0000000
--- a/internal/ceres/summary_utils.h
+++ /dev/null
@@ -1,49 +0,0 @@
-// 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)
-
-#ifndef CERES_INTERNAL_SUMMARY_UTILS_H_
-#define CERES_INTERNAL_SUMMARY_UTILS_H_
-
-#include <vector>
-#include "ceres/solver.h"
-
-namespace ceres {
-namespace internal {
-
-class Program;
-
-void SummarizeGivenProgram(const Program& program, Solver::Summary* summary);
-void SummarizeReducedProgram(const Program& program, Solver::Summary* summary);
-void SetSummaryFinalCost(Solver::Summary* summary);
-
-} // namespace internal
-} // namespace ceres
-
-#endif // CERES_INTERNAL_SUMMARY_UTILS_H_
diff --git a/jni/Android.mk b/jni/Android.mk
index 70680f5..496956c 100644
--- a/jni/Android.mk
+++ b/jni/Android.mk
@@ -145,6 +145,7 @@
$(CERES_SRC_PATH)/line_search_minimizer.cc \
$(CERES_SRC_PATH)/linear_least_squares_problems.cc \
$(CERES_SRC_PATH)/linear_operator.cc \
+ $(CERES_SRC_PATH)/line_search_preprocessor.cc \
$(CERES_SRC_PATH)/linear_solver.cc \
$(CERES_SRC_PATH)/local_parameterization.cc \
$(CERES_SRC_PATH)/loss_function.cc \
@@ -155,6 +156,7 @@
$(CERES_SRC_PATH)/partitioned_matrix_view.cc \
$(CERES_SRC_PATH)/polynomial.cc \
$(CERES_SRC_PATH)/preconditioner.cc \
+ $(CERES_SRC_PATH)/preprocessor.cc \
$(CERES_SRC_PATH)/problem.cc \
$(CERES_SRC_PATH)/problem_impl.cc \
$(CERES_SRC_PATH)/program.cc \
@@ -166,15 +168,14 @@
$(CERES_SRC_PATH)/schur_jacobi_preconditioner.cc \
$(CERES_SRC_PATH)/scratch_evaluate_preparer.cc \
$(CERES_SRC_PATH)/solver.cc \
- $(CERES_SRC_PATH)/solver_impl.cc \
$(CERES_SRC_PATH)/sparse_matrix.cc \
$(CERES_SRC_PATH)/sparse_normal_cholesky_solver.cc \
$(CERES_SRC_PATH)/split.cc \
$(CERES_SRC_PATH)/stringprintf.cc \
- $(CERES_SRC_PATH)/summary_utils.cc \
$(CERES_SRC_PATH)/suitesparse.cc \
$(CERES_SRC_PATH)/triplet_sparse_matrix.cc \
$(CERES_SRC_PATH)/trust_region_minimizer.cc \
+ $(CERES_SRC_PATH)/trust_region_preprocessor.cc \
$(CERES_SRC_PATH)/trust_region_strategy.cc \
$(CERES_SRC_PATH)/types.cc \
$(CERES_SRC_PATH)/visibility_based_preconditioner.cc \
