Golden Section method

This slide briefly explain about Golden Section Method .

1. GOLDEN SECTION METHOD SYED RUBAID AHMAD SAU/CS(M)/2013/01 Date : 7-5-2014

2. Contents What is Golden Section Method ? Terminology Working Method Numerical Example Conclusion References

3. What is Golden Section Method ? Golden Section is a technique to find out the extremum (maximum or minimum)of a strictly unimodal function by successively narrowing the range of values. This method maintains the function values for triples of points whose distances form a Golden ratio , So it’s known as Golden Section Method or Golden Ratio Method or Golden Mean Method . It is developed by an American statistician Jack Carl Kiefer in 1956 . He also developed Fibonacci Search Method .

4. Terminology Unimodal Function: a function f(x) is a unimodal function if for some value m, it is monotonically increasing for x ≤ m and monotonically decreasing for x ≥ m. In that case,the maximum value of f(x) is f(m) and there are no other local maxima. Interval of Uncertainty: Consider the line search problem to minimize θ(λ ) subject to a ≤ λ≤ b . Since the exact location of the minimum of θ over [a, b] is not known, this interval is called the interval of uncertainty. Golden Ratio: Two quantities are said to be in the golden ratio , if their ratio is the same as the rate of their sum to the larger of the two quantities. e.g a+ b/a = a/ b ≝ φ where Greek letter phi( φ ) represents Golden ratio . It value is φ =(1+√5)/2 =1.6180339887......

5. Working Method (1 of 2) The Golden Section Method for minimizing a unimodel Function over interval [ a k , b k ] : Initialization Step : Select an allowable final length of uncertainty l > 0 Let the initial interval of uncertainty be [a 1 ,b 1 ]   and let λ 1 = a 1  +(1- α)(b 1  - a 1 ) and μ 1 = a 1  + α( b 1  - a 1 ) , where α = 0.618. Evaluate θ(λ 1 ) and  θ(μ 1 ) , let k= 1 and go to Main Step

6. Working Method (2 of 2) Main Step : 1. If b k  - a k  < l , stop ; The optimal solution lies in the interval [ a k , b k ] . Otherwise , if θ(λ k ) >  θ(μ k ) , go to Step 2 and If θ(λ k ) ≤  θ(μ k ) , go to Step 3 . 2. Let a k+1 = λ k and b k+1 = b k . Furthermore , let λ k+1 = μ k and let μ k+1 = a k+1 + α( b k+1 -a k+1 ) . Evaluate θ( μ k+1 ) and go to Step 4. 3 . Let a k+1 = a k and b k+1 = μ k . Furthermore , let μ k+1 = λ k and let λ k+1 = a k+1 +(1- α ) ( b k+1 -a k+1 ) . Evaluate θ( λ k+1 ) and go to Step 4. 4 . Replace k by k+1 and go to Step 1

7. Numerical Example : Consider the following Problem : Minimize λ² + 2λ subject to -3 ≤ λ≤ 5 Clearly ,The given function to be minimized & its length of initial interval of uncertainty is 8 . λ 1 = a 1  +(1- α)(b 1  - a 1 ) λ 1 = -3+(1-0.618){5-(-3)}=-3+0.382(8) = 0.056 μ 1 = a 1  + α( b 1  - a 1 ) μ 1 =-3 +0.618{5-(-3)} = -3 + 0.618(8) = 1.944 Note that , θ(λ 1 ) < θ(μ 1 ) . The new interval of Uncertainty is [-3,1.944]. The Process is repeated & the computations are summarized in Table . The value of θ that are computed at each iteration are indicated by asterisk(*)

8. Table of Computations for Golden Section Method Iteration k a k b k λ k μ k θ(λ k ) θ(μ k ) 1 -3.000 5.000 0.56 1.944 0.115* 7.667* 2 -3.000 1.944 -1.112 0.056 -0.987* 0.115 3 -3.000 0.056 -1.832 -1.112 -0.308* -0.987 4 -1.832 0.056 -1.112 -0.664 -0.987 -0.887* 5 -1.832 -0.664 -1.384 -1.112 -0.853* -0.987 6 -1.384 -0.664 -1.112 -0.936 -0.987 -0.996* 7 -1.112 -0.664 -0.936 -0.840 -0.996 -0.974* 8 -1.112 -0.840 -1.016 -0.936 -1.000* -0.996 9 -1.112 -0.936 After eight iterations involving 9-observations , the interval of uncertainty is [-1.112,-0.936] , so that the minimum can be estimated to be the midpoint -1.024 . Note that the true minimums is in fact -1.0

9. Conclusion Golden ratio search is effective in unimodal optimization because it results in the least number of searches or trials to locate the optimum.Given a unimodal object function defined in a starting range [a 1 ,b 1 ],to search step-by-step, one condenses the range in which the optimal point is located until the width of the range is less than the given accuracy to position the location. Golden Section search is the use of the golden section ratio 0.618, or symmetrically,(1-0.618) =0.382, to condense the width of the range in each step.

10. References Website : http://en.wikipedia.org/wiki/Golden_section_search http://en.wikipedia.org/wiki/Golden_ratio http://en.wikipedia.org/wiki/Jack_Kiefer_(mathematician) http://en.wikipedia.org/wiki/Unimodality Online Tool used for mathematical formulation : http://math.typeit.org/ Books: “Nonlinear Programming: Theory and Algorithms ” by Mokhtar S. Bazar , Hanif D. Sherali and C.M. Shetty Publisher : John Willey & Sons Inc. “ Operationsns Research An Intoduction –Eight Edition ” by Hamdy A.Taha , Publisher : Prentice – Hall of India Private Limited Journal : “Using Golden Ratio Search to Improve Paired Construction of Quality ControlCharts ” by Xia Pan, , Jeffrey E. Jarrett at International Journal of Economics an Management Engineering (IJEME)

11. Thank you !!!