コンテンツにスキップ
検索

黄金分割探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』
この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
  • 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。
  • 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
  • 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
  • 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
  • 翻訳後、{{翻訳告知|en|Golden-section search|…}}をノートに追加することもできます。
  • Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2025年5月）
黄金分割探索

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

概略

[編集]

図は極小値を求めるための黄金分割探索の1ステップを表している。縦軸は {\displaystyle f(x)} の関数値、横軸はパラメータ {\displaystyle x} を表す。3点 {\displaystyle x_{1}}、{\displaystyle x_{2}}、{\displaystyle x_{3}} で {\displaystyle f(x)} の値が評価されているものとする。{\displaystyle f_{2}} は {\displaystyle f_{1}} と {\displaystyle f_{3}} のどちらよりも小さいので、{\displaystyle f} が単峰関数であることから、極小は {\displaystyle x_{1}} から {\displaystyle x_{3}} の範囲のどこかに存在するということがわかる。

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

評価点の選択

[編集]

図から、次のステップの区間は {\displaystyle x_{1}} から {\displaystyle x_{4}}（長さa+c）か {\displaystyle x_{2}} から {\displaystyle x_{3}}（長さb）のいずれかである。黄金分割探索では、この区間の長さが等しくなければならないという制約を置く。もし等しくなければ、運の悪い選択を繰り返すことで、収束速度が遅くなってしまう可能性がある。{\displaystyle b=a+c} を保証するためには、{\displaystyle x_{4}} を {\displaystyle x_{4}=x_{1}+(x_{3}-x_{2})} のように選択すればよい。

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

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

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

がいえる。一方、もし {\displaystyle f(x_{4})} が {\displaystyle f_{4b}} で次の3点が {\displaystyle x_{2}}、{\displaystyle x_{4}}、{\displaystyle x_{3}} であった場合を考えると

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

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

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

すなわち

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

がいえる。ただし、{\displaystyle \varphi } は黄金比

{\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://www.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 
「https://ja.wikipedia.org/w/index.php?title=黄金分割探索&oldid=104952649」から取得
黄金分割探索
話題を追加
Morty Proxy This is a proxified and sanitized view of the page, visit original site.