黄金分割探索

黄金分割探索

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

概略

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

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

評価点の選択

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

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

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

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

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

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

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

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

すなわち

${\displaystyle {\frac {b}{a}}=\varphi }$

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

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

である。

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

脚注

参考文献

• Kiefer, J. (1953), “Sequential minimax search for a maximum”, Proceedings of the American Mathematical Society 4 (3): 502–506, doi:10.2307/2032161, JSTOR 2032161, MR0055639, https://jstor.org/stable/2032161 
• Avriel, Mordecai; Wilde, Douglass J. (1966), “Optimality proof for the symmetric Fibonacci search technique”, Fibonacci Quarterly 4: 265–269, MR0208812 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), “Section 10.2. Golden Section Search in One Dimension”, Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8, http://apps.nrbook.com/empanel/index.html#pg=492