Nonlinear Opt.: Gold section search 1

Interval reduction methods usually use the function value of two interior points in the interval to decide the direction in which to reduce it. One elegant way is to recycle one of the evaluated points and to use it in the nextiterations. This can be done by using the so-called Golden Section rule.

This method uses two evaluated points l (left) and r (right) in the interval $[a_{k},b_{k}]$ that are located in such a way that one of the points can be used again in the next iteration. The idea is sketched in Figure 1. The evaluation points l and r are located with fraction τ in such a way that Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): l=a+(1-\tau)(b-a)

and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): r=a+\tau(b-a)

. Equating in the Figure 1 the next right point to the old left point gives the equation Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau^2=1-\tau . The solution is the so-called Golden Section number Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau=\frac{\sqrt{5}-1}2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \approx 
0.618.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Algorithm Golden Section rule$([a,b],f,\epsilon )$

Set k := 1, a1 := a and b1 := b, Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau := \frac{\sqrt{5}-1}2

l := $x_{0}$ := a + (1 − Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau )(b − a); r := $x_{1}$ := a + Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau

(b − a)

Evaluate f($x_{1}$) := f($x_{0}$)

repeat

Evaluate f($x_{k}$)

        if (f(r) < f(l))

             $a_{k+1}$ := l; $b_{k+1}$ := $b_{k}$; l := r

             r := $x_{k+1}$ := $a_{k+1}$ + Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau

($b_{k+1}$ − $a_{k+1}$)

        else

             $a_{k+1}$ := $a_{k}$, $b_{k+1}$ := r; r := l

             l := $x_{k+1}$ := $a_{k+1}$ + (1 − Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tau
)($b_{k+1}$ − $a_{k+1}$)

        k := k + 1

until ($b_{k}$ − $a_{k}$ < $\epsilon$)

Example:

The Golden Section search is run on the function $f(x)=x+{\frac {16}{x+1}}$ with starting interval [2,4.5] accuracy $\epsilon =0.1$ The interval $a_{k}b_{k}$ encloses the minimum point Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^{*} . Notice that the interval is shrinking slower than by bisection, as Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): | b_{k+1}-a_{k+1} | = \tau | b_{k}-a_{k} | = \tau ^{k-1}|b_{1}-a_{1} |.

After 8 iterations

the reached accuracy is less than by bisection, although for this case xk approaches the minimum very well. On the other hand, only one function evaluation is required at each iteration.

Golden Section search for $f(x)=x+{\frac {16}{x+1}}$ , $[a_{0},b_{0}]$ = [2, 4.5], $\epsilon =0.1$

${\begin{vmatrix}&k&a_{k}&b_{k}&x_{k}&f(x_{k})\\&0&&&2.955&7.0005\\&1&2.000&4.500&3.545&7.0654\\&2&2.000&3.545&2.590&7.0468\\&3&2.590&3.545&3.180&7.0078\\&4&2.590&3.180&2.816&7.0089\\&5&2.816&3.180&3.041&7.0004\\&6&2.955&3.180&3.094&7.0022\\&7&2.955&3.094&3.008&7.0000\\&8&2.955&3.041&2.988&7.000\\\end{vmatrix}}$

I will write another example now, so that we can understand the topic better

The function is given Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(x)=-0.5x^{2}-e^{-x} .

Determine the method of golden section an approximation of the maximum point this function!

To use the initial interval $[a_{1},b_{1}]$ with $a_{1}=0,b_{1}=0$ and use two steps!

Solution:

In order to be able to apply the method of the golden section, the condition must initially to check that there is a concave function with F (x).

start

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda _{1}=a_{1}+\delta (b_{1}-a_{1})=0+0,382(1-0)=0,382

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \mu_{1}=a_{1}+(1-\delta )(b_{1}-a_{1})=0+0,618(1-0)=0,618

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(\lambda _{1})=-0,5*0,382^{2}-e^{-0,382}=0,755;

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(\mu _{1})=-0,5*0,618^{2}-e^{-0,618}=-0,73

1.Iteration

$F(\lambda _{1})<F(\mu _{2});a_{2}:=\lambda _{1};b_{2}=b_{1};i.e[a_{2},b_{2}]=[0.382,1]$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_2=\mu_1=0.618; \mu_2=a_2+(1-\delta )(b_2-a_2)=0.382+0.618(1-0.382)=0.764

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(\lambda_2)=F(\mu_1)=-0.730;F(\mu_2)=0.5*0.764^2-e^{-0.764}=-0.758

2.Iteration

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(\lambda_2)\geq F(\mu_2);a_3:=a_2;b_3:=\mu_2; i.e [a_3,b_3]=[0.382,0.764]

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \mu_3=\lambda_2=0.618;\lambda_3=a_3+\delta(b_3-a_3)=0.382+0.382(0.764-0.382)=0.528

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): F(\mu_3)=F(\mu_2)=0.730;F(\lambda_3)=-0.5*0.528^2-e^{-0.529}=-0.729

After 16 iterations we can reach the maximum at x=0.567 with F(x)=-0.728

Author: 378398 375861 378013

References:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \cdot

Eligius M. T. Hendrix,Boglárka G.-Tóth (2010) "Nonlinear Programming algorithms"

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \cdot

Domschke, Wolfgang (2005) "Übungen und Fallbeispiele zum Operations Research"