コンテンツにスキップ

黄金分割探索

出典: フリー百科事典『ウィキペディア(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