黄金分割探索

黄金分割探索は、単峰関数の極値（極大値または極小値）を求める方法の一つで、極値が存在するとわかっている範囲を逐次的に狭めていく方法である。この方法は、常に3点の関数値を保持し、それらの距離の比が黄金比であることからこの名で呼ばれている。フィボナッチ探索や二分探索と密接な関係がある。フィボナッチ探索と黄金分割探索は によって考案された（ も参照）。
概略.
図は極小値を求めるための黄金分割探索の1ステップを表している。縦軸はformula_1の関数値、横軸はパラメータ"x"を表す。3点formula_2、formula_3、formula_4でformula_1の値が評価されているものとする。formula_6はformula_7とformula_8のどちらよりも小さいので、"f"が単峰関数であることから、極小はformula_2からformula_4の範囲のどこかに存在するということがわかる。
次のステップでは、新しい"x"で関数を評価し、関数形を探る。この"x"をformula_11とする。formula_11は、最も広い区間（この場合formula_3とformula_4の間）のどこかに決めると効率がよい。図から、もし新しい関数値がformula_15であったとすると、極小はformula_2からformula_11の区間に存在することがわかる。この場合、次のステップでは3点はformula_2、formula_3、formula_11となる。一方、もし新しい関数値がformula_21であった場合は、極小はformula_3からformula_4の区間に存在する。この場合、次の3点はformula_3、formula_11、formula_4となる。いずれの場合も、各ステップで極小が存在する範囲を狭められるということが保証されている。
評価点の選択.
図から、次のステップの区間はformula_2からformula_11（長さ"a"+"c"）かformula_3からformula_4（長さ"b"）のいずれかである。黄金分割探索では、この区間の長さが等しくなければならないという制約を置く。もし等しくなければ、運の悪い選択を繰り返すことで、収束速度が遅くなってしまう可能性がある。"b" = "a"+"c"を保証するためには、formula_11をformula_32のように選択すればよい。
しかしここで、formula_3をformula_2とformula_4の間のどこに置けばよいのかという問題が残る。黄金分割探索では、3点の間隔の比が次の3点formula_36あるいはformula_37の比に等しいようにとる。間隔の比を一定にすることで、formula_3がformula_2やformula_4に非常に近いといった状況が起こるのを防ぎ、各ステップで間隔が一様に小さくなっていくことを保証できる。
数学的には、 formula_41の評価の前後で間隔の比が変わらないということを保証するためには、formula_41がformula_15で次の3点がformula_2、formula_3、formula_11であった場合を考えると
がいえる。一方、もしformula_41がformula_21で次の3点がformula_3、formula_11、formula_4であった場合を考えると
がいえる。これらの式から"c"を除去すると、
すなわち
がいえる。ただし、φは黄金比
である。
このように、間隔の比が黄金比になっていることがこのアルゴリズムの名称の由来である。