backtracking_line_searcher.h

Go to the documentation of this file.

/*
 * Copyright 2021 MusicScience37 (Kenta Kabashima)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#pragma once
 
#include <type_traits>  // IWYU pragma: keep
 
#include "num_collect/base/exception.h"
#include "num_collect/base/index_type.h"
#include "num_collect/base/precondition.h"
#include "num_collect/logging/logging_macros.h"
#include "num_collect/opt/concepts/differentiable_objective_function.h"
#include "num_collect/opt/concepts/multi_variate_differentiable_objective_function.h"
 
namespace num_collect::opt {
 
template <concepts::differentiable_objective_function ObjectiveFunction>
class backtracking_line_searcher;
 
template <
    concepts::multi_variate_differentiable_objective_function ObjectiveFunction>
class backtracking_line_searcher<ObjectiveFunction> {
public:
    using objective_function_type = ObjectiveFunction;
 
    using variable_type = typename objective_function_type::variable_type;
 
    using value_type = typename objective_function_type::value_type;
 
    static_assert(std::is_same_v<typename variable_type::Scalar, value_type>,
        "This class assumes that scalars in Eigen::Matrix class is same as "
        "value_type");
 
    explicit backtracking_line_searcher(
        const objective_function_type& obj_fun = objective_function_type())
        : obj_fun_(obj_fun) {}
 
    void init(const variable_type& init_variable) {
        variable_ = init_variable;
        obj_fun_.evaluate_on(variable_);
        evaluations_ = 1;
    }
 
    void search(const variable_type& direction) {
        step_ = init_step;
 
        const variable_type prev_var = variable_;
        const value_type prev_value = obj_fun_.value();
        const value_type step_coeff =
            armijo_coeff_ * obj_fun_.gradient().dot(direction);
 
        // prevent infinite loops
        constexpr index_type max_loops = 1000;
        for (index_type i = 0; i < max_loops; ++i) {
            variable_ = prev_var + step_ * direction;
            obj_fun_.evaluate_on(variable_);
            ++evaluations_;
            if (obj_fun_.value() <= prev_value + step_ * step_coeff) {
                return;
            }
            step_ *= step_scale_;
        }
 
        NUM_COLLECT_LOG_AND_THROW(
            algorithm_failure, "failed to search step size");
    }
 
    [[nodiscard]] auto obj_fun() -> objective_function_type& {
        return obj_fun_;
    }
 
    [[nodiscard]] auto obj_fun() const -> const objective_function_type& {
        return obj_fun_;
    }
 
    [[nodiscard]] auto opt_variable() const -> const variable_type& {
        return variable_;
    }
 
    [[nodiscard]] auto opt_value() const -> const value_type& {
        return obj_fun_.value();
    }
 
    [[nodiscard]] auto gradient() const -> const variable_type& {
        return obj_fun_.gradient();
    }
 
    [[nodiscard]] auto evaluations() const -> index_type {
        return evaluations_;
    }
 
    [[nodiscard]] auto last_step() const -> value_type { return step_; }
 
    auto armijo_coeff(value_type value) -> backtracking_line_searcher& {
        NUM_COLLECT_PRECONDITION(static_cast<value_type>(0) < value &&
                value < static_cast<value_type>(1),
            "Coefficient in Armijo rule must be in the range (0, 1).");
        armijo_coeff_ = value;
        return *this;
    }
 
    auto step_scale(value_type value) -> backtracking_line_searcher& {
        NUM_COLLECT_PRECONDITION(static_cast<value_type>(0) < value &&
                value < static_cast<value_type>(1),
            "Ratio to scale step sizes must be in the range (0, 1).");
        step_scale_ = value;
        return *this;
    }
 
private:
    objective_function_type obj_fun_;
 
    variable_type variable_{};
 
    static inline const auto init_step = static_cast<value_type>(1.0);
 
    value_type step_{init_step};
 
    static inline const auto default_armijo_coeff =
        static_cast<value_type>(0.1);
 
    value_type armijo_coeff_{default_armijo_coeff};
 
    static inline const auto default_step_scale = static_cast<value_type>(0.5);
 
    value_type step_scale_{default_step_scale};
 
    index_type evaluations_{0};
};
 
}  // namespace num_collect::opt