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