Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <optional>
       4             : 
       5             : #include "Solver.h"
       6             : #include "Functional.h"
       7             : #include "LineSearchMethod.h"
       8             : 
       9             : namespace elsa
      10             : {
      11             :     /**
      12             :      * @brief BFGS solver
      13             :      *
      14             :      * Broyden–Fletcher–Goldfarb–Shanno (BFGS) is a quasi-Newton iterative optimization algorithm
      15             :      * for non-linear problems.
      16             :      * BFGS minimizes an objective function @f$f@f$ by first constructing an
      17             :      * approximation of it as:
      18             :      * @f[
      19             :      * m(d) = f(x_i) + \nablaf_i^T d + frac{1}{2}d^T H^{-1}_i d
      20             :      * @f]
      21             :      *
      22             :      * where @f$f: \mathbb{R}^n \to \mathbb{R}@f$ is differentiable,
      23             :      * @f$\nabla f_i: \mathbb{R}^n is the gradient of f at x_i@f$,
      24             :      * @f$ d: \mathbb{R}^n is a search direction @f$,
      25             :      * @f$ H^{-1}_i: \mathbb{R}^{n \times n} is an approximation of the Hessian \nabla^2 f(x_i) @f$
      26             :      *
      27             :      * The search direction @f$d@f$ that minimizes the approximation @f$m(d)@f$ is
      28             :      * analytically found to be @f$d_i = H_i \nabla f_i@f$.
      29             :      *
      30             :      * @f$H_i@f$ is calculated by the following formula:
      31             :      *
      32             :      * @f[
      33             :      * H_{i+1} = (I - \rho_i s_i y_i^T) H_i (I - \rho y_i s_i^T) + \rho s_i s_i^T
      34             :      * @f]
      35             :      *
      36             :      * where:
      37             :      * @f$ H^_i: \mathbb{R}^{n \times n} is an approximation of the inverse Hessian
      38             :      * (\nabla^2f(x_i))^{-1}@f$
      39             :      * @f$I: \mathbb{R}^{n \times \n} is identity matrix@f$,
      40             :      * @f$ \rho_i: frac{1}{y_i^T s_i}@f$,
      41             :      * @f$ s_i: \mathbb{R}^{n} = x_{i+1} - x_i  @f$, and
      42             :      * @f$ y_i: \mathbb{R}^{n} = \nabla f_{i+1} - \nabla f_i  @f$
      43             :      *
      44             :      * References:
      45             :      * - See Wright and Nocedal, ‘Numerical Optimization’, 2nd Edition, 2006, pp. 136-145.
      46             :      *
      47             :      * @author
      48             :      * - Said Alghabra - initial code
      49             :      *
      50             :      * @tparam data_t data type for the domain and range of the problem, defaulting to real_t
      51             :      */
      52             :     template <typename data_t = real_t>
      53             :     class BFGS : public Solver<data_t>
      54             :     {
      55             :     public:
      56             :         /// Scalar alias
      57             :         using Scalar = typename Solver<data_t>::Scalar;
      58             : 
      59             :         BFGS(const Functional<data_t>& problem, const LineSearchMethod<data_t>& line_search_method,
      60             :              const data_t& tol = 1e-4);
      61             : 
      62             :         /// make copy constructor deletion explicit
      63             :         BFGS(const BFGS<data_t>&) = delete;
      64             : 
      65             :         /// default destructor
      66          10 :         ~BFGS() override = default;
      67             : 
      68             :         DataContainer<data_t>
      69             :             solve(index_t iterations,
      70             :                   std::optional<DataContainer<data_t>> x0 = std::nullopt) override;
      71             : 
      72             :     private:
      73             :         /// the differentiable optimizaion problem
      74             :         std::unique_ptr<Functional<data_t>> _problem;
      75             : 
      76             :         /// the line search method
      77             :         // TODO: maybe change this to be only strong wolfe?
      78             :         std::unique_ptr<LineSearchMethod<data_t>> _ls;
      79             : 
      80             :         /// the step size
      81             :         data_t _tol;
      82             : 
      83             :         /// implement the polymorphic clone operation
      84             :         BFGS<data_t>* cloneImpl() const override;
      85             : 
      86             :         /// implement the polymorphic comparison operation
      87             :         bool isEqual(const Solver<data_t>& other) const override;
      88             :     };
      89             : } // namespace elsa