黄金分割探索

黄金分割探索とは

黄金分割探索は、単峰関数（一つの極大値または極小値を持つ関数）の極値を求めるための数値最適化アルゴリズムの一つです。この方法は、関数の極値が存在する範囲を特定し、その範囲を段階的に狭めていくことで、より正確な極値の位置を特定します。特に、微分が難しい関数や導関数が利用できない場合に有効です。

探索の概要

黄金分割探索では、常に3つの評価点（x1, x2, x3）を用いて探索を行います。これらの点における関数値（f(x1), f(x2), f(x3)）を比較し、極値が存在する可能性のある範囲を絞り込みます。例えば、関数f(x)がx1からx3の範囲で極小値を持つ場合、もしf(x2)がf(x1)とf(x3)よりも小さければ、極小値はx1とx3の間に存在すると判断できます。

次のステップでは、新たな評価点x4を導入します。このx4は、最も広い区間（この場合はx2とx3の間）に設定します。x4における関数値f(x4)を評価することで、極値が存在する範囲をさらに絞り込みます。もしf(x4)がf(x2)より小さければ、極小値はx1からx4の間に存在し、そうでなければx2からx3の間に存在すると判断します。

このように、各ステップで極値が存在する範囲を狭めていくことで、より正確な極値の位置を特定することができます。

評価点の選択

黄金分割探索の効率性を高めるために重要なのが、評価点の配置です。このアルゴリズムでは、各ステップで評価点の配置比率を一定に保つ必要があります。具体的には、評価点の間隔の比率が常に黄金比（約1.618）になるように評価点を設定します。これにより、各ステップで探索範囲が均等に狭まり、効率的に極値に近づくことができます。

例えば、現在の探索範囲がx1からx3であり、x2がその中間にあるとします。次の評価点x4は、x1とx3の間で、x1からx2の距離とx2からx4の距離の比が黄金比になるように決定されます。これにより、次のステップで探索範囲がx1からx4、またはx2からx3に絞り込まれる場合でも、探索効率が損なわれることがありません。

なぜ黄金比なのか？

黄金比を用いる理由は、探索範囲を効率よく絞り込むためです。もし評価点の間隔が均等でなければ、探索範囲の収縮速度が遅くなり、極値を見つけるまでに多くのステップが必要になる可能性があります。黄金比を用いることで、各ステップで探索範囲を一定の比率で絞り込むことができ、効率的に極値を見つけることができます。

具体的には、以下の関係式が成り立ちます。

次の評価点x4を導入する際、x1, x2, x4 の間隔比、または x2, x4, x3 の間隔比が黄金比になるように調整します。この比率を維持することで、探索範囲の縮小が安定し、アルゴリズムの収束が早まります。



c/a = a/b


これは、新しい評価点x4がf(x4a)であった場合です。一方、f(x4)がf(x4b)であった場合は


c/(b-c) = a/b

が成立します。

これらの式からcを消去すると


(b/a)^2 = (b/a) + 1

が得られ、この式を解くと、b/aは黄金比φになることが分かります。このように、黄金分割探索は、評価点の間隔比に黄金比を利用することで、効率的な探索を実現しているのです。

まとめ

黄金分割探索は、単峰関数の極値を効率的に探索するための強力なアルゴリズムです。黄金比を用いることで、探索範囲を段階的に絞り込み、少ないステップで正確な極値を特定することができます。そのため、多くの最適化問題において重要な役割を果たしています。

もう一度検索