黄金おうごん分割ぶんかつ探索たんさく

黄金おうごん分割ぶんかつ探索たんさく

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

概略がいりゃく

図ずは極小きょくしょう値ちを求もとめるための黄金おうごん分割ぶんかつ探索たんさくの1ステップを表あらわしている。縦たて軸じくは$f(x)$の関数かんすう値ち、横よこ軸じくはパラメータxを表あらわす。3点てん$x_{1}$、$x_{2}$、$x_{3}$で$f(x)$の値ねが評価ひょうかされているものとする。$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, 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