diff options
Diffstat (limited to 'extern/ceres/internal/ceres/line_search.cc')
| -rw-r--r-- | extern/ceres/internal/ceres/line_search.cc | 327 |
1 files changed, 168 insertions, 159 deletions
diff --git a/extern/ceres/internal/ceres/line_search.cc b/extern/ceres/internal/ceres/line_search.cc index 352c64f5057..7e871a20a53 100644 --- a/extern/ceres/internal/ceres/line_search.cc +++ b/extern/ceres/internal/ceres/line_search.cc @@ -57,10 +57,10 @@ namespace { const int kErrorMessageNumericPrecision = 8; } // namespace -ostream& operator<<(ostream &os, const FunctionSample& sample); +ostream& operator<<(ostream& os, const FunctionSample& sample); // Convenience stream operator for pushing FunctionSamples into log messages. -ostream& operator<<(ostream &os, const FunctionSample& sample) { +ostream& operator<<(ostream& os, const FunctionSample& sample) { os << sample.ToDebugString(); return os; } @@ -73,17 +73,17 @@ LineSearch* LineSearch::Create(const LineSearchType line_search_type, string* error) { LineSearch* line_search = NULL; switch (line_search_type) { - case ceres::ARMIJO: - line_search = new ArmijoLineSearch(options); - break; - case ceres::WOLFE: - line_search = new WolfeLineSearch(options); - break; - default: - *error = string("Invalid line search algorithm type: ") + - LineSearchTypeToString(line_search_type) + - string(", unable to create line search."); - return NULL; + case ceres::ARMIJO: + line_search = new ArmijoLineSearch(options); + break; + case ceres::WOLFE: + line_search = new WolfeLineSearch(options); + break; + default: + *error = string("Invalid line search algorithm type: ") + + LineSearchTypeToString(line_search_type) + + string(", unable to create line search."); + return NULL; } return line_search; } @@ -96,8 +96,7 @@ LineSearchFunction::LineSearchFunction(Evaluator* evaluator) initial_evaluator_residual_time_in_seconds(0.0), initial_evaluator_jacobian_time_in_seconds(0.0) {} -void LineSearchFunction::Init(const Vector& position, - const Vector& direction) { +void LineSearchFunction::Init(const Vector& position, const Vector& direction) { position_ = position; direction_ = direction; } @@ -200,9 +199,9 @@ void LineSearch::Search(double step_size_estimate, summary->polynomial_minimization_time_in_seconds = 0.0; options().function->ResetTimeStatistics(); this->DoSearch(step_size_estimate, initial_cost, initial_gradient, summary); - options().function-> - TimeStatistics(&summary->cost_evaluation_time_in_seconds, - &summary->gradient_evaluation_time_in_seconds); + options().function->TimeStatistics( + &summary->cost_evaluation_time_in_seconds, + &summary->gradient_evaluation_time_in_seconds); summary->total_time_in_seconds = WallTimeInSeconds() - start_time; } @@ -218,8 +217,7 @@ double LineSearch::InterpolatingPolynomialMinimizingStepSize( const double min_step_size, const double max_step_size) const { if (!current.value_is_valid || - (interpolation_type == BISECTION && - max_step_size <= current.x)) { + (interpolation_type == BISECTION && max_step_size <= current.x)) { // Either: sample is invalid; or we are using BISECTION and contracting // the step size. return std::min(std::max(current.x * 0.5, min_step_size), max_step_size); @@ -274,8 +272,8 @@ double LineSearch::InterpolatingPolynomialMinimizingStepSize( } double step_size = 0.0, unused_min_value = 0.0; - MinimizeInterpolatingPolynomial(samples, min_step_size, max_step_size, - &step_size, &unused_min_value); + MinimizeInterpolatingPolynomial( + samples, min_step_size, max_step_size, &step_size, &unused_min_value); return step_size; } @@ -315,41 +313,43 @@ void ArmijoLineSearch::DoSearch(const double step_size_estimate, function->Evaluate(step_size_estimate, kEvaluateGradient, ¤t); while (!current.value_is_valid || - current.value > (initial_cost - + options().sufficient_decrease - * initial_gradient - * current.x)) { + current.value > (initial_cost + options().sufficient_decrease * + initial_gradient * current.x)) { // If current.value_is_valid is false, we treat it as if the cost at that // point is not large enough to satisfy the sufficient decrease condition. ++summary->num_iterations; if (summary->num_iterations >= options().max_num_iterations) { - summary->error = - StringPrintf("Line search failed: Armijo failed to find a point " - "satisfying the sufficient decrease condition within " - "specified max_num_iterations: %d.", - options().max_num_iterations); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: Armijo failed to find a point " + "satisfying the sufficient decrease condition within " + "specified max_num_iterations: %d.", + options().max_num_iterations); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } return; } const double polynomial_minimization_start_time = WallTimeInSeconds(); - const double step_size = - this->InterpolatingPolynomialMinimizingStepSize( - options().interpolation_type, - initial_position, - previous, - current, - (options().max_step_contraction * current.x), - (options().min_step_contraction * current.x)); + const double step_size = this->InterpolatingPolynomialMinimizingStepSize( + options().interpolation_type, + initial_position, + previous, + current, + (options().max_step_contraction * current.x), + (options().min_step_contraction * current.x)); summary->polynomial_minimization_time_in_seconds += (WallTimeInSeconds() - polynomial_minimization_start_time); if (step_size * descent_direction_max_norm < options().min_step_size) { - summary->error = - StringPrintf("Line search failed: step_size too small: %.5e " - "with descent_direction_max_norm: %.5e.", step_size, - descent_direction_max_norm); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: step_size too small: %.5e " + "with descent_direction_max_norm: %.5e.", + step_size, + descent_direction_max_norm); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } return; } @@ -435,8 +435,8 @@ void WolfeLineSearch::DoSearch(const double step_size_estimate, } VLOG(3) << std::scientific << std::setprecision(kErrorMessageNumericPrecision) - << "Starting line search zoom phase with bracket_low: " - << bracket_low << ", bracket_high: " << bracket_high + << "Starting line search zoom phase with bracket_low: " << bracket_low + << ", bracket_high: " << bracket_high << ", bracket width: " << fabs(bracket_low.x - bracket_high.x) << ", bracket abs delta cost: " << fabs(bracket_low.value - bracket_high.value); @@ -461,11 +461,9 @@ void WolfeLineSearch::DoSearch(const double step_size_estimate, // but still has bracket_high.value < initial_position.value. // 3. bracket_high is chosen after bracket_low, s.t. // bracket_low.gradient * (bracket_high.x - bracket_low.x) < 0. - if (!this->ZoomPhase(initial_position, - bracket_low, - bracket_high, - &solution, - summary) && !solution.value_is_valid) { + if (!this->ZoomPhase( + initial_position, bracket_low, bracket_high, &solution, summary) && + !solution.value_is_valid) { // Failed to find a valid point (given the specified decrease parameters) // within the specified bracket. return; @@ -501,20 +499,18 @@ void WolfeLineSearch::DoSearch(const double step_size_estimate, // // Returns false if no step size > minimum step size was found which // satisfies at least the Armijo condition. -bool WolfeLineSearch::BracketingPhase( - const FunctionSample& initial_position, - const double step_size_estimate, - FunctionSample* bracket_low, - FunctionSample* bracket_high, - bool* do_zoom_search, - Summary* summary) const { +bool WolfeLineSearch::BracketingPhase(const FunctionSample& initial_position, + const double step_size_estimate, + FunctionSample* bracket_low, + FunctionSample* bracket_high, + bool* do_zoom_search, + Summary* summary) const { LineSearchFunction* function = options().function; FunctionSample previous = initial_position; FunctionSample current; - const double descent_direction_max_norm = - function->DirectionInfinityNorm(); + const double descent_direction_max_norm = function->DirectionInfinityNorm(); *do_zoom_search = false; *bracket_low = initial_position; @@ -536,10 +532,9 @@ bool WolfeLineSearch::BracketingPhase( ++summary->num_iterations; if (current.value_is_valid && - (current.value > (initial_position.value - + options().sufficient_decrease - * initial_position.gradient - * current.x) || + (current.value > (initial_position.value + + options().sufficient_decrease * + initial_position.gradient * current.x) || (previous.value_is_valid && current.value > previous.value))) { // Bracket found: current step size violates Armijo sufficient decrease // condition, or has stepped past an inflection point of f() relative to @@ -556,8 +551,8 @@ bool WolfeLineSearch::BracketingPhase( } if (current.value_is_valid && - fabs(current.gradient) <= - -options().sufficient_curvature_decrease * initial_position.gradient) { + fabs(current.gradient) <= -options().sufficient_curvature_decrease * + initial_position.gradient) { // Current step size satisfies the strong Wolfe conditions, and is thus a // valid termination point, therefore a Zoom not required. *bracket_low = current; @@ -585,23 +580,25 @@ bool WolfeLineSearch::BracketingPhase( break; } else if (current.value_is_valid && - fabs(current.x - previous.x) * descent_direction_max_norm - < options().min_step_size) { + fabs(current.x - previous.x) * descent_direction_max_norm < + options().min_step_size) { // We have shrunk the search bracket to a width less than our tolerance, // and still not found either a point satisfying the strong Wolfe // conditions, or a valid bracket containing such a point. Stop searching // and set bracket_low to the size size amongst all those tested which // minimizes f() and satisfies the Armijo condition. - LOG_IF(WARNING, !options().is_silent) - << "Line search failed: Wolfe bracketing phase shrank " - << "bracket width: " << fabs(current.x - previous.x) - << ", to < tolerance: " << options().min_step_size - << ", with descent_direction_max_norm: " - << descent_direction_max_norm << ", and failed to find " - << "a point satisfying the strong Wolfe conditions or a " - << "bracketing containing such a point. Accepting " - << "point found satisfying Armijo condition only, to " - << "allow continuation."; + + if (!options().is_silent) { + LOG(WARNING) << "Line search failed: Wolfe bracketing phase shrank " + << "bracket width: " << fabs(current.x - previous.x) + << ", to < tolerance: " << options().min_step_size + << ", with descent_direction_max_norm: " + << descent_direction_max_norm << ", and failed to find " + << "a point satisfying the strong Wolfe conditions or a " + << "bracketing containing such a point. Accepting " + << "point found satisfying Armijo condition only, to " + << "allow continuation."; + } *bracket_low = current; break; @@ -609,18 +606,22 @@ bool WolfeLineSearch::BracketingPhase( // Check num iterations bound here so that we always evaluate the // max_num_iterations-th iteration against all conditions, and // then perform no additional (unused) evaluations. - summary->error = - StringPrintf("Line search failed: Wolfe bracketing phase failed to " - "find a point satisfying strong Wolfe conditions, or a " - "bracket containing such a point within specified " - "max_num_iterations: %d", options().max_num_iterations); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: Wolfe bracketing phase failed to " + "find a point satisfying strong Wolfe conditions, or a " + "bracket containing such a point within specified " + "max_num_iterations: %d", + options().max_num_iterations); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } // Ensure that bracket_low is always set to the step size amongst all // those tested which minimizes f() and satisfies the Armijo condition // when we terminate due to the 'artificial' max_num_iterations condition. *bracket_low = current.value_is_valid && current.value < bracket_low->value - ? current : *bracket_low; + ? current + : *bracket_low; break; } // Either: f(current) is invalid; or, f(current) is valid, but does not @@ -632,17 +633,16 @@ bool WolfeLineSearch::BracketingPhase( // size. // // In Nocedal & Wright [1] (p60), the step-size can only increase in the - // bracketing phase: step_size_{k+1} \in [step_size_k, step_size_k * factor]. - // However this does not account for the function returning invalid values - // which we support, in which case we need to contract the step size whilst - // ensuring that we do not invert the bracket, i.e, we require that: + // bracketing phase: step_size_{k+1} \in [step_size_k, step_size_k * + // factor]. However this does not account for the function returning invalid + // values which we support, in which case we need to contract the step size + // whilst ensuring that we do not invert the bracket, i.e, we require that: // step_size_{k-1} <= step_size_{k+1} < step_size_k. const double min_step_size = - current.value_is_valid - ? current.x : previous.x; + current.value_is_valid ? current.x : previous.x; const double max_step_size = - current.value_is_valid - ? (current.x * options().max_step_expansion) : current.x; + current.value_is_valid ? (current.x * options().max_step_expansion) + : current.x; // We are performing 2-point interpolation only here, but the API of // InterpolatingPolynomialMinimizingStepSize() allows for up to @@ -652,22 +652,24 @@ bool WolfeLineSearch::BracketingPhase( DCHECK(!unused_previous.value_is_valid); // Contracts step size if f(current) is not valid. const double polynomial_minimization_start_time = WallTimeInSeconds(); - const double step_size = - this->InterpolatingPolynomialMinimizingStepSize( - options().interpolation_type, - previous, - unused_previous, - current, - min_step_size, - max_step_size); + const double step_size = this->InterpolatingPolynomialMinimizingStepSize( + options().interpolation_type, + previous, + unused_previous, + current, + min_step_size, + max_step_size); summary->polynomial_minimization_time_in_seconds += (WallTimeInSeconds() - polynomial_minimization_start_time); if (step_size * descent_direction_max_norm < options().min_step_size) { - summary->error = - StringPrintf("Line search failed: step_size too small: %.5e " - "with descent_direction_max_norm: %.5e", step_size, - descent_direction_max_norm); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: step_size too small: %.5e " + "with descent_direction_max_norm: %.5e", + step_size, + descent_direction_max_norm); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } return false; } @@ -684,8 +686,8 @@ bool WolfeLineSearch::BracketingPhase( // Ensure that even if a valid bracket was found, we will only mark a zoom // as required if the bracket's width is greater than our minimum tolerance. if (*do_zoom_search && - fabs(bracket_high->x - bracket_low->x) * descent_direction_max_norm - < options().min_step_size) { + fabs(bracket_high->x - bracket_low->x) * descent_direction_max_norm < + options().min_step_size) { *do_zoom_search = false; } @@ -707,8 +709,7 @@ bool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, << std::scientific << std::setprecision(kErrorMessageNumericPrecision) << "Ceres bug: f_low input to Wolfe Zoom invalid, please contact " << "the developers!, initial_position: " << initial_position - << ", bracket_low: " << bracket_low - << ", bracket_high: "<< bracket_high; + << ", bracket_low: " << bracket_low << ", bracket_high: " << bracket_high; // We do not require bracket_high.gradient_is_valid as the gradient condition // for a valid bracket is only dependent upon bracket_low.gradient, and // in order to minimize jacobian evaluations, bracket_high.gradient may @@ -725,8 +726,7 @@ bool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, << std::scientific << std::setprecision(kErrorMessageNumericPrecision) << "Ceres bug: f_high input to Wolfe Zoom invalid, please " << "contact the developers!, initial_position: " << initial_position - << ", bracket_low: " << bracket_low - << ", bracket_high: "<< bracket_high; + << ", bracket_low: " << bracket_low << ", bracket_high: " << bracket_high; if (bracket_low.gradient * (bracket_high.x - bracket_low.x) >= 0) { // The third condition for a valid initial bracket: @@ -738,18 +738,20 @@ bool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, // returns inconsistent gradient values relative to the function values, // we do not CHECK_LT(), but we do stop processing and return an invalid // value. - summary->error = - StringPrintf("Line search failed: Wolfe zoom phase passed a bracket " - "which does not satisfy: bracket_low.gradient * " - "(bracket_high.x - bracket_low.x) < 0 [%.8e !< 0] " - "with initial_position: %s, bracket_low: %s, bracket_high:" - " %s, the most likely cause of which is the cost function " - "returning inconsistent gradient & function values.", - bracket_low.gradient * (bracket_high.x - bracket_low.x), - initial_position.ToDebugString().c_str(), - bracket_low.ToDebugString().c_str(), - bracket_high.ToDebugString().c_str()); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: Wolfe zoom phase passed a bracket " + "which does not satisfy: bracket_low.gradient * " + "(bracket_high.x - bracket_low.x) < 0 [%.8e !< 0] " + "with initial_position: %s, bracket_low: %s, bracket_high:" + " %s, the most likely cause of which is the cost function " + "returning inconsistent gradient & function values.", + bracket_low.gradient * (bracket_high.x - bracket_low.x), + initial_position.ToDebugString().c_str(), + bracket_low.ToDebugString().c_str(), + bracket_high.ToDebugString().c_str()); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } solution->value_is_valid = false; return false; } @@ -763,25 +765,30 @@ bool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, // not satisfy the Wolfe condition. *solution = bracket_low; if (summary->num_iterations >= options().max_num_iterations) { - summary->error = - StringPrintf("Line search failed: Wolfe zoom phase failed to " - "find a point satisfying strong Wolfe conditions " - "within specified max_num_iterations: %d, " - "(num iterations taken for bracketing: %d).", - options().max_num_iterations, num_bracketing_iterations); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: Wolfe zoom phase failed to " + "find a point satisfying strong Wolfe conditions " + "within specified max_num_iterations: %d, " + "(num iterations taken for bracketing: %d).", + options().max_num_iterations, + num_bracketing_iterations); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } return false; } - if (fabs(bracket_high.x - bracket_low.x) * descent_direction_max_norm - < options().min_step_size) { + if (fabs(bracket_high.x - bracket_low.x) * descent_direction_max_norm < + options().min_step_size) { // Bracket width has been reduced below tolerance, and no point satisfying // the strong Wolfe conditions has been found. - summary->error = - StringPrintf("Line search failed: Wolfe zoom bracket width: %.5e " - "too small with descent_direction_max_norm: %.5e.", - fabs(bracket_high.x - bracket_low.x), - descent_direction_max_norm); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: Wolfe zoom bracket width: %.5e " + "too small with descent_direction_max_norm: %.5e.", + fabs(bracket_high.x - bracket_low.x), + descent_direction_max_norm); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } return false; } @@ -799,14 +806,13 @@ bool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, const FunctionSample unused_previous; DCHECK(!unused_previous.value_is_valid); const double polynomial_minimization_start_time = WallTimeInSeconds(); - const double step_size = - this->InterpolatingPolynomialMinimizingStepSize( - options().interpolation_type, - lower_bound_step, - unused_previous, - upper_bound_step, - lower_bound_step.x, - upper_bound_step.x); + const double step_size = this->InterpolatingPolynomialMinimizingStepSize( + options().interpolation_type, + lower_bound_step, + unused_previous, + upper_bound_step, + lower_bound_step.x, + upper_bound_step.x); summary->polynomial_minimization_time_in_seconds += (WallTimeInSeconds() - polynomial_minimization_start_time); // No check on magnitude of step size being too small here as it is @@ -826,13 +832,17 @@ bool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, const bool kEvaluateGradient = true; function->Evaluate(step_size, kEvaluateGradient, solution); if (!solution->value_is_valid || !solution->gradient_is_valid) { - summary->error = - StringPrintf("Line search failed: Wolfe Zoom phase found " - "step_size: %.5e, for which function is invalid, " - "between low_step: %.5e and high_step: %.5e " - "at which function is valid.", - solution->x, bracket_low.x, bracket_high.x); - LOG_IF(WARNING, !options().is_silent) << summary->error; + summary->error = StringPrintf( + "Line search failed: Wolfe Zoom phase found " + "step_size: %.5e, for which function is invalid, " + "between low_step: %.5e and high_step: %.5e " + "at which function is valid.", + solution->x, + bracket_low.x, + bracket_high.x); + if (!options().is_silent) { + LOG(WARNING) << summary->error; + } return false; } @@ -842,10 +852,9 @@ bool WolfeLineSearch::ZoomPhase(const FunctionSample& initial_position, << ", bracket_high: " << bracket_high << ", minimizing solution: " << *solution; - if ((solution->value > (initial_position.value - + options().sufficient_decrease - * initial_position.gradient - * solution->x)) || + if ((solution->value > (initial_position.value + + options().sufficient_decrease * + initial_position.gradient * solution->x)) || (solution->value >= bracket_low.value)) { // Armijo sufficient decrease not satisfied, or not better // than current lowest sample, use as new upper bound. |