出典: フリー百科事典『ウィキペディア（Wikipedia）』
黄金分割探索
黄金分割探索は、単峰関数の極値（極大値または極小値）を求める方法の一つで、極値が存在するとわかっている範囲を逐次的に狭めていく方法である。この方法は、常に3点の関数値を保持し、それらの距離の比が黄金比であることからこの名で呼ばれている。フィボナッチ探索や二分探索と密接な関係がある。フィボナッチ探索と黄金分割探索は(Kiefer 1953) によって考案された（Avriel & Wilde 1966 も参照）。
図は極小値を求めるための黄金分割探索の1ステップを表している。縦軸は
の関数値、横軸はパラメータxを表す。3点
、
、
での値が評価されているものとする。
は
と
のどちらよりも小さいので、fが単峰関数であることから、極小はからの範囲のどこかに存在するということがわかる。
次のステップでは、新しいxで関数を評価し、関数形を探る。このxを
とする。は、最も広い区間（この場合との間）のどこかに決めると効率がよい。図から、もし新しい関数値が
であったとすると、極小はからの区間に存在することがわかる。この場合、次のステップでは3点は、、となる。一方、もし新しい関数値が
であった場合は、極小はからの区間に存在する。この場合、次の3点は、、となる。いずれの場合も、各ステップで極小が存在する範囲を狭められるということが保証されている。
評価点の選択[編集]
図から、次のステップの区間はから（長さa+c）かから（長さb）のいずれかである。黄金分割探索では、この区間の長さが等しくなければならないという制約を置く。もし等しくなければ、運の悪い選択を繰り返すことで、収束速度が遅くなってしまう可能性がある。b = a+cを保証するためには、を
のように選択すればよい。
しかしここで、をとの間のどこに置けばよいのかという問題が残る。黄金分割探索では、3点の間隔の比が次の3点
あるいは
の比に等しいようにとる。間隔の比を一定にすることで、がやに非常に近いといった状況が起こるのを防ぎ、各ステップで間隔が一様に小さくなっていくことを保証できる。
数学的には、 
の評価の前後で間隔の比が変わらないということを保証するためには、がで次の3点が、、であった場合を考えると
がいえる。一方、もしがで次の3点が、、であった場合を考えると
がいえる。これらの式からcを除去すると、
すなわち
がいえる。ただし、φは黄金比
である。
このように、間隔の比が黄金比になっていることがこのアルゴリズムの名称の由来である。
参考文献[編集]
- 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
