Nonlinear Opt.: Gold section search 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Proth (Diskussion | Beiträge) |
|||
Zeile 8: | Zeile 8: | ||
− | [[Datei:Golden_ration.png|rechts|gerahmt|Golden Ratio]] | + | [[Datei:Golden_ration.png|rechts|gerahmt|Golden Ratio Spiral]] |
'''Golden Ratio: ''' <math>\varphi=\frac{a}{b}=\frac{1+\sqrt{5}}{2}= 1,618</math> | '''Golden Ratio: ''' <math>\varphi=\frac{a}{b}=\frac{1+\sqrt{5}}{2}= 1,618</math> |
Version vom 26. Juni 2013, 16:48 Uhr
Inhaltsverzeichnis
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 the one intermediate point from the previous iteration that isn't used as a new interval bound is also the first new intermediate point. 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 with the maximum function value. Otherwise, let k go to k+1 and return step 2.
Graphical illustration for finding the minimum of the function: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x)=(x-2)^2-2
with an initial interval of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): [-10 ; 10]
Example
Function:
Initial interval: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): [-0,5 ; 0,5]
Which option you have to choose for the step n depends on your previous iteration.
Explanation:
Step 1 - We have -0,5 and +0,5 as the initial interval and use -0,5 for variable a und +0,5 for variable b. With this two starting points we calculate x1 and x2 as explained above. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}=(-0,5)+\frac{0,5-(-0,5)}{(1,618)^{2}}=0,118
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}=0,5-(x_{1}-(-0,5))=(-0,118)
Step 2 -