Nonlinear Opt.: Gold section search 2: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 12: | Zeile 12: | ||
| − | + | '''Finding a maximum: | |
| + | ''' | ||
'''Step one:''' | '''Step one:''' | ||
| Zeile 30: | Zeile 31: | ||
'''(1)''' '''''If''''' | '''(1)''' '''''If''''' | ||
| − | <math>f(x_{1}^{k-1})>f(x_{2}^{k-1})</math> | + | <math>f(x_{1}^{k-1})>f(x_{2}^{k-1})</math> '''In order to find a minimum:''' <math>f(x_{1}^{k-1})<f(x_{2}^{k-1})</math> |
| − | ''''',then''''' | + | ''''', then''''' |
<math>a^{k}=a^{k-1}</math> '''''and''''' <math>b^{k}=x_{2}^{k-1}</math> | <math>a^{k}=a^{k-1}</math> '''''and''''' <math>b^{k}=x_{2}^{k-1}</math> | ||
| Zeile 40: | Zeile 41: | ||
'''(2)''' '''''If ''''' | '''(2)''' '''''If ''''' | ||
| − | <math>f(x_{1}^{k-1})\leq f(x_{2}^{k-1})</math> | + | <math>f(x_{1}^{k-1})\leq f(x_{2}^{k-1})</math> '''In order to find a minimum:''' <math>f(x_{1}^{k-1})\geq f(x_{2}^{k-1})</math> |
| − | ''''',then''''' | + | ''''', then''''' |
<math>a^{k}=x_{1}^{k-1}</math> '''''and''''' <math>b^{k}=b^{k-1}</math> | <math>a^{k}=x_{1}^{k-1}</math> '''''and''''' <math>b^{k}=b^{k-1}</math> | ||
| Zeile 51: | Zeile 52: | ||
Stop when <math>(b^{k}-a^{k})<\varepsilon</math> , arbitrarily small, and let the optimal <math>x^{*}</math> be equal to the point <math>a^{k},b^{k},x_{1}^{k},x_{2}^{k}</math> with the maximum function value. Otherwise, let k go to k+1 and return step 2. | Stop when <math>(b^{k}-a^{k})<\varepsilon</math> , arbitrarily small, and let the optimal <math>x^{*}</math> be equal to the point <math>a^{k},b^{k},x_{1}^{k},x_{2}^{k}</math> with the maximum function value. Otherwise, let k go to k+1 and return step 2. | ||
| + | |||
| + | |||
| + | '''Finding a minimum:''' | ||
| + | |||
| + | |||
Version vom 20. Juni 2013, 18:36 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 points is the same as in the previous iteration. Fetter Text.The name of the search methods is based on the calculation of the two intermediate points by using the golden ratio.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Golden Ratio: \phi=\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
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.
Finding a minimum:
<a href="http://www.codecogs.com/eqnedit.php?latex=\begin{matrix}&space;k&space;&&space;a_k&space;&&space;b_k&space;&&space;{x_1}^k&space;&&space;{x_2}^k&space;&&space;f({x_1}^k)<f({x_2}^k)&space;&&space;f({x_1}^k)>f({x_2}^k)&space;\end{matrix}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\begin{matrix}&space;k&space;&&space;a_k&space;&&space;b_k&space;&&space;{x_1}^k&space;&&space;{x_2}^k&space;&&space;f({x_1}^k)<f({x_2}^k)&space;&&space;f({x_1}^k)>f({x_2}^k)&space;\end{matrix}" title="\begin{matrix} k & a_k & b_k & {x_1}^k & {x_2}^k & f({x_1}^k)<f({x_2}^k) & f({x_1}^k)>f({x_2}^k) \end{matrix}" /></a>
<img src="http://latex.codecogs.com/gif.latex?\begin{matrix}&space;k&space;&&space;a_k&space;&&space;b_k&space;&&space;{x_1}^k&space;&&space;{x_2}^k&space;&&space;f({x_1}^k)<f({x_2}^k)&space;&&space;f({x_1}^k)>f({x_2}^k)&space;\end{matrix}" title="\begin{matrix} k & a_k & b_k & {x_1}^k & {x_2}^k & f({x_1}^k)<f({x_2}^k) & f({x_1}^k)>f({x_2}^k) \end{matrix}" />
\[\begin{matrix} k & a_k & b_k & {x_1}^k & {x_2}^k & f({x_1}^k)<f({x_2}^k) & f({x_1}^k)>f({x_2}^k) \end{matrix}\]
\begin{matrix}
k & a_k & b_k & {x_1}^k & {x_2}^k & f({x_1}^k)<f({x_2}^k) & f({x_1}^k)>f({x_2}^k)
\end{matrix}
