Line data    Source code

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