黄金分割探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』

移動: 案内検索
黄金分割探索

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

概略[編集]

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

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

評価点の選択[編集]

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

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

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

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

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

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

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

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

すなわち

\frac{b}{a}=\varphi

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

\varphi= \frac{1+\sqrt{5}}{2}= 1.618033988\ldots

である。

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

脚注[編集]