Golden Section Search Method - Theory

The Golden Section Search Method is a numerical optimization technique used to efficiently find the optimal value within a specified interval. This method divides the search space using the golden ratio to narrow down the optimal solution with minimal iterations. By selecting intermediate points strategically, this method can converge towards the maximum smoothly. The technique is illustrated through computations and diagrams for a better understanding.

• Numerical Methods
• Optimization
• Golden Section Search
• Interval Search
• Efficient Search

noriast Follow

Uploaded on Dec 13, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Numerical Methods Golden Section Search Method - Theory http://nm.mathforcollege.com

2. For more details on this topic Go to http://nm.mathforcollege.com Click on Keyword Click on Golden Section Search Method

3. You are free to Share to copy, distribute, display and perform the work to Remix to make derivative works

4. Under the following conditions Attribution You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work). Noncommercial You may not use this work for commercial purposes. Share Alike If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one.

5. Equal Interval Search Method Choose an interval [a, b] over which the optima occurs. Compute and 2 2 2 + + a b a b + f f 2 + 2 + 2 a b a b If then the interval in which the maximum occurs is otherwise it occurs in 2 2 + f(x) f f 2 2 . Opt + 2 a b , b 2 + a b 2 2 + , a x a + b a b a + b 2 2 Figure 1 Equal interval search method. 5 http://nm.mathforcollege.com

6. Golden Section Search Method The Equal Interval method is inefficient when is small. Also, we need to compute 2 interior points ! The Golden Section Search method divides the search more efficiently closing in on the optima in fewer iterations. f2 f1 fu fL XL Xu X1 X2 Figure 2. Golden Section Search method 6 http://nm.mathforcollege.com

7. Golden Section Search Method- Selecting the Intermediate Points = . 0 382 ( ) b x x u L f2 = . 0 618 ( ) a x x f1 f1 u L fL fL fu fu a-b b b XL Xu X1 X2 XL Xu X1 a b a Determining the first intermediate point a X X l + = 1 a Determining the second intermediate point = X b u a b = = . 0 618 ( ?); why hence + = = = + ( a ) a b X X a X X a X b u l 2 u l = = . 0 618 * ( ), . 0 382 * ( ) X X and b X X u l u l + a a b b = = + 1 ) 1 1 R ( 5 b a a = + + = = = 2 1 1 0 61803 . 0 R R R R R b R = Let ,hence a 2 b Golden Ratio=> = . 0 618 ... a 7 http://nm.mathforcollege.com

8. Golden Section Search Method = + ( ) 4 sin 1 ( + cos ) f ( ) f = ( ) 4 sin 2 sin( 2 ) f = + = ( ) 4 cos + 4 cos( 2 ) 0 f 3 ] 1 = 2 4 cos 2 [ 4 cos 0 = Hence, after solving quadratic equation, with initial guess = (0, 1.5708 rad) . Opt 3 X X 3 2 1 2 =Initial Iteration Second Iteration st 1 Only 1 new inserted location need to be completed! 8 http://nm.mathforcollege.com

9. Golden Section Search- Determining the new search region f2 f1 f2 f1 fL fL fu fu X2 Case 1 X2 Case 2 XL Xu X1 XL Xu X1 Case1: If then the new interval is Case2: If then the new interval is ) ( ) ( 1 2 x f x f [ , , ] xL x 2x ( ) ( ) f x f x 2 1 1 [ , , ] x x ux 2 1 9 http://nm.mathforcollege.com

10. Golden Section Search- Determining the new search region At each new interval ,one needs to determine only 1(not 2) new inserted location (either compute the new ,or new ) Max. Min. It is desirable to have automated procedure to compute and initially. 2x 1x + = + = ( ) 4 sin 1 ( cos ) f ( ) 4 sin 1 ( cos ) f u x L x 10 http://nm.mathforcollege.com

11. Golden Section Search- (1-D) Line Search Method Min.g( )=Max.[-g( )] jth 0.382( U - l) 1st j-2th j-1th j U = (1.618)v V = 0 _ j - 2 b U L Figure 2.5 Golden section partition. a = L L = (1.618)v V = 0 0 2.618 5.232 Figure 2.4 Bracketing the minimum point. 9.468 2nd 1.6182 1.618 j - 2 a = L + 0.382( U l) = (1.618)v + 0.382 (1.618)j-1(1+1.618) V = 0 3rd j - 2 j - 1 a = (1.618)v + 1 (1.618)j-1 = (1.618)v = already known ! V = 0 V = 0 4th 11 http://nm.mathforcollege.com

12. Golden Section Search- (1-D) Line Search Method If If , Then the minimum will be between a & b. as shown in Figure 2.5, Then the minimum will be between & a L U = ( ) ( ) g g a b ( ) ( ) g ag b and . U = = U a = = . 1 ( j Notice that: And 618 ) U L U a = = = . 1 [ + . 1 [ 1 j j 1 ( 2 . 0 382 )( ) . 0 ( 236 )( 618 ] 618 ] ) b L b a U L . 1 618 = . 1 [ 1 [ . 1 + = . 1 [ 1 1 j j . 0 ( 236 )( 618 ] 618 ]) . 0 618 ( 618 ] ) . 1 618 Thus b (wrt U & L ) plays same role as a(wrt U & L ) !! = . 1 [ = j . 0 ( 382 ) ( 618 ] . 0 382 ( ) _ _ b L U L 12 http://nm.mathforcollege.com

13. Golden Section Search- (1-D) Line Search Method Step 1 : For a chosen small step size in ,say smallest integer such that . ,let j be the ) 1 = . 1 ( + 2 1 10 618 10 ) j j . 1 ( V V ( 618 ) ) ( g g = = 0 0 V V 2 J j = V = V The upper and lower bound on i are and = . 1 ( = . 1 ( . V V 618 ) 618 ) L U 0 0 Step 2: Compute g( b) ,where a= L+ 0.382( U- L) ,and b = L+ 0.618( U- L). Note that , so g( a) is already known. Step 3: Compare g( a) and g( b) and go to Step 4,5, or 6. Step 4: If g( a)<g( b),then L i b. By the choice of aand b, the new pointsandhave Compute , whereand go to Step 7. ) ( a g a = 1 j = V = . 1 ( V 618 ) a 0 = = = . . 0 + b a u b L L 382 ( ) L u L 13 http://nm.mathforcollege.com

14. Golden Section Search- (1-D) Line Search Method Step 5: If g( a) > g( b),then a i U. Similar to the procedure in Step 4, put and . Compute ,where and go to Step 7. L b = ) ( b g = = u u L a + . 0 618 ( ) u L Step 6: If g( a) = g( b) put L = aand u = b and return to Step 2. 1 = , + i ( , ) Step 7: If is suitably small, put and stop. Otherwise, delete the bar symbols on ,and and return to Step 3. u L u L 2 L a b u 14 http://nm.mathforcollege.com

15. THE END http://nm.mathforcollege.com

16. Acknowledgement This instructional power point brought to you by Numerical Methods for STEM undergraduate http://nm.mathforcollege.com Committed to bringing numerical methods to the undergraduate

17. For instructional videos on other topics, go to http://nm.mathforcollege.com This material is based upon work supported by the National Science Foundation under Grant # 0717624. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

18. The End - Really