Numerical on Dichotomous Search

Views:
 
Category: Education
     
 

Presentation Description

Dichotomous Search in a classic optimization technique.

Comments

Presentation Transcript

OPTIMIZATION ALGORITHMS:

OPTIMIZATION ALGORITHMS NUMERICALS ON DICHOTOMOUS SEARCH BY Sumita Das

Dichotomous Search:

Dichotomous Search It is a Search Based Method Requirements for Dichotomous Search: Interval of uncertainty which contains minimum of function must be bounded [a b] Function must be unimodal . PowerPoint Presentation by Sumita Das, GHRCE

Algorithm:

Algorithm Input: Level of uncertainty [a b] Initialization: k=0 a k =a b k =b ϵ > 0 l : Permitted length of interval PowerPoint Presentation by Sumita Das, GHRCE

Slide 4:

While( b k - a k )>l λ k = ( a k + b k ) /2 - ϵ μ k = ( a k + b k ) /2 + ϵ if f( λ k )>=f( μ k ) a k+1 = λ k b k+1 = b k Else b k+1 = μ k a k+1 = a k end if k=k+1 end while PowerPoint Presentation by Sumita Das, GHRCE If (b-a) is greater than permitted length of interval. Usually taken as 0.1 Find λ Find μ λ is now a. b remains same μ is now b. a remains same

In Simple words:

In Simple words We are using 4 point information i.e. a, b, λ and μ to find the minima/maxima PowerPoint Presentation by Sumita Das, GHRCE Midpoint λ μ ϵ ϵ a b How to calculate λ λ= (Midpoint of a and b) - ϵ λ=( a+b )/2 - ϵ How to calculate μ μ = (Midpoint of a and b) + ϵ μ = ( a+b )/2 + ϵ Place λ and μ symmetrically, each at a distance of ‘ ϵ ’ from the midpoint of a and b

Slide 6:

If f ( λ) >=f( μ), so the solution is on the right side . Hence solution is between λ and b. PowerPoint Presentation by Sumita Das, GHRCE In Simple words: Case A Midpoint λ μ ϵ a b ϵ λ is now a. Again Perform Procedure for new a and b. a b is now a Midpoint μ ϵ λ ϵ

Slide 7:

If f f ( λ)<f ( μ), so the solution is on the left side . Hence solution is between a and μ. PowerPoint Presentation by Sumita Das, GHRCE In Simple words: Case B Midpoint λ μ ϵ a b ϵ Midpoint a b is now b μ is now b. Again Perform Procedure for a and new b λ ϵ ϵ μ

Example:

Example Que : Find Minima f(x)= ( X-1) 2 +3 [-3 6] Solution: Let l=1, ϵ =0.5 k a k b k ( b k - a k ) λ k μ k f( λ k ) f( μ k ) 0 -3 6 9 (-3+6)/2 -0.5 =1 (-3+6)/2 +0.5 =2 (1-1) 2 +3 =3 (2-1) 2 +3 =4 1 -3 2 5 -1 0 7 4 2 -1 2 3 0 1 4 7 3 -1 1 2 -0.5 0.5 5.25 3.25 PowerPoint Presentation by Sumita Das, GHRCE Continue until ( b k - a k ) becomes <= l

Assignment:

Assignment Find the minimum of the function f(x)=x(x-1.5) in the interval [0 1] using dichotomous search. PowerPoint Presentation by Sumita Das, GHRCE k a k b k ( b k - a k ) λ k μ k f( λ k ) f( μ k ) 0 0 1 1 0.25 0.75 -0.3125 -0.5625 1 0.25 1 0.75 0.4375 0.8125 -0.464 -0.5585 2 0.4375 1 0.5625 0.578 0.859 -0.5329 -.5509

References:

References PowerPoint Presentation by Sumita Das, GHRCE [1] Singiresu S. Rao , “Engineering Optimization, Chapter 5: Nonlinear Programming I: One-Dimensional Minimization Methods”, 4 th Edition

authorStream Live Help