LBFGS.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief LBFGS
6  *
7  * The Limited-Memory Broyden, Fletcher, Goldfarb, Shannon (BFGS) algorithm
8  * is a quasi-Newton method for unconstrained real-valued optimization.
9  * See: http://en.wikipedia.org/wiki/LBFGS for details.
10  *
11  *
12  *
13  * \author S. Dahlgaard, O.Krause
14  * \date 2013
15  *
16  *
17  * \par Copyright 1995-2015 Shark Development Team
18  *
19  * <BR><HR>
20  * This file is part of Shark.
21  * <http://image.diku.dk/shark/>
22  *
23  * Shark is free software: you can redistribute it and/or modify
24  * it under the terms of the GNU Lesser General Public License as published
25  * by the Free Software Foundation, either version 3 of the License, or
26  * (at your option) any later version.
27  *
28  * Shark is distributed in the hope that it will be useful,
29  * but WITHOUT ANY WARRANTY; without even the implied warranty of
30  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31  * GNU Lesser General Public License for more details.
32  *
33  * You should have received a copy of the GNU Lesser General Public License
34  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
35  *
36  */
37 //===========================================================================
38 
39 
40 #ifndef SHARK_ML_OPTIMIZER_LBFGS_H
41 #define SHARK_ML_OPTIMIZER_LBFGS_H
42 
43 #include <shark/Core/DLLSupport.h>
45 #include <deque>
46 
47 namespace shark {
48 
49 //! \brief Limited-Memory Broyden, Fletcher, Goldfarb, Shannon algorithm for unconstrained optimization
51 protected:
54 public:
55  LBFGS() :m_numHist(100){}
56 
57  /// \brief From INameable: return the class name.
58  std::string name() const
59  { return "LBFGS"; }
60 
61  /// \brief Specify the amount of steps to be memorized and used to find the L-BFGS direction.
62  ///
63  ///\param numhist The amount of steps to use.
64  void setHistCount(unsigned int numhist) {
65  SHARK_CHECK(numhist > 0, "[LBFGS::setHistCount] An empty history is not allowed");
66  m_numHist = numhist;
67  }
68 
69  //from ISerializable
70  SHARK_EXPORT_SYMBOL void read(InArchive &archive);
71  SHARK_EXPORT_SYMBOL void write(OutArchive &archive) const;
72 protected: // Methods
73 
74  ///\brief Stores another step and searchDirection, discarding the oldest on if necessary.
75  ///
76  /// \param step Last performed step
77  /// \param y difference in gradients
78  SHARK_EXPORT_SYMBOL void updateHist(RealVector& y, RealVector &step);
79  /// \brief Get the LBFGS direction.
80  ///
81  /// This approximates the inverse hessian multiplied by the gradient.
82  /// This uses the rho, alpha and beta vectors. Description of these
83  /// can be seen in ie. the wiki page of LBFGS.
84  SHARK_EXPORT_SYMBOL void getDirection(RealVector& searchDirection);
85 
86 
87 protected: // Instance vars
88  double m_updThres;///<Threshold for when to update history.
89  unsigned int m_numHist; ///< Number of steps to use for LBFGS.
90  // Initial Hessian approximation. We use a diagonal matrix, where each element is
91  // the same, so we only need to store one double.
92  double m_hdiag;
93 
94  // Saved steps for creating the approximation.
95  // Use deque as it gives fast pop.front, push.back and access. Supposedly.
96  // steps holds the values x_(k+1) - x_k
97  // gradientDifferences holds the values g_(k+1) - g_k
98  std::deque<RealVector> m_steps;
99  std::deque<RealVector> m_gradientDifferences;
100 };
101 
102 }
103 #endif