Home | History | Annotate | Download | only in ceres
      1 // Ceres Solver - A fast non-linear least squares minimizer
      2 // Copyright 2012 Google Inc. All rights reserved.
      3 // http://code.google.com/p/ceres-solver/
      4 //
      5 // Redistribution and use in source and binary forms, with or without
      6 // modification, are permitted provided that the following conditions are met:
      7 //
      8 // * Redistributions of source code must retain the above copyright notice,
      9 //   this list of conditions and the following disclaimer.
     10 // * Redistributions in binary form must reproduce the above copyright notice,
     11 //   this list of conditions and the following disclaimer in the documentation
     12 //   and/or other materials provided with the distribution.
     13 // * Neither the name of Google Inc. nor the names of its contributors may be
     14 //   used to endorse or promote products derived from this software without
     15 //   specific prior written permission.
     16 //
     17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
     18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
     21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     27 // POSSIBILITY OF SUCH DAMAGE.
     28 //
     29 // Author: sameeragarwal (at) google.com (Sameer Agarwal)
     30 //
     31 // Limited memory positive definite approximation to the inverse
     32 // Hessian, using the LBFGS algorithm
     33 
     34 #ifndef CERES_INTERNAL_LOW_RANK_INVERSE_HESSIAN_H_
     35 #define CERES_INTERNAL_LOW_RANK_INVERSE_HESSIAN_H_
     36 
     37 #include <list>
     38 
     39 #include "ceres/internal/eigen.h"
     40 #include "ceres/linear_operator.h"
     41 
     42 namespace ceres {
     43 namespace internal {
     44 
     45 // LowRankInverseHessian is a positive definite approximation to the
     46 // Hessian using the limited memory variant of the
     47 // Broyden-Fletcher-Goldfarb-Shanno (BFGS)secant formula for
     48 // approximating the Hessian.
     49 //
     50 // Other update rules like the Davidon-Fletcher-Powell (DFP) are
     51 // possible, but the BFGS rule is considered the best performing one.
     52 //
     53 // The limited memory variant was developed by Nocedal and further
     54 // enhanced with scaling rule by Byrd, Nocedal and Schanbel.
     55 //
     56 // Nocedal, J. (1980). "Updating Quasi-Newton Matrices with Limited
     57 // Storage". Mathematics of Computation 35 (151): 773782.
     58 //
     59 // Byrd, R. H.; Nocedal, J.; Schnabel, R. B. (1994).
     60 // "Representations of Quasi-Newton Matrices and their use in
     61 // Limited Memory Methods". Mathematical Programming 63 (4):
     62 class LowRankInverseHessian : public LinearOperator {
     63  public:
     64   // num_parameters is the row/column size of the Hessian.
     65   // max_num_corrections is the rank of the Hessian approximation.
     66   // use_approximate_eigenvalue_scaling controls whether the initial
     67   // inverse Hessian used during Right/LeftMultiply() is scaled by
     68   // the approximate eigenvalue of the true inverse Hessian at the
     69   // current operating point.
     70   // The approximation uses:
     71   // 2 * max_num_corrections * num_parameters + max_num_corrections
     72   // doubles.
     73   LowRankInverseHessian(int num_parameters,
     74                         int max_num_corrections,
     75                         bool use_approximate_eigenvalue_scaling);
     76   virtual ~LowRankInverseHessian() {}
     77 
     78   // Update the low rank approximation. delta_x is the change in the
     79   // domain of Hessian, and delta_gradient is the change in the
     80   // gradient.  The update copies the delta_x and delta_gradient
     81   // vectors, and gets rid of the oldest delta_x and delta_gradient
     82   // vectors if the number of corrections is already equal to
     83   // max_num_corrections.
     84   bool Update(const Vector& delta_x, const Vector& delta_gradient);
     85 
     86   // LinearOperator interface
     87   virtual void RightMultiply(const double* x, double* y) const;
     88   virtual void LeftMultiply(const double* x, double* y) const {
     89     RightMultiply(x, y);
     90   }
     91   virtual int num_rows() const { return num_parameters_; }
     92   virtual int num_cols() const { return num_parameters_; }
     93 
     94  private:
     95   const int num_parameters_;
     96   const int max_num_corrections_;
     97   const bool use_approximate_eigenvalue_scaling_;
     98   double approximate_eigenvalue_scale_;
     99   ColMajorMatrix delta_x_history_;
    100   ColMajorMatrix delta_gradient_history_;
    101   Vector delta_x_dot_delta_gradient_;
    102   std::list<int> indices_;
    103 };
    104 
    105 }  // namespace internal
    106 }  // namespace ceres
    107 
    108 #endif  // CERES_INTERNAL_LOW_RANK_INVERSE_HESSIAN_H_
    109