三分探索
local optimumを1つみつけるアルゴリズム。
任意のlocal optimumがglobal optimumであるならばglobal optimumが見つかる。
例えば極値が1つで微分が0の有限の長さを持つ区間が存在しない場合
アルゴリズム
$ \lbrack l, r \rbrackから$ f(x)のlocal minimumを見つけたい場合には以下を繰り返す。
if $ f(\frac{l + 2r}{3}) > f(\frac{2l + r}{3})
$ l \leftarrow \frac{l+2r}{3}
else
$ r \leftarrow \frac{2l+r}{3}
local maximumの場合には不等号が逆。
計算量
1回のループで探索範囲は$ \frac{2}{3}になる。なので$ n回のループで探索範囲が最初の$ 10^{-d}程度を目指すのであれば、
$ (\frac{2}{3})^n < 10^{-d}
$ n > - \frac{d} {\log_{10}(\frac{2}{3})}
例えば$ d = 10なら$ n = 57回
参考