Introduction to Golden Section Search Method by Leon Gradisar
"Learn about the Golden Section Search Method introduced by Leon Gradisar in 2010, a technique for finding the extremum of a function using a constant interval of reduction. Discover how this method is applied in various fields from geometry to architecture, along with its algorithm and workflow."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Golden Section Search By Leon Gradisar (531/2010)
Golden Section Method Introduction -Golden Section Method uses constant Interval of reduciton -Which can be seen in different aspects of proportion from geometry to architecture. 2/11
Golden Section Search Introduction The Golden section search is a technique for finding the extr emum (minimum or maximum) of a strictly unimodal function by successively narrowing the range of values inside which the extre mum is known to exist. -The technique derives its name from the fact that the algorithm maintains the function values for triples of points whose distance s form a golden ratio. -Fibonacci search and Golden section search were discovered by Kiefer (1953) 3/11
Golden Section Idea -The diagram above illustrates a single step in the technique for finding a minimum. -The value of has already been evaluated at the three points: x1,x2 and x3. Since f2 is smaller than either f1 or f3, it is clear that a minimum lies inside the interval from x1 to x3 (since f is unimodal). -The next step is evaluating it at a new value x4. -if the function yields f4a: then a minimum lies between x1 and x4 and the new triplet of points will be x1,x2 and x4 If the function yields f4b: then a minimum lies between x2 and x3, and the new triplet of points will be x2 and x3. -By this logic we can construct a new narrower search interval that is guaranteed to contain the function's minimum. 4/11
Golden Section Workflow -From the diagram, it is seen that the new search interval will be either between and with a length of a+c , or between and with a length of b . -To ensure that the spacing after evaluatingf(x4) -In case f(x4) = f4a our new triplet of points is x1,x2,x4 then we want: -In case f(x4)= our new triplet of points is x2,x4,x4 , then we want: -Eliminating c from these two equations yields: or -Where is the golden ratio: 5/11
Golden Section Algorithm 6/11
Maxeler MAXELER IN A NUTSHELL Dataflow paradigm The write to the memory is postponed until the data processing is finished Decreases cost of reading and writing temporary result Tokens on the entry points of vertices in a graph are a condition for operation completition Loop oriented, big data As less data dependences as possible 7/11
Golden Section Algorithm Code in Makseler 8/11
Golden Search Compile Results 9/11
Golden Section References Milutinovic, V., editor, Advances in Computers: DataFlow ,Elsevier, 2015. Milutinovic, V., Salom, J., Trifunovic, N., Giorgi, R. Guide to DataFlow SuperComputing , Springer, 2015 Milutinovic, V., editor, High-Level Language Computer Architec ture, (Chapter 9, DataFlow Machines, Gaudiot, J.-L.,), Computer Science Press, 1989. Golden Section , https://en.wikipedia.org/wiki/Jack_Kiefer_(statistician), 2016 Golden Section , https://en.wikipedia.org/wiki/Golden_section_search, 2016 10/11
Questions? Than you for your attention! 11/11
