Golden Section Search

Golden Section Search

The golden ratio

$\frac{a}{b}=\frac{b}{a+b}=\Phi$

Noticing that

$\frac{1}{\Phi }=\frac{a+b}{b}=\frac{a}{b}+1=\Phi +1$

it follows that

$\frac{1}{\Phi }=\Phi +1$

$1={\Phi }^2+\Phi$

${\Phi }^2+\Phi -1=0$

Solving $\Phi$

$\Phi =\frac{\sqrt{5}-1}{2}\approx 0.618034$

Approach to the univariate Golden Section Search

An interval of uncertainty $I^k=[a^k,b^k]$ (during iteration k) is iteratively reduced in a way that if the original interval of uncertainty $I^0=[a^0,b^0]$ were to contain a single local optimum of the function $f$, then so would all subsequent intervals of uncertainty $I^k$, for any $k\in \mathbb{N}$.

The GSS heuristic returns an estimate of the entire, sufficiently small interval of uncertainty which contains a local optimum of $f$.

Worked Example

$$f(x)=1+2x^2-e^x$$

with the initial point interval $I^0=[a^0,b^0]=[0,1]$

Step 1

The required number of search iterations is:

$\Omega =\lceil lo{g}_{\Phi }(\frac{{ϵ}_{tol}}{b^0-a^0})\rceil$ where $\Phi \approx 0.618034$.

$\Omega =\lceil lo{g}_{0.618034}(\frac{0.0005}{1-0})\rceil$ $\Omega =\lceil lo{g}_{0.618034}(0.0005)\rceil$ $\Omega \approx \lceil 15.7953366\rceil$

$\therefore \Omega =16$

Step 2

for $k=\Omega -1=16-1=15$:

Step 3

${\alpha }^k\leftarrow b^k-\Phi (b^k-a^k)$, ${\beta }^k\leftarrow a^k+\Phi (b^k-a^k)$

$I^0=[a^0,b^0]=[0,1]$

k	$a^k$	$b^k$	${\alpha }^k$	${\beta }^k$
0	0	1	0.381 966	-0.618 034
1
2
3
4
5
…
15

Approach to the bivariate Golden Section Search

The interval $I^k=[a^k,b^k]$ of uncertainty is replaced by a rectangle of uncertainty, denoted by $R^k=[a_1^k,b_1^k]\times [a_2^k,b_2^k]$ which has corner points ${\text{A}}^k,{\text{B}}^k,{\text{C}}^k$ and ${\text{D}}^k$.

$\Omega =max\{\lceil lo{g}_{\Phi }(\frac{{ϵ}_{tol}}{b_1^0-a_1^0})\rceil ,\lceil lo{g}_{\Phi }(\frac{{ϵ}_{tol}}{b_2^0-a_2^0})\rceil \}$

Worked Example

$f(x_1,x_2)=-x_1^2-4x_2^2+2x_1+8x_2-5$

with initial rectangle interval $R^0=[a_1^0,b_1^0,a_2^0,b_2^0]=[0,2]\times [0,\frac{3}{2}]$

Step 1

$\Omega =max\{\lceil lo{g}_{\Phi }(\frac{{ϵ}_{tol}}{b_1^0-a_1^0})\rceil ,\lceil lo{g}_{\Phi }(\frac{{ϵ}_{tol}}{b_2^0-a_2^0})\rceil \}$

$\Omega =max\{\lceil lo{g}_{0.618034}(\frac{0.0005}{2-0})\rceil ,\lceil lo{g}_{0.618034}(\frac{0.0005}{\frac{3}{2}-0})\rceil \}$

$\Omega =max\{\lceil (17.23576)\rceil ,\lceil (16.63793)\rceil \}$

$\Omega =max\{18,17\}$

$\Omega =18$