Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <memory>
       4             : 
       5             : #include "Solver.h"
       6             : #include "Problem.h"
       7             : #include "DataContainer.h"
       8             : 
       9             : namespace elsa
      10             : {
      11             :     /**
      12             :      * @brief Class implementing Nesterov's Fast Gradient Method.
      13             :      *
      14             :      * This class implements Nesterov's Fast Gradient Method. FGM is a first order method to
      15             :      * efficiently optimize convex functions with Lipschitz-Continuous gradients.
      16             :      *
      17             :      * @details
      18             :      * # Nesterov's fast gradient method algorithm overview #
      19             :      * The algorithm repeats the following update steps for \f$i = 0, \dots, N-1\f$
      20             :      * \f{align*}{
      21             :      * y_{i+1} &= x_i - \frac{1}{L} f'(x_i) \\
      22             :      * t_{i+1} &= \frac{1 + \sqrt{1 + 4 t^2_i}}{2} \\
      23             :      * x_{i+1} &= y_{i} + \frac{t_i - 1}{t_{i+1}}(y_{i+1} - y_i)
      24             :      * \f}
      25             :      * The inputs are \f$f \in C_{L}^{1, 1}(\mathbb{R}^d)\f$, \f$x_0 \in \mathbb{R}^d\f$,
      26             :      * \f$y_0 = x_0\f$, \f$t_0 = 1\f$
      27             :      *
      28             :      * The presented (and also implemented) version of the algorithm corresponds to _FGM1_ in the
      29             :      * referenced paper.
      30             :      *
      31             :      * ## Convergence ##
      32             :      * Compared to the standard gradient descent, which has a convergence rate of
      33             :      * \f$\mathcal{O}(\frac{1}{N})\f$, the Nesterov's gradient method boots the convergence rate to
      34             :      * \f$\mathcal{O}(\frac{1}{N}^2)\f$
      35             :      *
      36             :      * In the current implementation, no particular stopping rule is implemented, only a fixed
      37             :      * number of iterations is used.
      38             :      *
      39             :      * ## FGM References ##
      40             :      * - Kim, D., Fessler, J.A. _Optimized first-order methods for smooth convex minimization_
      41             :      (2016) https://doi.org/10.1007/s10107-015-0949-3
      42             :      *
      43             :      * @tparam data_t data type for the domain and range of the problem, defaulting to real_t
      44             :      *
      45             :      * @see \verbatim embed:rst
      46             :      For a basic introduction and problem statement of first-order methods, see
      47             :      :ref:`here <elsa-first-order-methods-doc>` \endverbatim
      48             :      *
      49             :      * @author
      50             :      * - Michael Loipführer - initial code
      51             :      * - David Frank - Detailed Documentation
      52             :      */
      53             :     template <typename data_t = real_t>
      54             :     class FGM : public Solver<data_t>
      55             :     {
      56             :     public:
      57             :         /// Scalar alias
      58             :         using Scalar = typename Solver<data_t>::Scalar;
      59             : 
      60             :         /**
      61             :          * @brief Constructor for FGM, accepting an optimization problem and, optionally, a value
      62             :          * for epsilon
      63             :          *
      64             :          * @param[in] problem the problem that is supposed to be solved
      65             :          * @param[in] epsilon affects the stopping condition
      66             :          */
      67             :         FGM(const Problem<data_t>& problem,
      68             :             data_t epsilon = std::numeric_limits<data_t>::epsilon());
      69             : 
      70             :         /**
      71             :          * @brief Constructor for FGM, accepting an optimization problem, the inverse of a
      72             :          * preconditioner and, optionally, a value for epsilon
      73             :          *
      74             :          * @param[in] problem the problem that is supposed to be solved
      75             :          * @param[in] preconditionerInverse the inverse of the preconditioner
      76             :          * @param[in] epsilon affects the stopping condition
      77             :          */
      78             :         FGM(const Problem<data_t>& problem, const LinearOperator<data_t>& preconditionerInverse,
      79             :             data_t epsilon = std::numeric_limits<data_t>::epsilon());
      80             : 
      81             :         /// make copy constructor deletion explicit
      82             :         FGM(const FGM<data_t>&) = delete;
      83             : 
      84             :         /// default destructor
      85          18 :         ~FGM() override = default;
      86             : 
      87             :     private:
      88             :         /// the differentiable optimizaion problem
      89             :         std::unique_ptr<Problem<data_t>> _problem;
      90             : 
      91             :         /// the default number of iterations
      92             :         const index_t _defaultIterations{100};
      93             : 
      94             :         /// variable affecting the stopping condition
      95             :         data_t _epsilon;
      96             : 
      97             :         /// the inverse of the preconditioner (if supplied)
      98             :         std::unique_ptr<LinearOperator<data_t>> _preconditionerInverse{};
      99             : 
     100             :         /**
     101             :          * @brief Solve the optimization problem, i.e. apply iterations number of iterations of
     102             :          * gradient descent
     103             :          *
     104             :          * @param[in] iterations number of iterations to execute (the default 0 value executes
     105             :          * _defaultIterations of iterations)
     106             :          *
     107             :          * @returns a reference to the current solution
     108             :          */
     109             :         DataContainer<data_t>& solveImpl(index_t iterations) override;
     110             : 
     111             :         /// implement the polymorphic clone operation
     112             :         FGM<data_t>* cloneImpl() const override;
     113             : 
     114             :         /// implement the polymorphic comparison operation
     115             :         bool isEqual(const Solver<data_t>& other) const override;
     116             :     };
     117             : } // namespace elsa