曲がった迷路その21 - 黄金分割法

収束が近い予感がするのでどんどん進めよう。

さっき、はさみうち法をおさらいしたけど、もう一つの１次元最小化のアルゴリズムである黄金分割法のことを簡単にまとめておく。

黄金分割法

この方法は微係数を必要としないけど、探索区間の間に異なる２点の値が必要になる（1点だけでは無理ということは直感的にもわかる）。

具体的にどうするかと言うと図-27のように区間[a,b]のなかに2点cとdをとって、その値を比較する。

図の例ではf(c)のほうが小さく、最小値はあきらかに区間[c,b]ではなく[a,d]にあることがわかる。そこで探索区間を[a,d]に小さくして同じことを繰り返す。こうして区間を狭めていけばいい。中間の2点のとりかたは、効率には影響するが原理的にはどうでもいい。

効率を考えると一回で区間をなるべく小さくできるのがいいが、関数値の計算コストが高い場合には、一回の探索に2点の値が必要になることは不利になる。

図-27で探索区間を[a,d]にして繰り返したとき、点cの値はすでにわかっているので、2点のうち一方にこの点を使えば、新たに計算するのはもう1点ですむ。これを適当に選んでもいいけど、なかなか適当に選ぶというのも難しい。

このような場合、新しい2点の位置がいつも区間の同じ位置、つまり区間の端からの距離の比が同じになるようにすれば難しいことを考えずにすむ。

図-28のように、新しい2点が、区間の長さの比rとなるように決める。つまり

とする。

つぎに探索区間を[a,d]に縮小したときcの位置が使い回せるためには

となっていればいいからc、dの式を代入して整理すると

をみたすようなrにすれば、毎回かならず、前回の探索の一方の値が使えることになる。 この比rは

で、この1からの差1-rはいわゆる黄金比である。この比で絵を描けば美しくなるというのは僕は「そうなら苦労せんわ」と思うけど、その数学は単純で奥深くて美しい。

ようするに中間の2点を区間に対するこの比でとれば、一方の点は前回の区間探索の値を使えるということになって、区間探索1回ごとの値の計算回数ははさみうち法と同じ、区間の縮小率は0.5:0.618ですこしわるいけど微係数が必要ない、ということになる。