blob: f8ad2c91e776ac54ba08c2e9f29699a35803c181 [file] [log] [blame]
Austin Schuh70cc9552019-01-21 19:46:48 -08001// Ceres Solver - A fast non-linear least squares minimizer
2// Copyright 2015 Google Inc. All rights reserved.
3// http://ceres-solver.org/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are met:
7//
8// * Redistributions of source code must retain the above copyright notice,
9// this list of conditions and the following disclaimer.
10// * Redistributions in binary form must reproduce the above copyright notice,
11// this list of conditions and the following disclaimer in the documentation
12// and/or other materials provided with the distribution.
13// * Neither the name of Google Inc. nor the names of its contributors may be
14// used to endorse or promote products derived from this software without
15// specific prior written permission.
16//
17// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27// POSSIBILITY OF SUCH DAMAGE.
28//
29// Author: keir@google.com (Keir Mierle)
30// sameeragarwal@google.com (Sameer Agarwal)
31
32#include "ceres/solver.h"
33
34#include <algorithm>
35#include <memory>
36#include <sstream> // NOLINT
37#include <vector>
38
39#include "ceres/casts.h"
40#include "ceres/context.h"
41#include "ceres/context_impl.h"
42#include "ceres/detect_structure.h"
43#include "ceres/gradient_checking_cost_function.h"
44#include "ceres/internal/port.h"
45#include "ceres/parameter_block_ordering.h"
46#include "ceres/preprocessor.h"
47#include "ceres/problem.h"
48#include "ceres/problem_impl.h"
49#include "ceres/program.h"
50#include "ceres/schur_templates.h"
51#include "ceres/solver_utils.h"
52#include "ceres/stringprintf.h"
53#include "ceres/types.h"
54#include "ceres/wall_time.h"
55
56namespace ceres {
57namespace {
58
59using std::map;
60using std::string;
61using std::vector;
62using internal::StringAppendF;
63using internal::StringPrintf;
64
65#define OPTION_OP(x, y, OP) \
66 if (!(options.x OP y)) { \
67 std::stringstream ss; \
68 ss << "Invalid configuration. "; \
69 ss << string("Solver::Options::" #x " = ") << options.x << ". "; \
70 ss << "Violated constraint: "; \
71 ss << string("Solver::Options::" #x " " #OP " "#y); \
72 *error = ss.str(); \
73 return false; \
74 }
75
76#define OPTION_OP_OPTION(x, y, OP) \
77 if (!(options.x OP options.y)) { \
78 std::stringstream ss; \
79 ss << "Invalid configuration. "; \
80 ss << string("Solver::Options::" #x " = ") << options.x << ". "; \
81 ss << string("Solver::Options::" #y " = ") << options.y << ". "; \
82 ss << "Violated constraint: "; \
83 ss << string("Solver::Options::" #x); \
84 ss << string(#OP " Solver::Options::" #y "."); \
85 *error = ss.str(); \
86 return false; \
87 }
88
89#define OPTION_GE(x, y) OPTION_OP(x, y, >=);
90#define OPTION_GT(x, y) OPTION_OP(x, y, >);
91#define OPTION_LE(x, y) OPTION_OP(x, y, <=);
92#define OPTION_LT(x, y) OPTION_OP(x, y, <);
93#define OPTION_LE_OPTION(x, y) OPTION_OP_OPTION(x, y, <=)
94#define OPTION_LT_OPTION(x, y) OPTION_OP_OPTION(x, y, <)
95
96bool CommonOptionsAreValid(const Solver::Options& options, string* error) {
97 OPTION_GE(max_num_iterations, 0);
98 OPTION_GE(max_solver_time_in_seconds, 0.0);
99 OPTION_GE(function_tolerance, 0.0);
100 OPTION_GE(gradient_tolerance, 0.0);
101 OPTION_GE(parameter_tolerance, 0.0);
102 OPTION_GT(num_threads, 0);
103 if (options.check_gradients) {
104 OPTION_GT(gradient_check_relative_precision, 0.0);
105 OPTION_GT(gradient_check_numeric_derivative_relative_step_size, 0.0);
106 }
107 return true;
108}
109
110bool TrustRegionOptionsAreValid(const Solver::Options& options, string* error) {
111 OPTION_GT(initial_trust_region_radius, 0.0);
112 OPTION_GT(min_trust_region_radius, 0.0);
113 OPTION_GT(max_trust_region_radius, 0.0);
114 OPTION_LE_OPTION(min_trust_region_radius, max_trust_region_radius);
115 OPTION_LE_OPTION(min_trust_region_radius, initial_trust_region_radius);
116 OPTION_LE_OPTION(initial_trust_region_radius, max_trust_region_radius);
117 OPTION_GE(min_relative_decrease, 0.0);
118 OPTION_GE(min_lm_diagonal, 0.0);
119 OPTION_GE(max_lm_diagonal, 0.0);
120 OPTION_LE_OPTION(min_lm_diagonal, max_lm_diagonal);
121 OPTION_GE(max_num_consecutive_invalid_steps, 0);
122 OPTION_GT(eta, 0.0);
123 OPTION_GE(min_linear_solver_iterations, 0);
124 OPTION_GE(max_linear_solver_iterations, 1);
125 OPTION_LE_OPTION(min_linear_solver_iterations, max_linear_solver_iterations);
126
127 if (options.use_inner_iterations) {
128 OPTION_GE(inner_iteration_tolerance, 0.0);
129 }
130
131 if (options.use_inner_iterations &&
132 options.evaluation_callback != NULL) {
133 *error = "Inner iterations (use_inner_iterations = true) can't be "
134 "combined with an evaluation callback "
135 "(options.evaluation_callback != NULL).";
136 return false;
137 }
138
139 if (options.use_nonmonotonic_steps) {
140 OPTION_GT(max_consecutive_nonmonotonic_steps, 0);
141 }
142
143 if (options.linear_solver_type == ITERATIVE_SCHUR &&
144 options.use_explicit_schur_complement &&
145 options.preconditioner_type != SCHUR_JACOBI) {
146 *error = "use_explicit_schur_complement only supports "
147 "SCHUR_JACOBI as the preconditioner.";
148 return false;
149 }
150
151 if (options.dense_linear_algebra_library_type == LAPACK &&
152 !IsDenseLinearAlgebraLibraryTypeAvailable(LAPACK) &&
153 (options.linear_solver_type == DENSE_NORMAL_CHOLESKY ||
154 options.linear_solver_type == DENSE_QR ||
155 options.linear_solver_type == DENSE_SCHUR)) {
156 *error = StringPrintf(
157 "Can't use %s with "
158 "Solver::Options::dense_linear_algebra_library_type = LAPACK "
159 "because LAPACK was not enabled when Ceres was built.",
160 LinearSolverTypeToString(options.linear_solver_type));
161 return false;
162 }
163
164 if (options.sparse_linear_algebra_library_type == NO_SPARSE) {
165 const char* error_template =
166 "Can't use %s with "
167 "Solver::Options::sparse_linear_algebra_library_type = NO_SPARSE.";
168 const char* name = nullptr;
169
170 if (options.linear_solver_type == SPARSE_NORMAL_CHOLESKY ||
171 options.linear_solver_type == SPARSE_SCHUR) {
172 name = LinearSolverTypeToString(options.linear_solver_type);
173 } else if (options.linear_solver_type == ITERATIVE_SCHUR &&
174 (options.preconditioner_type == CLUSTER_JACOBI ||
175 options.preconditioner_type == CLUSTER_TRIDIAGONAL)) {
176 name = PreconditionerTypeToString(options.preconditioner_type);
177 }
178
179 if (name != nullptr) {
180 *error = StringPrintf(error_template, name);
181 return false;
182 }
183 } else if (!IsSparseLinearAlgebraLibraryTypeAvailable(
184 options.sparse_linear_algebra_library_type)) {
185 const char* error_template =
186 "Can't use %s with "
187 "Solver::Options::sparse_linear_algebra_library_type = %s, "
188 "because support was not enabled when Ceres Solver was built.";
189 const char* name = nullptr;
190 if (options.linear_solver_type == SPARSE_NORMAL_CHOLESKY ||
191 options.linear_solver_type == SPARSE_SCHUR) {
192 name = LinearSolverTypeToString(options.linear_solver_type);
193 } else if (options.linear_solver_type == ITERATIVE_SCHUR &&
194 (options.preconditioner_type == CLUSTER_JACOBI ||
195 options.preconditioner_type == CLUSTER_TRIDIAGONAL)) {
196 name = PreconditionerTypeToString(options.preconditioner_type);
197 }
198
199 if (name != nullptr) {
200 *error = StringPrintf(error_template,
201 name,
202 SparseLinearAlgebraLibraryTypeToString(
203 options.sparse_linear_algebra_library_type));
204 return false;
205 }
206 }
207
208 if (options.trust_region_strategy_type == DOGLEG) {
209 if (options.linear_solver_type == ITERATIVE_SCHUR ||
210 options.linear_solver_type == CGNR) {
211 *error = "DOGLEG only supports exact factorization based linear "
212 "solvers. If you want to use an iterative solver please "
213 "use LEVENBERG_MARQUARDT as the trust_region_strategy_type";
214 return false;
215 }
216 }
217
218 if (options.trust_region_minimizer_iterations_to_dump.size() > 0 &&
219 options.trust_region_problem_dump_format_type != CONSOLE &&
220 options.trust_region_problem_dump_directory.empty()) {
221 *error = "Solver::Options::trust_region_problem_dump_directory is empty.";
222 return false;
223 }
224
225 if (options.dynamic_sparsity &&
226 options.linear_solver_type != SPARSE_NORMAL_CHOLESKY) {
227 *error = "Dynamic sparsity is only supported with SPARSE_NORMAL_CHOLESKY.";
228 return false;
229 }
230
231 return true;
232}
233
234bool LineSearchOptionsAreValid(const Solver::Options& options, string* error) {
235 OPTION_GT(max_lbfgs_rank, 0);
236 OPTION_GT(min_line_search_step_size, 0.0);
237 OPTION_GT(max_line_search_step_contraction, 0.0);
238 OPTION_LT(max_line_search_step_contraction, 1.0);
239 OPTION_LT_OPTION(max_line_search_step_contraction,
240 min_line_search_step_contraction);
241 OPTION_LE(min_line_search_step_contraction, 1.0);
242 OPTION_GT(max_num_line_search_step_size_iterations, 0);
243 OPTION_GT(line_search_sufficient_function_decrease, 0.0);
244 OPTION_LT_OPTION(line_search_sufficient_function_decrease,
245 line_search_sufficient_curvature_decrease);
246 OPTION_LT(line_search_sufficient_curvature_decrease, 1.0);
247 OPTION_GT(max_line_search_step_expansion, 1.0);
248
249 if ((options.line_search_direction_type == ceres::BFGS ||
250 options.line_search_direction_type == ceres::LBFGS) &&
251 options.line_search_type != ceres::WOLFE) {
252 *error =
253 string("Invalid configuration: Solver::Options::line_search_type = ")
254 + string(LineSearchTypeToString(options.line_search_type))
255 + string(". When using (L)BFGS, "
256 "Solver::Options::line_search_type must be set to WOLFE.");
257 return false;
258 }
259
260 // Warn user if they have requested BISECTION interpolation, but constraints
261 // on max/min step size change during line search prevent bisection scaling
262 // from occurring. Warn only, as this is likely a user mistake, but one which
263 // does not prevent us from continuing.
264 LOG_IF(WARNING,
265 (options.line_search_interpolation_type == ceres::BISECTION &&
266 (options.max_line_search_step_contraction > 0.5 ||
267 options.min_line_search_step_contraction < 0.5)))
268 << "Line search interpolation type is BISECTION, but specified "
269 << "max_line_search_step_contraction: "
270 << options.max_line_search_step_contraction << ", and "
271 << "min_line_search_step_contraction: "
272 << options.min_line_search_step_contraction
273 << ", prevent bisection (0.5) scaling, continuing with solve regardless.";
274
275 return true;
276}
277
278#undef OPTION_OP
279#undef OPTION_OP_OPTION
280#undef OPTION_GT
281#undef OPTION_GE
282#undef OPTION_LE
283#undef OPTION_LT
284#undef OPTION_LE_OPTION
285#undef OPTION_LT_OPTION
286
287void StringifyOrdering(const vector<int>& ordering, string* report) {
288 if (ordering.size() == 0) {
289 internal::StringAppendF(report, "AUTOMATIC");
290 return;
291 }
292
293 for (int i = 0; i < ordering.size() - 1; ++i) {
294 internal::StringAppendF(report, "%d,", ordering[i]);
295 }
296 internal::StringAppendF(report, "%d", ordering.back());
297}
298
299void SummarizeGivenProgram(const internal::Program& program,
300 Solver::Summary* summary) {
301 summary->num_parameter_blocks = program.NumParameterBlocks();
302 summary->num_parameters = program.NumParameters();
303 summary->num_effective_parameters = program.NumEffectiveParameters();
304 summary->num_residual_blocks = program.NumResidualBlocks();
305 summary->num_residuals = program.NumResiduals();
306}
307
308void SummarizeReducedProgram(const internal::Program& program,
309 Solver::Summary* summary) {
310 summary->num_parameter_blocks_reduced = program.NumParameterBlocks();
311 summary->num_parameters_reduced = program.NumParameters();
312 summary->num_effective_parameters_reduced = program.NumEffectiveParameters();
313 summary->num_residual_blocks_reduced = program.NumResidualBlocks();
314 summary->num_residuals_reduced = program.NumResiduals();
315}
316
317void PreSolveSummarize(const Solver::Options& options,
318 const internal::ProblemImpl* problem,
319 Solver::Summary* summary) {
320 SummarizeGivenProgram(problem->program(), summary);
321 internal::OrderingToGroupSizes(options.linear_solver_ordering.get(),
322 &(summary->linear_solver_ordering_given));
323 internal::OrderingToGroupSizes(options.inner_iteration_ordering.get(),
324 &(summary->inner_iteration_ordering_given));
325
326 summary->dense_linear_algebra_library_type = options.dense_linear_algebra_library_type; // NOLINT
327 summary->dogleg_type = options.dogleg_type;
328 summary->inner_iteration_time_in_seconds = 0.0;
329 summary->num_line_search_steps = 0;
330 summary->line_search_cost_evaluation_time_in_seconds = 0.0;
331 summary->line_search_gradient_evaluation_time_in_seconds = 0.0;
332 summary->line_search_polynomial_minimization_time_in_seconds = 0.0;
333 summary->line_search_total_time_in_seconds = 0.0;
334 summary->inner_iterations_given = options.use_inner_iterations;
335 summary->line_search_direction_type = options.line_search_direction_type; // NOLINT
336 summary->line_search_interpolation_type = options.line_search_interpolation_type; // NOLINT
337 summary->line_search_type = options.line_search_type;
338 summary->linear_solver_type_given = options.linear_solver_type;
339 summary->max_lbfgs_rank = options.max_lbfgs_rank;
340 summary->minimizer_type = options.minimizer_type;
341 summary->nonlinear_conjugate_gradient_type = options.nonlinear_conjugate_gradient_type; // NOLINT
342 summary->num_threads_given = options.num_threads;
343 summary->preconditioner_type_given = options.preconditioner_type;
344 summary->sparse_linear_algebra_library_type = options.sparse_linear_algebra_library_type; // NOLINT
345 summary->trust_region_strategy_type = options.trust_region_strategy_type; // NOLINT
346 summary->visibility_clustering_type = options.visibility_clustering_type; // NOLINT
347}
348
349void PostSolveSummarize(const internal::PreprocessedProblem& pp,
350 Solver::Summary* summary) {
351 internal::OrderingToGroupSizes(pp.options.linear_solver_ordering.get(),
352 &(summary->linear_solver_ordering_used));
353 internal::OrderingToGroupSizes(pp.options.inner_iteration_ordering.get(),
354 &(summary->inner_iteration_ordering_used));
355
356 summary->inner_iterations_used = pp.inner_iteration_minimizer.get() != NULL; // NOLINT
357 summary->linear_solver_type_used = pp.linear_solver_options.type;
358 summary->num_threads_used = pp.options.num_threads;
359 summary->preconditioner_type_used = pp.options.preconditioner_type;
360
361 internal::SetSummaryFinalCost(summary);
362
363 if (pp.reduced_program.get() != NULL) {
364 SummarizeReducedProgram(*pp.reduced_program, summary);
365 }
366
367 using internal::CallStatistics;
368
369 // It is possible that no evaluator was created. This would be the
370 // case if the preprocessor failed, or if the reduced problem did
371 // not contain any parameter blocks. Thus, only extract the
372 // evaluator statistics if one exists.
373 if (pp.evaluator.get() != NULL) {
374 const map<string, CallStatistics>& evaluator_statistics =
375 pp.evaluator->Statistics();
376 {
377 const CallStatistics& call_stats = FindWithDefault(
378 evaluator_statistics, "Evaluator::Residual", CallStatistics());
379
380 summary->residual_evaluation_time_in_seconds = call_stats.time;
381 summary->num_residual_evaluations = call_stats.calls;
382 }
383 {
384 const CallStatistics& call_stats = FindWithDefault(
385 evaluator_statistics, "Evaluator::Jacobian", CallStatistics());
386
387 summary->jacobian_evaluation_time_in_seconds = call_stats.time;
388 summary->num_jacobian_evaluations = call_stats.calls;
389 }
390 }
391
392 // Again, like the evaluator, there may or may not be a linear
393 // solver from which we can extract run time statistics. In
394 // particular the line search solver does not use a linear solver.
395 if (pp.linear_solver.get() != NULL) {
396 const map<string, CallStatistics>& linear_solver_statistics =
397 pp.linear_solver->Statistics();
398 const CallStatistics& call_stats = FindWithDefault(
399 linear_solver_statistics, "LinearSolver::Solve", CallStatistics());
400 summary->num_linear_solves = call_stats.calls;
401 summary->linear_solver_time_in_seconds = call_stats.time;
402 }
403}
404
405void Minimize(internal::PreprocessedProblem* pp,
406 Solver::Summary* summary) {
407 using internal::Program;
408 using internal::Minimizer;
409
410 Program* program = pp->reduced_program.get();
411 if (pp->reduced_program->NumParameterBlocks() == 0) {
412 summary->message = "Function tolerance reached. "
413 "No non-constant parameter blocks found.";
414 summary->termination_type = CONVERGENCE;
415 VLOG_IF(1, pp->options.logging_type != SILENT) << summary->message;
416 summary->initial_cost = summary->fixed_cost;
417 summary->final_cost = summary->fixed_cost;
418 return;
419 }
420
421 const Vector original_reduced_parameters = pp->reduced_parameters;
422 std::unique_ptr<Minimizer> minimizer(
423 Minimizer::Create(pp->options.minimizer_type));
424 minimizer->Minimize(pp->minimizer_options,
425 pp->reduced_parameters.data(),
426 summary);
427
428 program->StateVectorToParameterBlocks(
429 summary->IsSolutionUsable()
430 ? pp->reduced_parameters.data()
431 : original_reduced_parameters.data());
432 program->CopyParameterBlockStateToUserState();
433}
434
435std::string SchurStructureToString(const int row_block_size,
436 const int e_block_size,
437 const int f_block_size) {
438 const std::string row =
439 (row_block_size == Eigen::Dynamic)
440 ? "d" : internal::StringPrintf("%d", row_block_size);
441
442 const std::string e =
443 (e_block_size == Eigen::Dynamic)
444 ? "d" : internal::StringPrintf("%d", e_block_size);
445
446 const std::string f =
447 (f_block_size == Eigen::Dynamic)
448 ? "d" : internal::StringPrintf("%d", f_block_size);
449
450 return internal::StringPrintf("%s,%s,%s", row.c_str(), e.c_str(), f.c_str());
451}
452
453} // namespace
454
455bool Solver::Options::IsValid(string* error) const {
456 if (!CommonOptionsAreValid(*this, error)) {
457 return false;
458 }
459
460 if (minimizer_type == TRUST_REGION &&
461 !TrustRegionOptionsAreValid(*this, error)) {
462 return false;
463 }
464
465 // We do not know if the problem is bounds constrained or not, if it
466 // is then the trust region solver will also use the line search
467 // solver to do a projection onto the box constraints, so make sure
468 // that the line search options are checked independent of what
469 // minimizer algorithm is being used.
470 return LineSearchOptionsAreValid(*this, error);
471}
472
473Solver::~Solver() {}
474
475void Solver::Solve(const Solver::Options& options,
476 Problem* problem,
477 Solver::Summary* summary) {
478 using internal::PreprocessedProblem;
479 using internal::Preprocessor;
480 using internal::ProblemImpl;
481 using internal::Program;
482 using internal::WallTimeInSeconds;
483
484 CHECK(problem != nullptr);
485 CHECK(summary != nullptr);
486
487 double start_time = WallTimeInSeconds();
488 *summary = Summary();
489 if (!options.IsValid(&summary->message)) {
490 LOG(ERROR) << "Terminating: " << summary->message;
491 return;
492 }
493
494 ProblemImpl* problem_impl = problem->problem_impl_.get();
495 Program* program = problem_impl->mutable_program();
496 PreSolveSummarize(options, problem_impl, summary);
497
498 // If gradient_checking is enabled, wrap all cost functions in a
499 // gradient checker and install a callback that terminates if any gradient
500 // error is detected.
501 std::unique_ptr<internal::ProblemImpl> gradient_checking_problem;
502 internal::GradientCheckingIterationCallback gradient_checking_callback;
503 Solver::Options modified_options = options;
504 if (options.check_gradients) {
505 modified_options.callbacks.push_back(&gradient_checking_callback);
506 gradient_checking_problem.reset(
507 CreateGradientCheckingProblemImpl(
508 problem_impl,
509 options.gradient_check_numeric_derivative_relative_step_size,
510 options.gradient_check_relative_precision,
511 &gradient_checking_callback));
512 problem_impl = gradient_checking_problem.get();
513 program = problem_impl->mutable_program();
514 }
515
516 // Make sure that all the parameter blocks states are set to the
517 // values provided by the user.
518 program->SetParameterBlockStatePtrsToUserStatePtrs();
519
520 // The main thread also does work so we only need to launch num_threads - 1.
521 problem_impl->context()->EnsureMinimumThreads(options.num_threads - 1);
522
523 std::unique_ptr<Preprocessor> preprocessor(
524 Preprocessor::Create(modified_options.minimizer_type));
525 PreprocessedProblem pp;
526
527 const bool status = preprocessor->Preprocess(modified_options, problem_impl, &pp);
528
529 // We check the linear_solver_options.type rather than
530 // modified_options.linear_solver_type because, depending on the
531 // lack of a Schur structure, the preprocessor may change the linear
532 // solver type.
533 if (IsSchurType(pp.linear_solver_options.type)) {
534 // TODO(sameeragarwal): We can likely eliminate the duplicate call
535 // to DetectStructure here and inside the linear solver, by
536 // calling this in the preprocessor.
537 int row_block_size;
538 int e_block_size;
539 int f_block_size;
540 DetectStructure(*static_cast<internal::BlockSparseMatrix*>(
541 pp.minimizer_options.jacobian.get())
542 ->block_structure(),
543 pp.linear_solver_options.elimination_groups[0],
544 &row_block_size,
545 &e_block_size,
546 &f_block_size);
547 summary->schur_structure_given =
548 SchurStructureToString(row_block_size, e_block_size, f_block_size);
549 internal::GetBestSchurTemplateSpecialization(&row_block_size,
550 &e_block_size,
551 &f_block_size);
552 summary->schur_structure_used =
553 SchurStructureToString(row_block_size, e_block_size, f_block_size);
554 }
555
556 summary->fixed_cost = pp.fixed_cost;
557 summary->preprocessor_time_in_seconds = WallTimeInSeconds() - start_time;
558
559 if (status) {
560 const double minimizer_start_time = WallTimeInSeconds();
561 Minimize(&pp, summary);
562 summary->minimizer_time_in_seconds =
563 WallTimeInSeconds() - minimizer_start_time;
564 } else {
565 summary->message = pp.error;
566 }
567
568 const double postprocessor_start_time = WallTimeInSeconds();
569 problem_impl = problem->problem_impl_.get();
570 program = problem_impl->mutable_program();
571 // On exit, ensure that the parameter blocks again point at the user
572 // provided values and the parameter blocks are numbered according
573 // to their position in the original user provided program.
574 program->SetParameterBlockStatePtrsToUserStatePtrs();
575 program->SetParameterOffsetsAndIndex();
576 PostSolveSummarize(pp, summary);
577 summary->postprocessor_time_in_seconds =
578 WallTimeInSeconds() - postprocessor_start_time;
579
580 // If the gradient checker reported an error, we want to report FAILURE
581 // instead of USER_FAILURE and provide the error log.
582 if (gradient_checking_callback.gradient_error_detected()) {
583 summary->termination_type = FAILURE;
584 summary->message = gradient_checking_callback.error_log();
585 }
586
587 summary->total_time_in_seconds = WallTimeInSeconds() - start_time;
588}
589
590void Solve(const Solver::Options& options,
591 Problem* problem,
592 Solver::Summary* summary) {
593 Solver solver;
594 solver.Solve(options, problem, summary);
595}
596
597string Solver::Summary::BriefReport() const {
598 return StringPrintf("Ceres Solver Report: "
599 "Iterations: %d, "
600 "Initial cost: %e, "
601 "Final cost: %e, "
602 "Termination: %s",
603 num_successful_steps + num_unsuccessful_steps,
604 initial_cost,
605 final_cost,
606 TerminationTypeToString(termination_type));
607}
608
609string Solver::Summary::FullReport() const {
610 using internal::VersionString;
611
612 string report = string("\nSolver Summary (v " + VersionString() + ")\n\n");
613
614 StringAppendF(&report, "%45s %21s\n", "Original", "Reduced");
615 StringAppendF(&report, "Parameter blocks % 25d% 25d\n",
616 num_parameter_blocks, num_parameter_blocks_reduced);
617 StringAppendF(&report, "Parameters % 25d% 25d\n",
618 num_parameters, num_parameters_reduced);
619 if (num_effective_parameters_reduced != num_parameters_reduced) {
620 StringAppendF(&report, "Effective parameters% 25d% 25d\n",
621 num_effective_parameters, num_effective_parameters_reduced);
622 }
623 StringAppendF(&report, "Residual blocks % 25d% 25d\n",
624 num_residual_blocks, num_residual_blocks_reduced);
625 StringAppendF(&report, "Residuals % 25d% 25d\n",
626 num_residuals, num_residuals_reduced);
627
628 if (minimizer_type == TRUST_REGION) {
629 // TRUST_SEARCH HEADER
630 StringAppendF(&report, "\nMinimizer %19s\n",
631 "TRUST_REGION");
632
633 if (linear_solver_type_used == DENSE_NORMAL_CHOLESKY ||
634 linear_solver_type_used == DENSE_SCHUR ||
635 linear_solver_type_used == DENSE_QR) {
636 StringAppendF(&report, "\nDense linear algebra library %15s\n",
637 DenseLinearAlgebraLibraryTypeToString(
638 dense_linear_algebra_library_type));
639 }
640
641 if (linear_solver_type_used == SPARSE_NORMAL_CHOLESKY ||
642 linear_solver_type_used == SPARSE_SCHUR ||
643 (linear_solver_type_used == ITERATIVE_SCHUR &&
644 (preconditioner_type_used == CLUSTER_JACOBI ||
645 preconditioner_type_used == CLUSTER_TRIDIAGONAL))) {
646 StringAppendF(&report, "\nSparse linear algebra library %15s\n",
647 SparseLinearAlgebraLibraryTypeToString(
648 sparse_linear_algebra_library_type));
649 }
650
651 StringAppendF(&report, "Trust region strategy %19s",
652 TrustRegionStrategyTypeToString(
653 trust_region_strategy_type));
654 if (trust_region_strategy_type == DOGLEG) {
655 if (dogleg_type == TRADITIONAL_DOGLEG) {
656 StringAppendF(&report, " (TRADITIONAL)");
657 } else {
658 StringAppendF(&report, " (SUBSPACE)");
659 }
660 }
661 StringAppendF(&report, "\n");
662 StringAppendF(&report, "\n");
663
664 StringAppendF(&report, "%45s %21s\n", "Given", "Used");
665 StringAppendF(&report, "Linear solver %25s%25s\n",
666 LinearSolverTypeToString(linear_solver_type_given),
667 LinearSolverTypeToString(linear_solver_type_used));
668
669 if (linear_solver_type_given == CGNR ||
670 linear_solver_type_given == ITERATIVE_SCHUR) {
671 StringAppendF(&report, "Preconditioner %25s%25s\n",
672 PreconditionerTypeToString(preconditioner_type_given),
673 PreconditionerTypeToString(preconditioner_type_used));
674 }
675
676 if (preconditioner_type_used == CLUSTER_JACOBI ||
677 preconditioner_type_used == CLUSTER_TRIDIAGONAL) {
678 StringAppendF(&report, "Visibility clustering%24s%25s\n",
679 VisibilityClusteringTypeToString(
680 visibility_clustering_type),
681 VisibilityClusteringTypeToString(
682 visibility_clustering_type));
683 }
684 StringAppendF(&report, "Threads % 25d% 25d\n",
685 num_threads_given, num_threads_used);
686
687 string given;
688 StringifyOrdering(linear_solver_ordering_given, &given);
689 string used;
690 StringifyOrdering(linear_solver_ordering_used, &used);
691 StringAppendF(&report,
692 "Linear solver ordering %22s %24s\n",
693 given.c_str(),
694 used.c_str());
695 if (IsSchurType(linear_solver_type_used)) {
696 StringAppendF(&report,
697 "Schur structure %22s %24s\n",
698 schur_structure_given.c_str(),
699 schur_structure_used.c_str());
700 }
701
702 if (inner_iterations_given) {
703 StringAppendF(&report,
704 "Use inner iterations %20s %20s\n",
705 inner_iterations_given ? "True" : "False",
706 inner_iterations_used ? "True" : "False");
707 }
708
709 if (inner_iterations_used) {
710 string given;
711 StringifyOrdering(inner_iteration_ordering_given, &given);
712 string used;
713 StringifyOrdering(inner_iteration_ordering_used, &used);
714 StringAppendF(&report,
715 "Inner iteration ordering %20s %24s\n",
716 given.c_str(),
717 used.c_str());
718 }
719 } else {
720 // LINE_SEARCH HEADER
721 StringAppendF(&report, "\nMinimizer %19s\n", "LINE_SEARCH");
722
723
724 string line_search_direction_string;
725 if (line_search_direction_type == LBFGS) {
726 line_search_direction_string = StringPrintf("LBFGS (%d)", max_lbfgs_rank);
727 } else if (line_search_direction_type == NONLINEAR_CONJUGATE_GRADIENT) {
728 line_search_direction_string =
729 NonlinearConjugateGradientTypeToString(
730 nonlinear_conjugate_gradient_type);
731 } else {
732 line_search_direction_string =
733 LineSearchDirectionTypeToString(line_search_direction_type);
734 }
735
736 StringAppendF(&report, "Line search direction %19s\n",
737 line_search_direction_string.c_str());
738
739 const string line_search_type_string =
740 StringPrintf("%s %s",
741 LineSearchInterpolationTypeToString(
742 line_search_interpolation_type),
743 LineSearchTypeToString(line_search_type));
744 StringAppendF(&report, "Line search type %19s\n",
745 line_search_type_string.c_str());
746 StringAppendF(&report, "\n");
747
748 StringAppendF(&report, "%45s %21s\n", "Given", "Used");
749 StringAppendF(&report, "Threads % 25d% 25d\n",
750 num_threads_given, num_threads_used);
751 }
752
753 StringAppendF(&report, "\nCost:\n");
754 StringAppendF(&report, "Initial % 30e\n", initial_cost);
755 if (termination_type != FAILURE &&
756 termination_type != USER_FAILURE) {
757 StringAppendF(&report, "Final % 30e\n", final_cost);
758 StringAppendF(&report, "Change % 30e\n",
759 initial_cost - final_cost);
760 }
761
762 StringAppendF(&report, "\nMinimizer iterations % 16d\n",
763 num_successful_steps + num_unsuccessful_steps);
764
765 // Successful/Unsuccessful steps only matter in the case of the
766 // trust region solver. Line search terminates when it encounters
767 // the first unsuccessful step.
768 if (minimizer_type == TRUST_REGION) {
769 StringAppendF(&report, "Successful steps % 14d\n",
770 num_successful_steps);
771 StringAppendF(&report, "Unsuccessful steps % 14d\n",
772 num_unsuccessful_steps);
773 }
774 if (inner_iterations_used) {
775 StringAppendF(&report, "Steps with inner iterations % 14d\n",
776 num_inner_iteration_steps);
777 }
778
779 const bool line_search_used =
780 (minimizer_type == LINE_SEARCH ||
781 (minimizer_type == TRUST_REGION && is_constrained));
782
783 if (line_search_used) {
784 StringAppendF(&report, "Line search steps % 14d\n",
785 num_line_search_steps);
786 }
787
788 StringAppendF(&report, "\nTime (in seconds):\n");
789 StringAppendF(&report, "Preprocessor %25.6f\n",
790 preprocessor_time_in_seconds);
791
792 StringAppendF(&report, "\n Residual only evaluation %18.6f (%d)\n",
793 residual_evaluation_time_in_seconds, num_residual_evaluations);
794 if (line_search_used) {
795 StringAppendF(&report, " Line search cost evaluation %10.6f\n",
796 line_search_cost_evaluation_time_in_seconds);
797 }
798 StringAppendF(&report, " Jacobian & residual evaluation %12.6f (%d)\n",
799 jacobian_evaluation_time_in_seconds, num_jacobian_evaluations);
800 if (line_search_used) {
801 StringAppendF(&report, " Line search gradient evaluation %6.6f\n",
802 line_search_gradient_evaluation_time_in_seconds);
803 }
804
805 if (minimizer_type == TRUST_REGION) {
806 StringAppendF(&report, " Linear solver %23.6f (%d)\n",
807 linear_solver_time_in_seconds, num_linear_solves);
808 }
809
810 if (inner_iterations_used) {
811 StringAppendF(&report, " Inner iterations %23.6f\n",
812 inner_iteration_time_in_seconds);
813 }
814
815 if (line_search_used) {
816 StringAppendF(&report, " Line search polynomial minimization %.6f\n",
817 line_search_polynomial_minimization_time_in_seconds);
818 }
819
820 StringAppendF(&report, "Minimizer %25.6f\n\n",
821 minimizer_time_in_seconds);
822
823 StringAppendF(&report, "Postprocessor %24.6f\n",
824 postprocessor_time_in_seconds);
825
826 StringAppendF(&report, "Total %25.6f\n\n",
827 total_time_in_seconds);
828
829 StringAppendF(&report, "Termination: %25s (%s)\n",
830 TerminationTypeToString(termination_type), message.c_str());
831 return report;
832}
833
834bool Solver::Summary::IsSolutionUsable() const {
835 return internal::IsSolutionUsable(*this);
836}
837
838} // namespace ceres