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

internal/ceres/line_search.cc

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;