黄金分割探索 黄金分割探索 は、単峰関数の極値 （極大値または極小値）を求める方法の一つで、極値が存在するとわかっている範囲を逐次的に狭めていく方法である。この方法は、常に3点の関数値を保持し、それらの距離の比が黄金比 であることからこの名で呼ばれている。フィボナッチ探索や二分探索 と密接な関係がある。フィボナッチ探索と黄金分割探索は(Kiefer 1953 ) によって考案された（Avriel & Wilde 1966 も参照）。
概略 図は極小値を求めるための黄金分割探索の1ステップを表している。縦軸は f ( x ) {\displaystyle f(x)} x を表す。3点 x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} f ( x ) {\displaystyle f(x)} f 2 {\displaystyle f_{2}} f 1 {\displaystyle f_{1}} f 3 {\displaystyle f_{3}} f が単峰関数であることから、極小は x 1 {\displaystyle x_{1}} x 3 {\displaystyle x_{3}}
次のステップでは、新しいx で関数を評価し、関数形を探る。このx を x 4 {\displaystyle x_{4}} x 4 {\displaystyle x_{4}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} f 4 a {\displaystyle f_{4a}} x 1 {\displaystyle x_{1}} x 4 {\displaystyle x_{4}} x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 4 {\displaystyle x_{4}} f 4 b {\displaystyle f_{4b}} x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} x 2 {\displaystyle x_{2}} x 4 {\displaystyle x_{4}} x 3 {\displaystyle x_{3}}
評価点の選択 図から、次のステップの区間は x 1 {\displaystyle x_{1}} x 4 {\displaystyle x_{4}} a +c ）か x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} b ）のいずれかである。黄金分割探索では、この区間の長さが等しくなければならないという制約を置く。もし等しくなければ、運の悪い選択を繰り返すことで、収束速度が遅くなってしまう可能性がある。b = a +c を保証するためには、 x 4 {\displaystyle x_{4}} x 4 = x 1 + ( x 3 − x 2 ) {\displaystyle x_{4}=x_{1}+(x_{3}-x_{2})}
しかしここで、 x 2 {\displaystyle x_{2}} x 1 {\displaystyle x_{1}} x 3 {\displaystyle x_{3}} x 1 , x 2 , x 4 {\displaystyle x_{1},x_{2},x_{4}} x 2 , x 4 , x 3 {\displaystyle x_{2},x_{4},x_{3}} x 2 {\displaystyle x_{2}} x 1 {\displaystyle x_{1}} x 3 {\displaystyle x_{3}}
数学的には、 f ( x 4 ) {\displaystyle f(x_{4})} f ( x 4 ) {\displaystyle f(x_{4})} f 4 a {\displaystyle f_{4a}} x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 4 {\displaystyle x_{4}}
c a = a b . {\displaystyle {\frac {c}{a}}={\frac {a}{b}}.} がいえる。一方、もし f ( x 4 ) {\displaystyle f(x_{4})} f 4 b {\displaystyle f_{4b}} x 2 {\displaystyle x_{2}} x 4 {\displaystyle x_{4}} x 3 {\displaystyle x_{3}}
c ( b − c ) = a b . {\displaystyle {\frac {c}{(b-c)}}={\frac {a}{b}}.} がいえる。これらの式からc を除去すると、
( b a ) 2 = b a + 1 {\displaystyle \left({\frac {b}{a}}\right)^{2}={\frac {b}{a}}+1} すなわち
b a = φ {\displaystyle {\frac {b}{a}}=\varphi } がいえる。ただし、φは黄金比
φ = 1 + 5 2 = 1.618033988 … {\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, MR 0055639, https://jstor.org/stable/2032161 Avriel, Mordecai; Wilde, Douglass J. (1966), “Optimality proof for the symmetric Fibonacci search technique”, Fibonacci Quarterly 4 : 265–269, MR 0208812 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 
