Dichotomous Search in a classic optimization technique.

Comments

Posting comment...

Premium member

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

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.