黄金分割法

非線形計画における１次元最適化法（最適探索法）の一種である。 †

1 次元最適化（最適地の探索法）の目的は，f(x) （x はスカラー）の最小値を求めること。 区間 [a, b] の中に，f(x) が最小となる点が一つだけあるとします．黄金分割法では，最小点が存在する区間を徐々に狭めていくことによって，最小点を求めようとする

• The golden section search is a technique for finding the extremum (minimum or maximum) of a unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triples of points whose distances form a golden ratio. The algorithm is closely related to a Fibonacci search (also described below) and to a binary search. Golden section search was introduced by Kiefer (1953), and Fibonacci search by Avriel and Wilde (1966).

基本的考え方 †

一般に、 f(x) が区間 [a, b] で単峰性（この区間で，唯一の最小点を持つ）であるとき，最小点の存在範囲を [a, b] の中のより小さい部分区間に狭めるためには，少なくとも区間内の 2 点における関数の値を知る必要がある。

ここで、「各ステップごとに，最小点を含む区間の幅を一定の比率 τ で減らせるようにできるか？」という問題を考える。

ここで[a(i), b(i)] : ある段階における区間　、x1(i), x2(i) : 区間内の点（x1(i) < x2(i)） としたとき，一定比率 τ で減少するためには，次式を満たす必要があります．

(x2(i) - a(i)) / (b(i) - a(i)) = (b(i) - x1(i)) / (b(i) - a(i)) = τ　　(1)

したがって

x1(i) - a(i) = b(i) - x2(i)　　                                              (2)

いま，f(x2(i)) > f(x1(i)) とすると

b(i+1) = x2(i) 
a(i+1) = a(i) 

が成立します． さらに，

x2(i+1) = x1(i) 

とします. したがって，

(x2(i+1) - a(i)) / (x2(i) - a(i)) = (x1(i) - a(i)) / (x2(i) - a(i)) = τ　　(3) 

となります．また，(2) 式より，

x1(i) - a(i) = b(i) - a(i) - (x2(i) - a(i)) 

なので,この両辺を (x2(i) - a(i)) で割ると，(1)，(3) 式より，

(x1(i) - a(i)) / (x2(i) - a(i)) = 1 / τ - 1 = τ 

となります．従って，次の関係が得られます．

τ 2 + τ - 1 = 0

この２次方程式の正の根は、

 τ = （√５- 1) / 2 ≒ 0.618 　かつ　1+τ＝黄金比（黄金数）

になる。 黄金分割法では，この τ を使用します． 初期区間 [a(0), b(0)] を与えた後，区間内を、0.618で内分しながら、より小さい値が得られる区間を収束するまで，手続きを繰り返します．

簡単な手順 †

• x1,x2 を、 をそれぞれ、区間[a,b}を τ:1 およびその逆に内分する点とする。
• それぞれの点で関数値 f1, f2 を計算する。
• f1>f2なら最小値は区間[x1,b] にあるので、a を x1 で置き換え、最初に戻る。x2 が 次の ｘ１ になるので、関数値も使い回せる。
• そうでなければ逆に b を x2 で置き換え、同様に 最初に戻る。 上の手順を 区間巾[a,b]が十分小さくなるまで繰り返す。

この反復法のメリット †

一定の比率で区間巾を狭められるので、収束性が保証される。
反復一度について関数計算が1度ですむので計算が速い

黄金分割法は、測定回数が限られているとき、最も小さい区間に縮小できる方法であることが証明されています。