黄金分割探索

図は極小値を求めるための黄金分割探索の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 }$

である。

このように、間隔の比が黄金比になっていることがこのアルゴリズムの名称の由来である。