diff --git a/internal/ceres/line_search_minimizer.cc b/internal/ceres/line_search_minimizer.cc
index 339d275..977fd6c 100644
--- a/internal/ceres/line_search_minimizer.cc
+++ b/internal/ceres/line_search_minimizer.cc
@@ -74,18 +74,29 @@
 // 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;
   }
 
-  return status;
+  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;
+  }
+
+  state->gradient_squared_norm = (x - projected_gradient_step).squaredNorm();
+  state->gradient_max_norm = (x - projected_gradient_step).lpNorm<Eigen::Infinity>();
+  return true;
 }
 
 }  // namespace
@@ -125,10 +136,9 @@
   iteration_summary.step_solver_time_in_seconds = 0;
 
   // Do initial cost and Jacobian evaluation.
-  if (!Evaluate(evaluator, x, &current_state)) {
-    summary->message = "Terminating: Cost and gradient evaluation failed.";
+  if (!Evaluate(evaluator, x, &current_state, &summary->message)) {
     summary->termination_type = FAILURE;
-    LOG_IF(WARNING, is_not_silent) << summary->message;
+    LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message;
     return;
   }
 
@@ -138,22 +148,13 @@
   iteration_summary.gradient_max_norm = current_state.gradient_max_norm;
   iteration_summary.gradient_norm = sqrt(current_state.gradient_squared_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->message =
-        StringPrintf("Terminating: Gradient tolerance reached. "
-                     "Relative gradient max norm: %e <= %e",
-                     iteration_summary.gradient_max_norm /
-                     initial_gradient_max_norm,
-                     options.gradient_tolerance);
+  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) << summary->message;
+    VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
     return;
   }
 
@@ -210,23 +211,23 @@
 
   while (true) {
     if (!RunCallbacks(options.callbacks, iteration_summary, summary)) {
-      return;
+      break;
     }
 
     iteration_start_time = WallTimeInSeconds();
     if (iteration_summary.iteration >= options.max_num_iterations) {
-      summary->message = "Terminating: Maximum number of iterations reached.";
+      summary->message = "Maximum number of iterations reached.";
       summary->termination_type = NO_CONVERGENCE;
-      VLOG_IF(1, is_not_silent) << summary->message;
+      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 = "Terminating: Maximum solver time reached.";
+      summary->message = "Maximum solver time reached.";
       summary->termination_type = NO_CONVERGENCE;
-      VLOG_IF(1, is_not_silent) << summary->message;
+      VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
       break;
     }
 
@@ -252,11 +253,11 @@
       // have already reached our specified maximum number of restarts,
       // terminate optimization.
       summary->message =
-          StringPrintf("Terminating: Line search direction failure: specified "
+          StringPrintf("Line search direction failure: specified "
                        "max_num_line_search_direction_restarts: %d reached.",
                        options.max_num_line_search_direction_restarts);
       summary->termination_type = FAILURE;
-      LOG_IF(WARNING, is_not_silent) << summary->message;
+      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
@@ -345,8 +346,12 @@
     if (!evaluator->Plus(x.data(), delta.data(), x_plus_delta.data())) {
       LOG_IF(WARNING, is_not_silent)
           << "x_plus_delta = Plus(x, delta) failed. ";
-    } else if (!Evaluate(evaluator, x_plus_delta, &current_state)) {
-      LOG_IF(WARNING, is_not_silent) << "Step failed to evaluate. ";
+    } else if (!Evaluate(evaluator,
+                         x_plus_delta,
+                         &current_state,
+                         &summary->message)) {
+      LOG_IF(WARNING, is_not_silent) << "Step failed to evaluate. "
+                                     << summary->message;
     } else {
       x = x_plus_delta;
     }
@@ -354,15 +359,13 @@
     iteration_summary.gradient_max_norm = current_state.gradient_max_norm;
     iteration_summary.gradient_norm = sqrt(current_state.gradient_squared_norm);
 
-    if (iteration_summary.gradient_max_norm <= absolute_gradient_tolerance) {
-      summary->message =
-          StringPrintf("Terminating: Gradient tolerance reached. "
-                       "Relative gradient max norm: %e <= %e. ",
-                       (iteration_summary.gradient_max_norm /
-                        initial_gradient_max_norm),
-                       options.gradient_tolerance);
+    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) << summary->message;
+      VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
       break;
     }
 
@@ -371,14 +374,14 @@
         options.function_tolerance * previous_state.cost;
     if (fabs(iteration_summary.cost_change) < absolute_function_tolerance) {
       summary->message =
-          StringPrintf("Terminating. Function tolerance reached. "
+          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) << summary->message;
-      return;
+      VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
+      break;
     }
 
     iteration_summary.cost = current_state.cost + summary->fixed_cost;
diff --git a/internal/ceres/solver.cc b/internal/ceres/solver.cc
index da87de1..36c58b3 100644
--- a/internal/ceres/solver.cc
+++ b/internal/ceres/solver.cc
@@ -344,8 +344,8 @@
   StringAppendF(&report, "Total               %25.3f\n\n",
                 total_time_in_seconds);
 
-  StringAppendF(&report, "Termination:        %25s\n",
-                TerminationTypeToString(termination_type));
+  StringAppendF(&report, "Termination:        %25s (%s)\n",
+                TerminationTypeToString(termination_type), message.c_str());
   return report;
 };
 
diff --git a/internal/ceres/trust_region_minimizer.cc b/internal/ceres/trust_region_minimizer.cc
index f8ecac2..51eb75f 100644
--- a/internal/ceres/trust_region_minimizer.cc
+++ b/internal/ceres/trust_region_minimizer.cc
@@ -152,6 +152,8 @@
   Vector gradient(num_effective_parameters);
   Vector model_residuals(num_residuals);
   Vector scale(num_effective_parameters);
+  Vector negative_gradient(num_effective_parameters);
+  Vector projected_gradient_step(num_parameters);
 
   IterationSummary iteration_summary;
   iteration_summary.iteration = 0;
@@ -197,36 +199,39 @@
     return;
   }
 
-  int num_consecutive_nonmonotonic_steps = 0;
-  double minimum_cost = cost;
-  double reference_cost = cost;
-  double accumulated_reference_model_cost_change = 0.0;
-  double candidate_cost = cost;
-  double accumulated_candidate_model_cost_change = 0.0;
+  negative_gradient = -gradient;
+  if (!evaluator->Plus(x.data(),
+                       negative_gradient.data(),
+                       projected_gradient_step.data())) {
+    summary->message = "Unable to compute gradient step.";
+    summary->termination_type = FAILURE;
+    LOG(ERROR) << "Terminating: " << summary->message;
+    return;
+  }
 
   summary->initial_cost = cost + summary->fixed_cost;
   iteration_summary.cost = cost + summary->fixed_cost;
-  iteration_summary.gradient_max_norm = gradient.lpNorm<Eigen::Infinity>();
-  iteration_summary.gradient_norm = gradient.norm();
+  iteration_summary.gradient_max_norm =
+    (x - projected_gradient_step).lpNorm<Eigen::Infinity>();
+  iteration_summary.gradient_norm = (x - projected_gradient_step).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->message = StringPrintf("Terminating: Gradient tolerance reached. "
-                                  "Relative gradient max norm: %e <= %e",
-                                  (iteration_summary.gradient_max_norm /
-                                   initial_gradient_max_norm),
-                                  options_.gradient_tolerance);
+  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) << summary->message;
+    VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
     return;
   }
 
+  if (options_.jacobi_scaling) {
+    EstimateScale(*jacobian, scale.data());
+    jacobian->ScaleColumns(scale.data());
+  } else {
+    scale.setOnes();
+  }
+
   iteration_summary.iteration_time_in_seconds =
       WallTimeInSeconds() - iteration_start_time;
   iteration_summary.cumulative_time_in_seconds =
@@ -234,13 +239,12 @@
       + summary->preprocessor_time_in_seconds;
   summary->iterations.push_back(iteration_summary);
 
-  if (options_.jacobi_scaling) {
-    EstimateScale(*jacobian, scale.data());
-    jacobian->ScaleColumns(scale.data());
-  } else {
-    scale.setOnes();
-  }
-
+  int num_consecutive_nonmonotonic_steps = 0;
+  double minimum_cost = cost;
+  double reference_cost = cost;
+  double accumulated_reference_model_cost_change = 0.0;
+  double candidate_cost = cost;
+  double accumulated_candidate_model_cost_change = 0.0;
   int num_consecutive_invalid_steps = 0;
   bool inner_iterations_are_enabled = options.inner_iteration_minimizer != NULL;
   while (true) {
@@ -251,18 +255,18 @@
 
     iteration_start_time = WallTimeInSeconds();
     if (iteration_summary.iteration >= options_.max_num_iterations) {
-      summary->message = "Terminating: Maximum number of iterations reached.";
+      summary->message = "Maximum number of iterations reached.";
       summary->termination_type = NO_CONVERGENCE;
-      VLOG_IF(1, is_not_silent) << summary->message;
+      VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
       return;
     }
 
     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 = "Terminating: Maximum solver time reached.";
+      summary->message = "Maximum solver time reached.";
       summary->termination_type = NO_CONVERGENCE;
-      VLOG_IF(1, is_not_silent) << summary->message;
+      VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
       return;
     }
 
@@ -292,10 +296,10 @@
 
     if (strategy_summary.termination_type == LINEAR_SOLVER_FATAL_ERROR) {
       summary->message =
-          "Terminating. Linear solver failed due to unrecoverable "
+          "Linear solver failed due to unrecoverable "
           "non-numeric causes. Please see the error log for clues. ";
       summary->termination_type = FAILURE;
-      LOG_IF(WARNING, is_not_silent) << summary->message;
+      LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message;
       return;
     }
 
@@ -339,11 +343,11 @@
       if (++num_consecutive_invalid_steps >=
           options_.max_num_consecutive_invalid_steps) {
         summary->message = StringPrintf(
-            "Terminating. Number of successive invalid steps more "
+            "Number of successive invalid steps more "
             "than Solver::Options::max_num_consecutive_invalid_steps: %d",
             options_.max_num_consecutive_invalid_steps);
         summary->termination_type = FAILURE;
-        LOG_IF(WARNING, is_not_silent) << summary->message;
+        LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message;
         return;
       }
 
@@ -448,13 +452,13 @@
           (x_norm + options_.parameter_tolerance);
       if (iteration_summary.step_norm <= step_size_tolerance) {
         summary->message =
-            StringPrintf("Terminating. Parameter tolerance reached. "
-                         "relative step_norm: %e <= %e.",
+            StringPrintf("Parameter tolerance reached. "
+                         "Relative step_norm: %e <= %e.",
                          (iteration_summary.step_norm /
                           (x_norm + options_.parameter_tolerance)),
                          options_.parameter_tolerance);
         summary->termination_type = CONVERGENCE;
-        VLOG_IF(1, is_not_silent) << summary->message;
+        VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
         return;
       }
 
@@ -463,12 +467,12 @@
           options_.function_tolerance * cost;
       if (fabs(iteration_summary.cost_change) < absolute_function_tolerance) {
         summary->message =
-            StringPrintf("Terminating. Function tolerance reached. "
+            StringPrintf("Function tolerance reached. "
                          "|cost_change|/cost: %e <= %e",
                          fabs(iteration_summary.cost_change) / cost,
                          options_.function_tolerance);
         summary->termination_type = CONVERGENCE;
-        VLOG_IF(1, is_not_silent) << summary->message;
+        VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
         return;
       }
 
@@ -565,25 +569,34 @@
                                residuals.data(),
                                gradient.data(),
                                jacobian)) {
-        summary->message =
-            "Terminating: Residual and Jacobian evaluation failed.";
+        summary->message = "Residual and Jacobian evaluation failed.";
         summary->termination_type = FAILURE;
-        LOG_IF(WARNING, is_not_silent) << summary->message;
+        LOG_IF(WARNING, is_not_silent) << "Terminating: " << summary->message;
         return;
       }
 
-      iteration_summary.gradient_max_norm = gradient.lpNorm<Eigen::Infinity>();
-      iteration_summary.gradient_norm = gradient.norm();
-
-      if (iteration_summary.gradient_max_norm <= absolute_gradient_tolerance) {
+      negative_gradient = -gradient;
+      if (!evaluator->Plus(x.data(),
+                           negative_gradient.data(),
+                           projected_gradient_step.data())) {
         summary->message =
-            StringPrintf("Terminating: Gradient tolerance reached. "
-                         "Relative gradient max norm: %e <= %e",
-                         (iteration_summary.gradient_max_norm /
-                          initial_gradient_max_norm),
-                         options_.gradient_tolerance);
+            "projected_gradient_step = Plus(x, -gradient) failed.";
+        summary->termination_type = FAILURE;
+        LOG(ERROR) << "Terminating: " << summary->message;
+        return;
+      }
+
+      iteration_summary.gradient_max_norm =
+        (x - projected_gradient_step).lpNorm<Eigen::Infinity>();
+      iteration_summary.gradient_norm = (x - projected_gradient_step).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) << summary->message;
+        VLOG_IF(1, is_not_silent) << "Terminating: " << summary->message;
         return;
       }