3分探索
凸関数の極値を求める方法を知りたくなってググってみたところid:nodchipさんのエントリがヒットした．
以下，個人的なまとめ．
実数探索三種類解説 - nodchipの日記
http://d.hatena.ne.jp/nodchip/20090303/1236058357
単調関数の零点を求めるのには2分探索が使われるけど，凸関数の極値を求めるのには3分探索が使われるらしい．
三分探索は凸関数の極値を求めるために使うアルゴリズムです。このアルゴリズムは関数が微分不可能な場合にも使えます。やり方は探索領域を三分割し、真ん中二本の境界のうちどちらの値が大きいかを調べ、それとは逆の方の境界を新たな探索領域の端にするというものです。一回のイテレーションで関数の計算を2回行い、探索領域が2/3になります。
3分探索がうまくいく理由は以下のとおり．
f : [a,b]→R : 上に凸な関数とし，区間[a,b]を3等分して[a,c1],[c1,c2],[c2,b]の3つの区間が出来た場合，
- 極値が[a,c1]にあるならばf(c1)>f(c2)が，成り立つのでb=c2がとられる
- 極値が[c1,c2]にあるならばa=c1となってもb=c2となってもよい
- 極値が[c2,b]にあるならばf(c1)
以上より，探索領域[a,b]は常に極値を持ったまま，幅が2/3ずつ狭まっていく．
黄金分割探索
このとき，単純に3等分するのではなく比を黄金比(=)で分割するといい事があるらしい．
黄金分割探索は三分探索と同様に凸関数の極値を求めるために使うアルゴリズムです。領域の分割を黄金比によって再帰的に行うため、前回のイテレーションでの値を再利用することができ、高速化することができます。1回のイテレーションで関数の計算を1回行い、探索領域が約0.618倍になります。
黄金比で分割することによって直前の値を再利用できるようになる＋探索領域が若干狭くなるらしい．すごい．
実際，として図を描いてみると，
まず区間をφ:1，1:φに内分する点c1,c2をそれぞれ取ると
のようになって，次にc1とbを1:φ,φ:1に内分する点c1',c2'を取ると
となり，c2とc1'は一致する．
このためf(c2)=f(c1')が成り立ち，関数の値を求める回数が1回で済む．
