三分探索

三分探索．二分探索じゃなくて三分探索．

二分探索は，単調関数の零点を求めるのに使われますが，
三分探索は，凸関数の極値を求めるのに使われます．

参考

実数探索三種類解説 - nodchipの日記
http://d.hatena.ne.jp/nodchip/20090303/1236058357

3分探索 - ICPC突破専用ザク
http://d.hatena.ne.jp/ir5/20090630/1246349028

fを上に凸な関数とします．
区間[a, b]を3等分して[a, c1], [c1, c2], [c2, b]の3つの区間をつくります．
この時，極大値は，上の3区間の内のどれかにあり，以下が成立します．

・極大値が[a, c1]にある(Fig.1)
⇒f(c1)>f(c2)が成立．b=c2とする．
・極大値が[c1, c2]にある(Fig.2)
⇒a=c1となってもb=c2となってもよい ．
・極大値が[c2, b]にある(Fig.3)
⇒f(c1)<f(c2)が成立．a=c1とする．



Fig.1


Fig.2


Fig.3

言い換えれば，
f(c1)>f(c2)⇒極大値は[a, c2]に存在
f(c1)<f(c2)⇒極大値は[c1, b]に存在

よって，各ステップ毎に探索空間を2/3にすることが出来ます．

これを実装すると下のようになります．

double search(double left, double right, int iteration){
  for(int i=0;i    if(f((left*2+right)/3)>f((left+right*2)/3))
      right=(left+right*2)/3;
    else
      left=(left*2+right)/3;
  }
  return (left+right)/2;
}

・例1
f(x)=x^-x
df/dx=(-ln(x)-1)x^-x
ですので，
df/dx=0
とおけば，
x=1/e≒0.367879441
となります．

結果:
初期値
[0, 4]
100回反復計算させた時の解
x=0.3678794519063162

・例2
鋸波
x-floor(x)
連続関数ですが，x∈Zの時は微分不可能であり極大値をとります．

結果:
初期値
[0, 4]
100回反復計算させた時の解
x=1.9999999999999996
上手く計算できたようです．

・例3
δ関数っぽいもの
δ関数は，
δ(x)=0 (x≠0)
δ(0)=∞
ですが，それっぽいものとして，

f(x)=0 (x≠0)
f(0)=1
に三分法を適用．

結果:
初期値
[-2, 2]
100回反復計算させた時の解
x=1.9999999999999996

駄目でした．連続で無いとやはり無理ですね．