黄金分割探索

黄金分割探索

黄金分割探索は、単峰関数の極値（極大値または極小値）を求める方法の一つで、極値が存在するとわかっている範囲を逐次的に狭めていく方法である。この方法は、常に3点の関数値を保持し、それらの距離の比が黄金比であることからこの名で呼ばれている。フィボナッチ探索や二分探索と密接な関係がある。フィボナッチ探索と黄金分割探索はテンプレート:Harv によって考案された（テンプレート:Harvnb も参照）。

概略

図は極小値を求めるための黄金分割探索の1ステップを表している。縦軸は$f(x)$の関数値、横軸はパラメータxを表す。3点$x_1$、$x_2$、$x_3$で$f(x)$の値が評価されているものとする。$f_2$は$f_1$と$f_3$のどちらよりも小さいので、fが単峰関数であることから、極小は$x_1$から$x_3$の範囲のどこかに存在するということがわかる。

次のステップでは、新しいxで関数を評価し、関数形を探る。このxを$x_4$とする。$x_4$は、最も広い区間（この場合$x_2$と$x_3$の間）のどこかに決めると効率がよい。図から、もし新しい関数値が$f_{4a}$であったとすると、極小は$x_1$から$x_4$の区間に存在することがわかる。この場合、次のステップでは3点は$x_1$、$x_2$、$x_4$となる。一方、もし新しい関数値が$f_{4b}$であった場合は、極小は$x_2$から$x_3$の区間に存在する。この場合、次の3点は$x_2$、$x_4$、$x_3$となる。いずれの場合も、各ステップで極小が存在する範囲を狭められるということが保証されている。

評価点の選択

図から、次のステップの区間は$x_1$から$x_4$（長さa+c）か$x_2$から$x_3$（長さb）のいずれかである。黄金分割探索では、この区間の長さが等しくなければならないという制約を置く。もし等しくなければ、運の悪い選択を繰り返すことで、収束速度が遅くなってしまう可能性がある。b = a+cを保証するためには、$x_4$を$x_4=x_1+(x_3-x_2)$のように選択すればよい。

しかしここで、$x_2$を$x_1$と$x_3$の間のどこに置けばよいのかという問題が残る。黄金分割探索では、3点の間隔の比が次の3点$x_1,x_2,x_4$あるいは$x_2,x_4,x_3$の比に等しいようにとる。間隔の比を一定にすることで、$x_2$が$x_1$や$x_3$に非常に近いといった状況が起こるのを防ぎ、各ステップで間隔が一様に小さくなっていくことを保証できる。

数学的には、 $f(x_4)$の評価の前後で間隔の比が変わらないということを保証するためには、$f(x_4)$が$f_{4a}$で次の3点が$x_1$、$x_2$、$x_4$であった場合を考えると

$\frac{c}{a}=\frac{a}{b}.$

がいえる。一方、もし$f(x_4)$が$f_{4b}$で次の3点が$x_2$、$x_4$、$x_3$であった場合を考えると

$\frac{c}{(b-c)}=\frac{a}{b}.$

がいえる。これらの式からcを除去すると、

${\left(\frac{b}{a}\right)}^2=\frac{b}{a}+1$

すなわち

$\frac{b}{a}=\phi$

がいえる。ただし、φは黄金比

$\phi =\frac{1+\sqrt{5}}{2}=1.618033988\dots$

である。

このように、間隔の比が黄金比になっていることがこのアルゴリズムの名称の由来である。

参考文献

• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation