黄金分割探索 (Golden-section search) (src/algorithm/GoldenSearch.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2026-07-29 23:40:35+09:00
Include: #include "src/algorithm/GoldenSearch.hpp"

使い方

pair<double, T> golden(double l, double r, function<T(double)> f)：閉区間 $[l, r]$ 上の連続関数 $f(x)$ の達成する $a$ と極大値 $f(a)$ の組を返す．
- $f$ が $[l, a]$ 上で狭義単調増加，$[a, r]$ 上で狭義単調減少であれば，最大値 $(a, f(a))$ が求まる．
最小値を求める場合は，fl < fr の代わりに fl > fr と書けば良い．

精度

$80$ 回反復すると $f$ が $81$ 回評価され，探索区間の幅は $\phi^{80} \approx 5.2 \times 10^{16}$ 倍に縮小する．

Verified with

test/algorithm/GoldenSearch.test.cpp

Code

// return {argmax, max}
// f は [l, r] 上で上に単峰であること
auto golden(double l, double r, auto f) {
   const double p = numbers::phi - 1;
   double r2 = lerp(l, r, p);
   auto fr = f(r2);
   rep(i, 0, 80) {  // phi^80 = 5e16
      double l2 = lerp(r, l, p);
      auto fl = f(l2);
      // maximize
      if(fl < fr) l = r, r = l2;
      else r = r2, r2 = l2, fr = fl;
   }
   return pair{r2, fr};
}

#line 1 "src/algorithm/GoldenSearch.hpp"
// return {argmax, max}
// f は [l, r] 上で上に単峰であること
auto golden(double l, double r, auto f) {
    const double p = numbers::phi - 1;
    double r2 = lerp(l, r, p);
    auto fr = f(r2);
    rep(i, 0, 80) {  // phi^80 = 5e16
        double l2 = lerp(r, l, p);
        auto fl = f(l2);
        // maximize
        if (fl < fr) l = r, r = l2; 
        else r = r2, r2 = l2, fr = fl;
    }
    return pair{r2, fr};
}