黄金分割探索のソースを表示

{{Expand English|Golden-section search|date=2024年5月}}
[[Image:GoldenSectionSearch.png|thumb|325px|right|黄金分割探索]]

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

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

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

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

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

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

:<math>\frac{c}{a}=\frac{a}{b}.</math>

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

:<math>\frac{c}{(b-c)}=\frac{a}{b}.</math>

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

:<math>\left(\frac{b}{a}\right)^2=\frac{b}{a}+1</math>

すなわち

:<math>\frac{b}{a}=\varphi</math>

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

:<math>\varphi= \frac{1+\sqrt{5}}{2}= 1.618033988\ldots</math>

である。

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

==脚注==
{{脚注ヘルプ}}
{{Reflist|2}}

==参考文献==
{{Refbegin}}
*{{citation
 | last = Kiefer
 | first = J.
 | authorlink = Jack Kiefer
 | title = Sequential minimax search for a maximum
 | jstor = 2032161
 | journal = [[Proceedings of the American Mathematical Society]]
 | volume = 4
 | year = 1953
 | issue = 3
 | pages = 502–506
 | mr = 0055639 
 | doi = 10.2307/2032161 |ref=harv}}
*{{citation
 | last1 = Avriel
 | first1 = Mordecai
 | last2 = Wilde
 | first2 = Douglass J.
 | title = Optimality proof for the symmetric Fibonacci search technique
 | journal = [[Fibonacci Quarterly]]
 | volume = 4
 | year = 1966
 | pages = 265–269
 | mr = 0208812 |ref=harv}}
*{{Citation | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press |  publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 10.2. Golden Section Search in One Dimension | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=492}}
{{Refend}}

{{最適化アルゴリズム}}
{{貴金属比}}
{{DEFAULTSORT:おうこんふんかつたんさく}}
[[Category:最適化アルゴリズム]]