黄金分割探索

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）

翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

●英語版記事を日本語へ機械翻訳したバージョン︵Google翻訳︶。 ●万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 ●信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 ●履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 ●翻訳後、{{翻訳告知|en|Golden-section search|…}}をノートに追加することもできます。 ●Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

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

黄金分割探索

概略

図は極小値を求めるための黄金分割探索の1ステップを表している。縦軸は

{\displaystyle f(

の関数値、横軸はパラメータxを表す。3点

x_{1}

、

x_{2}

、

x_{3}

で

{\displaystyle f(

の値が評価されているものとする。

f_{2}

は

f_{1}

と

f_{3}

のどちらよりも小さいので、fが単峰関数であることから、極小は

x_{1}

から

x_{3}

の範囲のどこかに存在するということがわかる。次のステップでは、新しいxで関数を評価し、関数形を探る。このxを

x_{4}

とする。

x_{4}

は、最も広い区間︵この場合

x_{2}

と

x_{3}

の間︶のどこかに決めると効率がよい。図から、もし新しい関数値が

f_{4a}

であったとすると、極小は

x_{1}

から

x_{4}

の区間に存在することがわかる。この場合、次のステップでは3点は

x_{1}

、

x_{2}

、

x_{4}

となる。一方、もし新しい関数値が

f_{4b}

であった場合は、極小は

x_{2}

から

x_{3}

の区間に存在する。この場合、次の3点は

x_{2}

、

x_{4}

、

x_{3}

となる。いずれの場合も、各ステップで極小が存在する範囲を狭められるということが保証されている。

評価点の選択

図から、次のステップの区間は

x_{1}

から

x_{4}

︵長さa+c︶か

x_{2}

から

x_{3}

︵長さb︶のいずれかである。黄金分割探索では、この区間の長さが等しくなければならないという制約を置く。もし等しくなければ、運の悪い選択を繰り返すことで、収束速度が遅くなってしまう可能性がある。b = a+cを保証するためには、

x_{4}

を

x_{4}=x_{1}+(x_{3}-x_{2})

のように選択すればよい。しかしここで、

x_{2}

を

x_{1}

と

x_{3}

の間のどこに置けばよいのかという問題が残る。黄金分割探索では、3点の間隔の比が次の3点

x_{1},x_{2},x_{4}

あるいは

x_{2},x_{4},x_{3}

の比に等しいようにとる。間隔の比を一定にすることで、

x_{2}

が

x_{1}

や

x_{3}

に非常に近いといった状況が起こるのを防ぎ、各ステップで間隔が一様に小さくなっていくことを保証できる。数学的には、

f(x_{4})

の評価の前後で間隔の比が変わらないということを保証するためには、

f(x_{4})

が

f_{4a}

で次の3点が

x_{1}

、

x_{2}

、

x_{4}

であった場合を考えると

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

がいえる。一方、もし

f(x_{4})

が

f_{4b}

で次の3点が

x_{2}

、

x_{4}

、

x_{3}

であった場合を考えると

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

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

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

すなわち

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

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

\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, 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

「https://ja.wikipedia.org/w/index.php?title=黄金分割探索&oldid=100460108」から取得