Nonlinear Opt.: Gold section search 2: Unterschied zwischen den Versionen

Version vom 21. Juni 2013, 14:12 Uhr

General

The Golden Section Search is an algorithm/ technique for finding the extremum of an unimodal function over an interval without using derivatives. It is very clever. The advantage towards other section search methods is the need, of only one new evaluation instead of two, because one intermediate point from the previous iteration is used. Fetter Text.The name of the search method is based on the calculation of the two intermediate points by using the Golden Ratio.

Golden Ratio: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \varphi=\frac{a}{b}=\frac{1+\sqrt{5}}{2}= 1,618

Golden Section Algorithm

Finding a maximum:

Step one:

Let a and b be the end points of the initial interval. Compute the intermediate points:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}=a+\frac{b-a}{(1,618)^{2}}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}=b-(x_{1}-a)

Set k=2

Step 2:

(1) If

  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{1}^{k-1})>f(x_{2}^{k-1})
                                                     In order to find a minimum:    Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{1}^{k-1})<f(x_{2}^{k-1})

, then

                      Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a^{k}=a^{k-1}
    and    Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b^{k}=x_{2}^{k-1}

                      Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}^{k}=a^{k}+(x_{2}^{k-1}-x_{1}^{k-1})
  and  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{k}=x_{1}^{k-1}

(2) If

 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{1}^{k-1})\leq f(x_{2}^{k-1})
                                                    In order to find a minimum:    Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x_{1}^{k-1})\geq f(x_{2}^{k-1})
        
         

, then

                         Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a^{k}=x_{1}^{k-1}
    and   Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b^{k}=b^{k-1}

                        Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}^{k}=x_{2}^{k-1}
  and   Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{k}=b^{k}-(x_{2}^{k-1}-x_{1}^{k-1})

Step 3:

Stop when Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (b^{k}-a^{k})<\varepsilon

, arbitrarily small and let the optimal Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^{*}
be equal to the point ${\displaystyle a^{k},b^{k},x_{1}^{k},x_{2}^{k}}$ with the maximum function value. Otherwise, let k go to k+1 and return step 2.

Example

Function: ${\displaystyle f(x)=\left|x\right|}$

Initial interval: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): [-0,5 ; 0,5]