blob: be4d40653c4bf186e8fb60f9b42d9eaffce81ab9 [file] [log] [blame]
// Ceres Solver - A fast non-linear least squares minimizer
// Copyright 2016 Google Inc. All rights reserved.
// http://ceres-solver.org/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
// * Neither the name of Google Inc. nor the names of its contributors may be
// used to endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//
// Author: sameeragarwal@google.com (Sameer Agarwal)
#ifndef CERES_INTERNAL_TRUST_REGION_MINIMIZER_H_
#define CERES_INTERNAL_TRUST_REGION_MINIMIZER_H_
#include <memory>
#include "ceres/internal/eigen.h"
#include "ceres/internal/port.h"
#include "ceres/minimizer.h"
#include "ceres/solver.h"
#include "ceres/sparse_matrix.h"
#include "ceres/trust_region_step_evaluator.h"
#include "ceres/trust_region_strategy.h"
#include "ceres/types.h"
namespace ceres {
namespace internal {
// Generic trust region minimization algorithm.
//
// For example usage, see SolverImpl::Minimize.
class CERES_EXPORT_INTERNAL TrustRegionMinimizer : public Minimizer {
public:
~TrustRegionMinimizer();
// This method is not thread safe.
void Minimize(const Minimizer::Options& options,
double* parameters,
Solver::Summary* solver_summary) override;
private:
void Init(const Minimizer::Options& options,
double* parameters,
Solver::Summary* solver_summary);
bool IterationZero();
bool FinalizeIterationAndCheckIfMinimizerCanContinue();
bool ComputeTrustRegionStep();
bool EvaluateGradientAndJacobian(bool new_evaluation_point);
void ComputeCandidatePointAndEvaluateCost();
void DoLineSearch(const Vector& x,
const Vector& gradient,
const double cost,
Vector* delta);
void DoInnerIterationsIfNeeded();
bool ParameterToleranceReached();
bool FunctionToleranceReached();
bool GradientToleranceReached();
bool MaxSolverTimeReached();
bool MaxSolverIterationsReached();
bool MinTrustRegionRadiusReached();
bool IsStepSuccessful();
bool HandleSuccessfulStep();
bool HandleInvalidStep();
Minimizer::Options options_;
// These pointers are shortcuts to objects passed to the
// TrustRegionMinimizer. The TrustRegionMinimizer does not own them.
double* parameters_;
Solver::Summary* solver_summary_;
Evaluator* evaluator_;
SparseMatrix* jacobian_;
TrustRegionStrategy* strategy_;
std::unique_ptr<TrustRegionStepEvaluator> step_evaluator_;
bool is_not_silent_;
bool inner_iterations_are_enabled_;
bool inner_iterations_were_useful_;
// Summary of the current iteration.
IterationSummary iteration_summary_;
// Dimensionality of the problem in the ambient space.
int num_parameters_;
// Dimensionality of the problem in the tangent space. This is the
// number of columns in the Jacobian.
int num_effective_parameters_;
// Length of the residual vector, also the number of rows in the Jacobian.
int num_residuals_;
// Current point.
Vector x_;
// Residuals at x_;
Vector residuals_;
// Gradient at x_.
Vector gradient_;
// Solution computed by the inner iterations.
Vector inner_iteration_x_;
// model_residuals = J * trust_region_step
Vector model_residuals_;
Vector negative_gradient_;
// projected_gradient_step = Plus(x, -gradient), an intermediate
// quantity used to compute the projected gradient norm.
Vector projected_gradient_step_;
// The step computed by the trust region strategy. If Jacobi scaling
// is enabled, this is a vector in the scaled space.
Vector trust_region_step_;
// The current proposal for how far the trust region algorithm
// thinks we should move. In the most basic case, it is just the
// trust_region_step_ with the Jacobi scaling undone. If bounds
// constraints are present, then it is the result of the projected
// line search.
Vector delta_;
// candidate_x = Plus(x, delta)
Vector candidate_x_;
// Scaling vector to scale the columns of the Jacobian.
Vector jacobian_scaling_;
// Euclidean norm of x_.
double x_norm_;
// Cost at x_.
double x_cost_;
// Minimum cost encountered up till now.
double minimum_cost_;
// How much did the trust region strategy reduce the cost of the
// linearized Gauss-Newton model.
double model_cost_change_;
// Cost at candidate_x_.
double candidate_cost_;
// Time at which the minimizer was started.
double start_time_in_secs_;
// Time at which the current iteration was started.
double iteration_start_time_in_secs_;
// Number of consecutive steps where the minimizer loop computed a
// numerically invalid step.
int num_consecutive_invalid_steps_;
};
} // namespace internal
} // namespace ceres
#endif // CERES_INTERNAL_TRUST_REGION_MINIMIZER_H_