三分探索を考えた

はじめに

凸関数（もしくは凹関数）の極値を求める三分探索という方法を学びました。

今回は、f(x)=x^2+2.3-5の極値を三分探索を使って求めることに挑戦します。

ちなみにグラフはこんな感じ。

関数部分

関数部分をfuncで準備します。
ためしに-5から5の範囲でxを振って出力してみます。

#include <bits/stdc++.h>
using namespace std;

double func(double x){
  double ans=pow(x,2)+(2.3)*x-5;
  return ans;
}

int main(){
  for(int i=-5;i<=5;i++){
    cout<<i<<"   "<<func(i)<<endl;
  }
  return 0;

}

出力

-5   8.5
-4   1.8
-3   -2.9
-2   -5.6
-1   -6.3
0   -5
1   -1.7
2   3.6
3   10.9
4   20.2
5   31.5

三分探索

三分探索は、探索する範囲を３等分してL（B）,1/3L（E）,2/3L（D）,R（C）の４つのポイントの大小関係から求める値を絞り込んでいきます。

LとRのうち凹関数の場合は1/3L（E) と2/3L（D)を比較して大きい方の外側（図ではDの方が大きいのでC）をとりのぞき、大きい方を新たなLまたは新たなRとして（図ではDを新たなRにする）、同様に三分探索を続けます。

LとRの差が十分に小さくなるか、繰り返し回数を適当な数（1000回）行ってLとRの距離が十分つまったところでつまった値を出力します。

実装

#include <bits/stdc++.h>
using namespace std;

double func(double x){
  double ans=pow(x,2)+(2.3)*x-5;
  return ans;
}

int main(){
  double left = -5;
  double right = 5;
  while(right-left>0.00000001) {
    double mid_l = left*2.0/3.0+right/3.0;
    double mid_r = left/3.0+right*2.0/3.0;
    if(func(mid_l)<func(mid_r)){
            right = mid_r;
        }else {
            left = mid_l;
        }
    }
  cout<<func(right)<<endl;
  return 0;
}
 

出力

-6.3225

検討

極値　-6.3225を求めることができました。

シンプルだけど実用性の高いアルゴリズムでいろいろと応用が効きそうです。