Nonlinear Opt.: Gold section search 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Example) |
Proth (Diskussion | Beiträge) (→Authors) |
||
(16 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 3: | Zeile 3: | ||
− | The Golden Section Search is an algorithm/ technique for finding the extremum of an unimodal function over an interval without using derivatives. | + | The Golden Section Search is an algorithm/technique for finding the extremum of an unimodal function over an interval without using derivatives. |
− | 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 | + | 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 boundary is also the first new intermediate point. |
− | + | The name of the search method is based on the calculation of the two intermediate points by using the ''Golden Ratio''. | |
Zeile 21: | Zeile 21: | ||
'''Finding a maximum:''' | '''Finding a maximum:''' | ||
− | '''Step | + | |
+ | |||
+ | '''Step 1:''' | ||
Let '''''a''''' and '''''b''''' be the end points of the initial interval. Compute the intermediate points: | Let '''''a''''' and '''''b''''' be the end points of the initial interval. Compute the intermediate points: | ||
− | <math>x_{1}=a+\frac{b-a}{ | + | <math>x_{1}=a+\frac{b-a}{\varphi ^{2}}</math> |
<math>x_{2}=b-(x_{1}-a)</math> | <math>x_{2}=b-(x_{1}-a)</math> | ||
+ | |||
'''''Set k=2''''' | '''''Set k=2''''' | ||
Zeile 41: | Zeile 44: | ||
''''', then''''' | ''''', then''''' | ||
− | <math> | + | <math>a_{k}=a_{k-1}</math> '''''and''''' <math>b_{k}=x_{2}^{k-1}</math> |
− | <math>x_{1}^{k}= | + | <math>x_{1}^{k}=a_{k}+(x_{2}^{k-1}-x_{1}^{k-1})</math> '''''and''''' <math>x_{2}^{k}=x_{1}^{k-1}</math> |
'''(2)''' '''''If ''''' | '''(2)''' '''''If ''''' | ||
Zeile 51: | Zeile 54: | ||
''''', then''''' | ''''', then''''' | ||
− | <math> | + | <math>a_{k}=x_{1}^{k-1}</math> '''''and''''' <math>b_{k}=b_{k-1}</math> |
− | <math>x_{1}^{k}=x_{2}^{k-1}</math> '''''and''''' <math>x_{2}^{k}= | + | <math>x_{1}^{k}=x_{2}^{k-1}</math> '''''and''''' <math>x_{2}^{k}=b_{k}-(x_{2}^{k-1}-x_{1}^{k-1})</math> |
'''Step 3:''' | '''Step 3:''' | ||
− | Stop when <math>( | + | 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 <math>k</math> go to <math>k+1</math> and return to '''Step 2'''. |
Zeile 69: | Zeile 72: | ||
[[Datei:Extremwert.gif|center|gerahmt]] | [[Datei:Extremwert.gif|center|gerahmt]] | ||
− | |||
− | |||
− | |||
== Example == | == Example == | ||
Zeile 81: | Zeile 81: | ||
Initial interval: <math>[-0,5 ; 0,5]</math> | Initial interval: <math>[-0,5 ; 0,5]</math> | ||
− | Which option | + | Which option to choose for Step n depends on the previous iteration. |
+ | |||
+ | |||
+ | [[Datei:matrix.gif|left]] | ||
− | |||
Zeile 113: | Zeile 115: | ||
'''Explanation: ''' | '''Explanation: ''' | ||
+ | |||
+ | |||
'''Step 1:''' | '''Step 1:''' | ||
Zeile 125: | Zeile 129: | ||
<math>x_2^1=0,5-(x_{1}-(-0,5))=(-0,118)</math> | <math>x_2^1=0,5-(x_{1}-(-0,5))=(-0,118)</math> | ||
+ | |||
+ | |||
'''Step 2:''' | '''Step 2:''' | ||
− | - After calculating <math>x_1^1</math> and <math>x_2^1</math>, check if the condition is complied. For minimum of the function, set the condition to | + | - After calculating <math>x_1^1</math> and <math>x_2^1</math>, check if the condition is complied. For minimum of the function, set the condition to: |
<math>f(x_{1}^{k})<f(x_{2}^{k})</math> | <math>f(x_{1}^{k})<f(x_{2}^{k})</math> | ||
Zeile 136: | Zeile 142: | ||
- Now set the new boundaries: | - Now set the new boundaries: | ||
− | <math>a_2\mapsto x_{1}^{1}=(-0,118)</math> '''and''' | + | <math>a_2\mapsto x_{1}^{1}=(-0,118)</math> |
− | + | '''and''' | |
<math>b_2\mapsto b_1=0,5</math> | <math>b_2\mapsto b_1=0,5</math> | ||
Zeile 144: | Zeile 150: | ||
- The only variable which has to recalculate is: | - The only variable which has to recalculate is: | ||
− | <math>x_{2}^{2}= | + | <math>x_{2}^{2}=b_{2}-(x_{2}^{1}-x_{1}^{1})=0,264</math> |
+ | |||
'''Step n:''' | '''Step n:''' | ||
− | - For the next and all following steps | + | - For the next and all following steps check the condition again |
+ | |||
+ | - If the condition is complied, as for <math>k = 2</math>, use the upper restrictions for '''Step n''', shown in the tableau. If not, use the lower restrictions. | ||
+ | |||
+ | |||
+ | |||
+ | ==References== | ||
+ | |||
+ | |||
+ | |||
+ | Daellenbach, Hans G.(1988)-"Introduction to operations research techniques" | ||
+ | |||
+ | M. Asghar Bhatti(1998)-"Practical Optimization Methods" | ||
+ | |||
+ | Klaus Neumann, Martin Morlock(2002)-"Operations Research" | ||
+ | |||
+ | "http://en.wikipedia.org/wiki/Golden_section_search"- Aufruf 27.06.2013 | ||
+ | |||
+ | |||
+ | ==Authors== | ||
− | + | 381745 | |
− | + | 381604 |
Aktuelle Version vom 1. Juli 2013, 10:59 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. 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 boundary is also the first new intermediate point. 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 1:
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}{\varphi ^{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 go to and return to 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 to choose for Step n depends on the previous iteration.
Explanation:
Step 1:
- We have -0,5 and +0,5 as the initial interval
- Use -0,5 for variable and +0,5 for variable
With this two starting points we calculate and as explained above.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1^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^1=0,5-(x_{1}-(-0,5))=(-0,118)
Step 2:
- After calculating and , check if the condition is complied. For minimum of the function, set the condition to:
- is not smaller than
- Now set the new boundaries:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_2\mapsto x_{1}^{1}=(-0,118) and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): b_2\mapsto b_1=0,5
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}^{2}\mapsto x_{2}^1 = 0,118
- The only variable which has to recalculate is:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{2}=b_{2}-(x_{2}^{1}-x_{1}^{1})=0,264
Step n:
- For the next and all following steps check the condition again
- If the condition is complied, as for , use the upper restrictions for Step n, shown in the tableau. If not, use the lower restrictions.
References
Daellenbach, Hans G.(1988)-"Introduction to operations research techniques"
M. Asghar Bhatti(1998)-"Practical Optimization Methods"
Klaus Neumann, Martin Morlock(2002)-"Operations Research"
"http://en.wikipedia.org/wiki/Golden_section_search"- Aufruf 27.06.2013
Authors
381745
381604