golden_section_search.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 <cmath>
 
#include "num_collect/base/index_type.h"
#include "num_collect/logging/iterations/iteration_logger.h"
#include "num_collect/logging/log_tag_view.h"
#include "num_collect/opt/concepts/single_variate_objective_function.h"
#include "num_collect/opt/optimizer_base.h"
 
namespace num_collect::opt {
 
constexpr auto golden_section_search_tag =
    logging::log_tag_view("num_collect::opt::golden_section_search");
 
template <concepts::single_variate_objective_function ObjectiveFunction>
class golden_section_search
    : public optimizer_base<golden_section_search<ObjectiveFunction>> {
public:
    using this_type = golden_section_search<ObjectiveFunction>;
 
    using objective_function_type = ObjectiveFunction;
 
    using variable_type = typename objective_function_type::variable_type;
 
    using value_type = typename objective_function_type::value_type;
 
    explicit golden_section_search(
        const objective_function_type& obj_fun = objective_function_type())
        : optimizer_base<golden_section_search<ObjectiveFunction>>(
              golden_section_search_tag),
          obj_fun_(obj_fun) {}
 
    void change_objective_function(const objective_function_type& obj_fun) {
        obj_fun_ = obj_fun;
    }
 
    void init(variable_type end1, variable_type end2) {
        end1_ = end1;
        end2_ = end2;
 
        mid1_ = end1_ + (end2_ - end1_) * mid_point_ratio;
        obj_fun_.evaluate_on(mid1_);
        value1_ = obj_fun_.value();
 
        iterations_ = 0;
    }
 
    auto tol_section_len(variable_type value) -> golden_section_search& {
        tol_section_len_ = value;
        return *this;
    }
 
    void iterate() {
        const variable_type mid2 = end2_ + (end1_ - end2_) * mid_point_ratio;
        obj_fun_.evaluate_on(mid2);
        const value_type value2 = obj_fun_.value();
        if (value1_ < value2) {
            // (end1_, mid1_, end2_) = (mid2, mid1_, end1_)
            end2_ = end1_;
            end1_ = mid2;
        } else {
            // (end1_, mid1_, end2_) = (mid1_, mid2, end2_)
            end1_ = mid1_;
            mid1_ = mid2;
            value1_ = value2;
        }
        ++iterations_;
    }
 
    [[nodiscard]] auto is_stop_criteria_satisfied() const -> bool {
        return section_len() < tol_section_len_;
    }
 
    void configure_iteration_logger(
        logging::iterations::iteration_logger<this_type>& iteration_logger)
        const {
        iteration_logger.template append<index_type>(
            "Iter.", &this_type::iterations);
        iteration_logger.template append<index_type>(
            "Eval.", &this_type::evaluations);
        iteration_logger.template append<value_type>(
            "Value", &this_type::opt_value);
    }
 
    [[nodiscard]] auto opt_variable() const -> const variable_type& {
        return mid1_;
    }
 
    [[nodiscard]] auto opt_value() const -> const value_type& {
        return value1_;
    }
 
    [[nodiscard]] auto iterations() const noexcept -> index_type {
        return iterations_;
    }
 
    [[nodiscard]] auto evaluations() const noexcept -> index_type {
        return iterations_ + 1;
    }
 
    [[nodiscard]] auto section_len() const -> variable_type {
        using std::abs;
        return abs(end1_ - end2_);
    }
 
    static inline const auto mid_point_ratio =
        static_cast<variable_type>((3.0 - std::sqrt(5.0)) / 2.0);
 
    static inline const auto default_tol_section_len =
        static_cast<variable_type>(1e-3);
 
private:
    objective_function_type obj_fun_;
 
    variable_type end1_{};
 
    variable_type end2_{};
 
    variable_type mid1_{};
 
    value_type value1_{};
 
    index_type iterations_{0};
 
    variable_type tol_section_len_{default_tol_section_len};
};
 
}  // namespace num_collect::opt