diff options
Diffstat (limited to 'internal/ceres/line_search_minimizer.cc')
| -rw-r--r-- | internal/ceres/line_search_minimizer.cc | 200 |
1 files changed, 120 insertions, 80 deletions
diff --git a/internal/ceres/line_search_minimizer.cc b/internal/ceres/line_search_minimizer.cc index 2cc89fa..ae77a73 100644 --- a/internal/ceres/line_search_minimizer.cc +++ b/internal/ceres/line_search_minimizer.cc @@ -38,8 +38,6 @@ // For details on the theory and implementation see "Numerical // Optimization" by Nocedal & Wright. -#ifndef CERES_NO_LINE_SEARCH_MINIMIZER - #include "ceres/line_search_minimizer.h" #include <algorithm> @@ -64,25 +62,36 @@ namespace ceres { namespace internal { namespace { -// Small constant for various floating point issues. -// TODO(sameeragarwal): Change to a better name if this has only one -// use. -const double kEpsilon = 1e-12; +// TODO(sameeragarwal): I think there is a small bug here, in that if +// the evaluation fails, then the state can contain garbage. Look at +// this more carefully. bool Evaluate(Evaluator* evaluator, const Vector& x, - LineSearchMinimizer::State* state) { - const bool status = evaluator->Evaluate(x.data(), - &(state->cost), - NULL, - state->gradient.data(), - NULL); - if (status) { - state->gradient_squared_norm = state->gradient.squaredNorm(); - state->gradient_max_norm = state->gradient.lpNorm<Eigen::Infinity>(); + LineSearchMinimizer::State* state, + string* message) { + if (!evaluator->Evaluate(x.data(), + &(state->cost), + NULL, + state->gradient.data(), + NULL)) { + *message = "Gradient evaluation failed."; + return false; + } + + Vector negative_gradient = -state->gradient; + Vector projected_gradient_step(x.size()); + if (!evaluator->Plus(x.data(), + negative_gradient.data(), + projected_gradient_step.data())) { + *message = "projected_gradient_step = Plus(x, -gradient) failed."; + return false; } - return status; + state->gradient_squared_norm = (x - projected_gradient_step).squaredNorm(); + state->gradient_max_norm = + (x - projected_gradient_step).lpNorm<Eigen::Infinity>(); + return true; } } // namespace @@ -90,6 +99,7 @@ bool Evaluate(Evaluator* evaluator, void LineSearchMinimizer::Minimize(const Minimizer::Options& options, double* parameters, Solver::Summary* summary) { + const bool is_not_silent = !options.is_silent; double start_time = WallTimeInSeconds(); double iteration_start_time = start_time; @@ -115,14 +125,17 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, iteration_summary.step_is_successful = false; iteration_summary.cost_change = 0.0; iteration_summary.gradient_max_norm = 0.0; + iteration_summary.gradient_norm = 0.0; iteration_summary.step_norm = 0.0; iteration_summary.linear_solver_iterations = 0; iteration_summary.step_solver_time_in_seconds = 0; // Do initial cost and Jacobian evaluation. - if (!Evaluate(evaluator, x, ¤t_state)) { - LOG(WARNING) << "Terminating: Cost and gradient evaluation failed."; - summary->termination_type = NUMERICAL_FAILURE; + if (!Evaluate(evaluator, x, ¤t_state, &summary->message)) { + summary->termination_type = FAILURE; + summary->message = "Initial cost and jacobian evaluation failed. " + "More details: " + summary->message; + LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; return; } @@ -130,20 +143,15 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, iteration_summary.cost = current_state.cost + summary->fixed_cost; iteration_summary.gradient_max_norm = current_state.gradient_max_norm; - - // The initial gradient max_norm is bounded from below so that we do - // not divide by zero. - const double initial_gradient_max_norm = - max(iteration_summary.gradient_max_norm, kEpsilon); - const double absolute_gradient_tolerance = - options.gradient_tolerance * initial_gradient_max_norm; - - if (iteration_summary.gradient_max_norm <= absolute_gradient_tolerance) { - summary->termination_type = GRADIENT_TOLERANCE; - VLOG(1) << "Terminating: Gradient tolerance reached." - << "Relative gradient max norm: " - << iteration_summary.gradient_max_norm / initial_gradient_max_norm - << " <= " << options.gradient_tolerance; + iteration_summary.gradient_norm = sqrt(current_state.gradient_squared_norm); + + if (iteration_summary.gradient_max_norm <= options.gradient_tolerance) { + summary->message = StringPrintf("Gradient tolerance reached. " + "Gradient max norm: %e <= %e", + iteration_summary.gradient_max_norm, + options.gradient_tolerance); + summary->termination_type = CONVERGENCE; + VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; return; } @@ -188,11 +196,10 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, scoped_ptr<LineSearch> line_search(LineSearch::Create(options.line_search_type, line_search_options, - &summary->error)); + &summary->message)); if (line_search.get() == NULL) { - LOG(ERROR) << "Ceres bug: Unable to create a LineSearch object, please " - << "contact the developers!, error: " << summary->error; - summary->termination_type = DID_NOT_RUN; + summary->termination_type = FAILURE; + LOG_IF(ERROR, is_not_silent) << "Terminating: " << summary->message; return; } @@ -200,22 +207,24 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, int num_line_search_direction_restarts = 0; while (true) { - if (!RunCallbacks(options.callbacks, iteration_summary, summary)) { - return; + if (!RunCallbacks(options, iteration_summary, summary)) { + break; } iteration_start_time = WallTimeInSeconds(); if (iteration_summary.iteration >= options.max_num_iterations) { + summary->message = "Maximum number of iterations reached."; summary->termination_type = NO_CONVERGENCE; - VLOG(1) << "Terminating: Maximum number of iterations reached."; + VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; break; } const double total_solver_time = iteration_start_time - start_time + summary->preprocessor_time_in_seconds; if (total_solver_time >= options.max_solver_time_in_seconds) { + summary->message = "Maximum solver time reached."; summary->termination_type = NO_CONVERGENCE; - VLOG(1) << "Terminating: Maximum solver time reached."; + VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; break; } @@ -240,14 +249,13 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, // Line search direction failed to generate a new direction, and we // have already reached our specified maximum number of restarts, // terminate optimization. - summary->error = + summary->message = StringPrintf("Line search direction failure: specified " "max_num_line_search_direction_restarts: %d reached.", options.max_num_line_search_direction_restarts); - LOG(WARNING) << summary->error << " terminating optimization."; - summary->termination_type = NUMERICAL_FAILURE; + summary->termination_type = FAILURE; + LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; break; - } else if (!line_search_status) { // Restart line search direction with gradient descent on first iteration // as we have not yet reached our maximum number of restarts. @@ -255,13 +263,16 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, options.max_num_line_search_direction_restarts); ++num_line_search_direction_restarts; - LOG(WARNING) + LOG_IF(WARNING, is_not_silent) << "Line search direction algorithm: " - << LineSearchDirectionTypeToString(options.line_search_direction_type) - << ", failed to produce a valid new direction at iteration: " - << iteration_summary.iteration << ". Restarting, number of " - << "restarts: " << num_line_search_direction_restarts << " / " - << options.max_num_line_search_direction_restarts << " [max]."; + << LineSearchDirectionTypeToString( + options.line_search_direction_type) + << ", failed to produce a valid new direction at " + << "iteration: " << iteration_summary.iteration + << ". Restarting, number of restarts: " + << num_line_search_direction_restarts << " / " + << options.max_num_line_search_direction_restarts + << " [max]."; line_search_direction.reset( LineSearchDirection::Create(line_search_direction_options)); current_state.search_direction = -current_state.gradient; @@ -286,14 +297,14 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, // direction in a line search, most likely cause for this being violated // would be a numerical failure in the line search direction calculation. if (initial_step_size < 0.0) { - summary->error = + summary->message = StringPrintf("Numerical failure in line search, initial_step_size is " "negative: %.5e, directional_derivative: %.5e, " "(current_cost - previous_cost): %.5e", initial_step_size, current_state.directional_derivative, (current_state.cost - previous_state.cost)); - LOG(WARNING) << summary->error; - summary->termination_type = NUMERICAL_FAILURE; + summary->termination_type = FAILURE; + LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; break; } @@ -301,6 +312,18 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, current_state.cost, current_state.directional_derivative, &line_search_summary); + if (!line_search_summary.success) { + summary->message = + StringPrintf("Numerical failure in line search, failed to find " + "a valid step size, (did not run out of iterations) " + "using initial_step_size: %.5e, initial_cost: %.5e, " + "initial_gradient: %.5e.", + initial_step_size, current_state.cost, + current_state.directional_derivative); + LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; + summary->termination_type = FAILURE; + break; + } current_state.step_size = line_search_summary.optimal_step_size; delta = current_state.step_size * current_state.search_direction; @@ -309,36 +332,31 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, iteration_summary.step_solver_time_in_seconds = WallTimeInSeconds() - iteration_start_time; - // TODO(sameeragarwal): Collect stats. - if (!evaluator->Plus(x.data(), delta.data(), x_plus_delta.data()) || - !Evaluate(evaluator, x_plus_delta, ¤t_state)) { - LOG(WARNING) << "Evaluation failed."; + if (!evaluator->Plus(x.data(), delta.data(), x_plus_delta.data())) { + summary->termination_type = FAILURE; + summary->message = + "x_plus_delta = Plus(x, delta) failed. This should not happen " + "as the step was valid when it was selected by the line search."; + LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; + break; + } else if (!Evaluate(evaluator, + x_plus_delta, + ¤t_state, + &summary->message)) { + summary->termination_type = FAILURE; + summary->message = + "Step failed to evaluate. This should not happen as the step was " + "valid when it was selected by the line search. More details: " + + summary->message; + LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message; + break; } else { x = x_plus_delta; } iteration_summary.gradient_max_norm = current_state.gradient_max_norm; - if (iteration_summary.gradient_max_norm <= absolute_gradient_tolerance) { - summary->termination_type = GRADIENT_TOLERANCE; - VLOG(1) << "Terminating: Gradient tolerance reached." - << "Relative gradient max norm: " - << iteration_summary.gradient_max_norm / initial_gradient_max_norm - << " <= " << options.gradient_tolerance; - break; - } - + iteration_summary.gradient_norm = sqrt(current_state.gradient_squared_norm); iteration_summary.cost_change = previous_state.cost - current_state.cost; - const double absolute_function_tolerance = - options.function_tolerance * previous_state.cost; - if (fabs(iteration_summary.cost_change) < absolute_function_tolerance) { - VLOG(1) << "Terminating. Function tolerance reached. " - << "|cost_change|/cost: " - << fabs(iteration_summary.cost_change) / previous_state.cost - << " <= " << options.function_tolerance; - summary->termination_type = FUNCTION_TOLERANCE; - return; - } - iteration_summary.cost = current_state.cost + summary->fixed_cost; iteration_summary.step_norm = delta.norm(); iteration_summary.step_is_valid = true; @@ -359,10 +377,32 @@ void LineSearchMinimizer::Minimize(const Minimizer::Options& options, summary->iterations.push_back(iteration_summary); ++summary->num_successful_steps; + + if (iteration_summary.gradient_max_norm <= options.gradient_tolerance) { + summary->message = StringPrintf("Gradient tolerance reached. " + "Gradient max norm: %e <= %e", + iteration_summary.gradient_max_norm, + options.gradient_tolerance); + summary->termination_type = CONVERGENCE; + VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; + break; + } + + const double absolute_function_tolerance = + options.function_tolerance * previous_state.cost; + if (fabs(iteration_summary.cost_change) < absolute_function_tolerance) { + summary->message = + StringPrintf("Function tolerance reached. " + "|cost_change|/cost: %e <= %e", + fabs(iteration_summary.cost_change) / + previous_state.cost, + options.function_tolerance); + summary->termination_type = CONVERGENCE; + VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message; + break; + } } } } // namespace internal } // namespace ceres - -#endif // CERES_NO_LINE_SEARCH_MINIMIZER |