OGM.h 4.31 KB
Newer Older
1
2
3
4
5
6
7
#pragma once

#include "Solver.h"

namespace elsa
{
    /**
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.
     *
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 <elsa-first-order-methods-doc>` \endverbatim
44
     *
45
46
47
     * @author
     * - Michael Loipführer - initial code
     * - David Frank - Detailed Documentation
48
49
50
51
52
     */
    template <typename data_t = real_t>
    class OGM : public Solver<data_t>
    {
    public:
53
54
55
        /// Scalar alias
        using Scalar = typename Solver<data_t>::Scalar;

56
        /**
57
         * @brief Constructor for OGM, accepting an optimization problem and, optionally, a value
58
59
         * for epsilon
         *
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<data_t>& problem,
            data_t epsilon = std::numeric_limits<data_t>::epsilon());

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<data_t>& problem, const LinearOperator<data_t>& preconditionerInverse,
            data_t epsilon = std::numeric_limits<data_t>::epsilon());

77
78
79
80
81
82
        /// make copy constructor deletion explicit
        OGM(const OGM<data_t>&) = delete;

        /// default destructor
        ~OGM() override = default;

83
84
85
        /// lift the base class method getCurrentSolution
        using Solver<data_t>::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;

93
94
95
        /// the inverse of the preconditioner (if supplied)
        std::unique_ptr<LinearOperator<data_t>> _preconditionerInverse{};

96
97
98
99
        /// lift the base class variable _problem
        using Solver<data_t>::_problem;

        /**
100
         * @brief Solve the optimization problem, i.e. apply iterations number of iterations of
101
102
         * gradient descent
         *
103
         * @param[in] iterations number of iterations to execute (the default 0 value executes
104
105
         * _defaultIterations of iterations)
         *
106
         * @returns a reference to the current solution
107
108
109
110
111
112
113
114
115
116
         */
        DataContainer<data_t>& solveImpl(index_t iterations) override;

        /// implement the polymorphic clone operation
        OGM<data_t>* cloneImpl() const override;

        /// implement the polymorphic comparison operation
        bool isEqual(const Solver<data_t>& other) const override;
    };
} // namespace elsa