Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include "LineSearchMethod.h"
       4             : 
       5             : namespace elsa
       6             : {
       7             :     /**
       8             :      * @brief Strong Wolfe Condition
       9             :      *
      10             :      * StrongWolfeCondition is a line search method attempting to find a step size
      11             :      * @f$\alpha@f$ that satisfies the sufficient decrease and curvature condition while making sure
      12             :      * that the step size @f$\alpha@f$ is not too short using the following inequalities:
      13             :      *
      14             :      * @f[
      15             :      * f(x_i+\alpha d_i) \le f(x_i) + c_1 \alpha \nabla f_i^T d_i \\
      16             :      * |\nabla f(x_i + \alpha d_i)^T d_i| \le c_2 |\nabla f_i^T d_i|
      17             :      * @f]
      18             :      *
      19             :      * where @f$f: \mathbb{R}^n \to \mathbb{R}@f$ is differentiable,
      20             :      * @f$\nabla f_i: \mathbb{R}^n is the gradient of f at x_i@f$,
      21             :      * @f$ d_i: \mathbb{R}^n is the search direction @f$,
      22             :      * @f$ c1: is a constant affecting the sufficient decrease condition @f$, and
      23             :      * @f$ c: is a constant affecting the curvature condition@f$.
      24             :      *
      25             :      * References:
      26             :      * - See Wright and Nocedal, ‘Numerical Optimization’, 2nd Edition, 2006, pp. 33-36.
      27             :      *
      28             :      * @author
      29             :      * - Said Alghabra - initial code
      30             :      *
      31             :      * @tparam data_t data type for the domain and range of the problem, defaulting to real_t
      32             :      */
      33             :     template <typename data_t = real_t>
      34             :     class StrongWolfeCondition : public LineSearchMethod<data_t>
      35             :     {
      36             :     public:
      37             :         StrongWolfeCondition(const Functional<data_t>& problem, data_t amax = 10, data_t c1 = 1e-4,
      38             :                              data_t c2 = 0.9, index_t max_iterations = 10);
      39          40 :         ~StrongWolfeCondition() override = default;
      40             :         data_t solve(DataContainer<data_t> xi, DataContainer<data_t> di) override;
      41             : 
      42             :         /// implement the polymorphic comparison operation
      43             :         bool isEqual(const LineSearchMethod<data_t>& other) const override;
      44             : 
      45             :     private:
      46             :         // largest allowed step size
      47             :         data_t _amax;
      48             : 
      49             :         // parameter affecting the sufficient decrease condition
      50             :         data_t _c1;
      51             : 
      52             :         // parameter affecting the curvature condition
      53             :         data_t _c2;
      54             :         data_t _zoom(data_t a_lo, data_t a_hi, data_t f_lo, data_t f_hi, data_t f0, data_t der_f_lo,
      55             :                      data_t der_f0, const DataContainer<data_t>& xi,
      56             :                      const DataContainer<data_t>& di, index_t max_iterations = 10);
      57             : 
      58             :         /// implement the polymorphic clone operation
      59             :         StrongWolfeCondition<data_t>* cloneImpl() const override;
      60             :     };
      61             : } // namespace elsa