internal/ceres/low_rank_inverse_hessian.h

   1 // Ceres Solver - A fast non-linear least squares minimizer
   2 // Copyright 2015 Google Inc. All rights reserved.
   3 // http://ceres-solver.org/
   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@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): 773–782.
  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_