Fix lower-bound on result of minimising step-size polynomial.
- Previously we were requesting a step-size which minimised the
polynomial in: [previous.x, current.x * factor].
- This is incorrect c/f Nocedal & Wright p60, the bounds for the
minimising step-size should be: [current.x, current.x * factor].
- However, Nocedal & Wright's bounds are insufficient when the function
can return invalid values, which we support.
- In the case that f(current) is invalid, we need to contract the
step-size to lie within: [previous.x, current.x) given that we know
that previous.x is valid so a valid step must exist within that range.
Change-Id: I67b5aaa09cc6d54cf5f264e2cf894ddc2af3f3ad
diff --git a/internal/ceres/line_search.cc b/internal/ceres/line_search.cc
index 86302a9..dd73b0e 100644
--- a/internal/ceres/line_search.cc
+++ b/internal/ceres/line_search.cc
@@ -627,7 +627,18 @@
// being a boundary of a bracket.
// If f(current) is valid, (but meets no criteria) expand the search by
- // increasing the step size.
+ // increasing the step size. If f(current) is invalid, contract the step
+ // 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:
+ // step_size_{k-1} <= step_size_{k+1} < step_size_k.
+ const double min_step_size =
+ 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;
@@ -646,7 +657,7 @@
previous,
unused_previous,
current,
- previous.x,
+ min_step_size,
max_step_size);
summary->polynomial_minimization_time_in_seconds +=
(WallTimeInSeconds() - polynomial_minimization_start_time);
@@ -659,6 +670,10 @@
return false;
}
+ // Only advance the lower boundary (in x) of the bracket if f(current)
+ // is valid such that we can support contracting the step size when
+ // f(current) is invalid without risking inverting the bracket in x, i.e.
+ // prevent previous.x > current.x.
previous = current.value_is_valid ? current : previous;
++summary->num_function_evaluations;
++summary->num_gradient_evaluations;
