diff --git a/docs/source/solving.rst b/docs/source/solving.rst
index 25b19b0..e8dfd9f 100644
--- a/docs/source/solving.rst
+++ b/docs/source/solving.rst
@@ -1112,10 +1112,12 @@
 
    Solver terminates if
 
-   .. math:: \frac{\|g(x)\|_\infty}{\|g(x_0)\|_\infty} < \text{gradient_tolerance}
+   .. math:: \|x - \Pi \boxplus(x, -g(x))\|_\infty < \text{gradient_tolerance}
 
-   where :math:`\|\cdot\|_\infty` refers to the max norm, and :math:`x_0` is
-   the vector of initial parameter values.
+   where :math:`\|\cdot\|_\infty` refers to the max norm, :math:`\Pi`
+   is projection onto the bounds constraints and :math:`\boxplus` is
+   Plus operation that for the overall local parameterization
+   associated with the parameter vector.
 
 .. member:: double Solver::Options::parameter_tolerance
 
@@ -2471,4 +2473,3 @@
  covariance.GetCovarianceBlock(x, x, covariance_xx)
  covariance.GetCovarianceBlock(y, y, covariance_yy)
  covariance.GetCovarianceBlock(x, y, covariance_xy)
-
diff --git a/docs/source/tutorial.rst b/docs/source/tutorial.rst
index 00c65a9..fdee1b8 100644
--- a/docs/source/tutorial.rst
+++ b/docs/source/tutorial.rst
@@ -122,7 +122,7 @@
       0: f: 1.250000e+01 d: 0.00e+00 g: 5.00e+00 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li:  0 it: 6.91e-06 tt: 1.91e-03
       1: f: 1.249750e-07 d: 1.25e+01 g: 5.00e-04 h: 5.00e+00 rho: 1.00e+00 mu: 3.00e+04 li:  1 it: 2.81e-05 tt: 1.99e-03
       2: f: 1.388518e-16 d: 1.25e-07 g: 1.67e-08 h: 5.00e-04 rho: 1.00e+00 mu: 9.00e+04 li:  1 it: 1.00e-05 tt: 2.01e-03
-   Ceres Solver Report: Iterations: 2, Initial cost: 1.250000e+01, Final cost: 1.388518e-16, Termination: PARAMETER_TOLERANCE.
+   Ceres Solver Report: Iterations: 2, Initial cost: 1.250000e+01, Final cost: 1.388518e-16, Termination: CONVERGENCE.
    x : 5 -> 10
 
 Starting from a :math:`x=5`, the solver in two iterations goes to 10
@@ -372,7 +372,7 @@
     9: f: 1.173223e-09 d: 1.76e-08 g: 1.19e-06 h: 4.81e-03 rho: 9.37e-01 mu: 1.97e+08 li:  1 it: 0.00e+00 tt: 0.00e+00
    10: f: 7.333425e-11 d: 1.10e-09 g: 1.49e-07 h: 2.40e-03 rho: 9.37e-01 mu: 5.90e+08 li:  1 it: 0.00e+00 tt: 0.00e+00
    11: f: 4.584044e-12 d: 6.88e-11 g: 1.86e-08 h: 1.20e-03 rho: 9.37e-01 mu: 1.77e+09 li:  1 it: 0.00e+00 tt: 0.00e+00
- Ceres Solver Report: Iterations: 12, Initial cost: 1.075000e+02, Final cost: 4.584044e-12, Termination: GRADIENT_TOLERANCE.
+ Ceres Solver Report: Iterations: 12, Initial cost: 1.075000e+02, Final cost: 4.584044e-12, Termination: CONVERGENCE.
  Final x1 = 0.00116741, x2 = -0.000116741, x3 = 0.000190535, x4 = 0.000190535
 
 It is easy to see that the optimal solution to this problem is at
@@ -461,7 +461,7 @@
    11: f: 1.063265e+00 d: 1.48e-01 g: 1.44e+00 h: 6.06e-02 rho: 9.97e-01 mu: 2.22e+02 li:  1 it: 0.00e+00 tt: 0.00e+00
    12: f: 1.056795e+00 d: 6.47e-03 g: 1.18e-01 h: 1.47e-02 rho: 1.00e+00 mu: 6.67e+02 li:  1 it: 0.00e+00 tt: 0.00e+00
    13: f: 1.056751e+00 d: 4.39e-05 g: 3.79e-03 h: 1.28e-03 rho: 1.00e+00 mu: 2.00e+03 li:  1 it: 0.00e+00 tt: 0.00e+00
- Ceres Solver Report: Iterations: 13, Initial cost: 1.211734e+02, Final cost: 1.056751e+00, Termination: FUNCTION_TOLERANCE.
+ Ceres Solver Report: Iterations: 13, Initial cost: 1.211734e+02, Final cost: 1.056751e+00, Termination: CONVERGENCE.
  Initial m: 0 c: 0
  Final   m: 0.291861 c: 0.131439
 
@@ -713,5 +713,3 @@
 #. `libmv_bundle_adjuster.cc
    <https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/libmv_bundle_adjuster.cc>`_
    is the bundle adjustment algorithm used by `Blender <www.blender.org>`_/libmv.
-
-
diff --git a/internal/ceres/trust_region_minimizer.cc b/internal/ceres/trust_region_minimizer.cc
index e2f1234..67f2b08 100644
--- a/internal/ceres/trust_region_minimizer.cc
+++ b/internal/ceres/trust_region_minimizer.cc
@@ -66,9 +66,9 @@
                                  const Vector& delta,
                                  Evaluator* evaluator) {
   LineSearchFunction line_search_function(evaluator);
-  line_search_function.Init(x, delta);
 
   LineSearch::Options line_search_options;
+  line_search_options.is_silent = true;
   line_search_options.interpolation_type =
       options.line_search_interpolation_type;
   line_search_options.min_step_size = options.min_line_search_step_size;
@@ -93,7 +93,15 @@
                                          line_search_options,
                                          &message)));
   LineSearch::Summary summary;
+  line_search_function.Init(x, delta);
+  // Try the trust region step.
   line_search->Search(1.0, cost, gradient.dot(delta), &summary);
+  if (!summary.success) {
+    // If that was not successful, try the negative gradient as a
+    // search direction.
+    line_search_function.Init(x, -gradient);
+    line_search->Search(1.0, cost, -gradient.squaredNorm(), &summary);
+  }
   return summary;
 }
 
@@ -560,6 +568,7 @@
     if (iteration_summary.step_is_successful) {
       ++summary->num_successful_steps;
       strategy->StepAccepted(iteration_summary.relative_decrease);
+
       x = x_plus_delta;
       x_norm = x.norm();