MBE203 6-7 - Lecture note PDF

Preview

Summary

Lecture note...

Description

MEEM2036 Engineering Computing, part 7, ver 4

MBE 2036 One-Dimensional Unconstrained Optimization Part 7

Jia Pan AC-1 Y6720 Email: [email protected] 1

MEEM2036 Engineering Computing, part 7, ver 4

What’s optimization ? • Finding the best result or optimal solution of a problem • Examples: – Power vs. Heat – Design vs. Cost

• Find x to minimize or maximize f(x) – f(x) –cost function, objective function

• One-dimensional vs. Multidimensional

2

MEEM2036 Engineering Computing, part 7, ver 4

Example • We need to enclose a rectangular field with a fence. We have 500 feet of fencing material and a building is on one side of the field and so won’t need any fencing. Determine the dimensions of the field that will enclose the largest area.

3

MEEM2036 Engineering Computing, part 7, ver 4

Solution • In most optimization problems we will have two functions. • The first is the function that we are actually trying to optimize • and the second will be the constraint.

4

MEEM2036 Engineering Computing, part 7, ver 4

• In this problem we want to maximize the area of a field and we know that will use 500 ft of fencing material. • So, the area will be the function we are trying to optimize and the amount of fencing is the constraint.

5

MEEM2036 Engineering Computing, part 7, ver 4

• Formally, we want to maximize • Where the constraint is

6

MEEM2036 Engineering Computing, part 7, ver 4

is the objective function or cost function • And we want to find that maximizes the objective function

7

MEEM2036 Engineering Computing, part 7, ver 4

Global and Local Min/Maximizers • • • • •

Global maximizer Global minimizer Local maximizer Local minimizer Global min/maximizer must be local min/maximizer • But the converse is NOT true

8

MEEM2036 Engineering Computing, part 7, ver 4

9

Example: 1D/2D Functions

Where are the global/local min/maximizers?

MEEM2036 Engineering Computing, part 7, ver 4

10

Global and Local Min/Maximizers • A minimizer of

is the maximizer of

• A maximizer of

is the minimizer of

• For both global and local min/maximizers

MEEM2036 Engineering Computing, part 7, ver 4

11

One-Dimensional Unconstrained Optimization Optimization

Root

V.S. Both involve: (1) initial guess and (2) search for a point on a function •

The optimum is the point where:

• In mathematical terms, f ’(x)=0 • If f”(x)0, the point is a minimum

•

The root is the point where:

• In mathematical terms, f (x)=0

• Some Optimization methods find an optima by solving the root problem of the first derivative of the function, i.e. f ’(x)=0 • However, f ’(x) may be difficult to find analytically. Numerical methods may be needed to solve the problem.

MEEM2036 Engineering Computing, part 7, ver 4

12

First Derivative Method for Finding Optimal Values  

Given: 

First Derivate of y : 󰆒

𝑑6(𝑥 − 3) 𝑑𝑥 𝑑(𝑥 − 3) 𝑑(𝑥 − 3) =6 𝑑(𝑥 − 3) 𝑑𝑥 =12 (x-3)

For finding the optimal values, we need to solve: 󰆒

󰆒󰆒

MEEM2036 Engineering Computing, part 7, ver 4

First Derivate Method for Finding Optimal Values Given: 





First Derivate of y : 󰆒





For finding the optimal values, we need to solve: 󰆒





=0

We expect 3 roots from here (complex) Sometimes it may not be easy to solve the equation!

13

MEEM2036 Engineering Computing, part 7, ver 4

Matlab roots >> roots([12, -30, -24, 12]) ans = 3.0485 -0.9092 0.3608

14

MEEM2036 Engineering Computing, part 7, ver 4

• Given a differentiable function ,a necessary condition for point to be an optimizer is . Such kind of points are called the critical points. – If , then the point is a local minimizer; – if , then the point is a local maximizer; – if , we cannot make a decision (and need to have more knowledge about the function’s higher order derivatives).

15

MEEM2036 Engineering Computing, part 7, ver 4

Example • We need to enclose a rectangular field with a fence. We have 500 feet of fencing material and a building is on one side of the field and so won’t need any fencing. Determine the dimensions of the field that will enclose the largest area.

16

MEEM2036 Engineering Computing, part 7, ver 4

Solution • Critical point satisfies • That is i.e.

17

MEEM2036 Engineering Computing, part 7, ver 4

Example • Suppose function is . Find the critical points. • Check whether they are local minimizer or maximizer. • Check whether they are global minimizer or maximizer.

18

MEEM2036 Engineering Computing, part 7, ver 4

Solution • First compute the critical points: then the critical points are and • Check • For thus is a local minimizer • For , thus is a local maximizer

19

MEEM2036 Engineering Computing, part 7, ver 4

20

Solution • Are they global minimizer or maximizer? • For local minimizer

– But



– So not a global minimizer over

• Similarly local maximizer global maximizer over

is not a

MEEM2036 Engineering Computing, part 7, ver 4

Also clear from the curve

21

MEEM2036 Engineering Computing, part 7, ver 4

Example • Suppose function is . Find its critical points and check whether they are local/global minimizer or maximizer.

22

MEEM2036 Engineering Computing, part 7, ver 4

Solution • First compute the critical points: thus is the only critical point thus cannot determine whether local minimizer or maximizer • Try numbers close to

– Thus neither minimizer or maximizer

23

MEEM2036 Engineering Computing, part 7, ver 4

Also clear from graph

24

MEEM2036 Engineering Computing, part 7, ver 4

Example • Suppose function is . Find the local minimizer or maximizer for , and check whether they are local minimizer or maximizer.

25

MEEM2036 Engineering Computing, part 7, ver 4

Solution • First compute the critical points: then the critical points are and • But now the interval is , thus only the is the critical point • We also need to check the boundary of the interval, i.e. when and

26

MEEM2036 Engineering Computing, part 7, ver 4

27

and

thus a local

minimizer • The values at the boundary:

smaller than both boundary – Thus

is the global minimizer

MEEM2036 Engineering Computing, part 7, ver 4

Can also be verified by the curve

28

MEEM2036 Engineering Computing, part 7, ver 4

29

Thus • Two local maximizer: boundary points and • One local minimizer: is the global maximizer is the global minimizer

MEEM2036 Engineering Computing, part 7, ver 4

Numerical Solutions • Sometimes analytical solution cannot be used – e.g., when the function is non-differentiable

30

MEEM2036 Engineering Computing, part 7, ver 4

Numerical Solutions • Sometimes analytical solution cannot be used • Sometimes it is difficult to solve the equation • Solution: Numerical approaches

31

MEEM2036 Engineering Computing, part 7, ver 4

Numerical Solution I • Golden-Section search • We first introduce some background about golden-section • And then discuss the algorithm

32

MEEM2036 Engineering Computing, part 7, ver 4

Golden-Section



33

MEEM2036 Engineering Computing, part 7, ver 4

34

Golden-section b

a

a

b Given golden-section:

Proof:

c

Answer:

MEEM2036 Engineering Computing, part 7, ver 4

Golden-Section Search • The Golden-Section search is a simple, general-purpose, singlevariable search technique • It is similar in spirit to the bisection approach for locating root • As with Bisection method, we can start by defining an interval that contains a single answer • That is the interval should contain a single maximum or minimum–it is called unimodal  The method starts with two initial guesses xL and xU that bracket one local optimal value of f(x)

35

MEEM2036 Engineering Computing, part 7, ver 4

Example: which is unimodal

36

MEEM2036 Engineering Computing, part 7, ver 4

Review of Root finding • Golden-section search is similar to the Bisection method for root finding • Let’s first review the bisection method

37

MEEM2036 Engineering Computing, part 7, ver 4

38

Bracketing methods Two initial guesses that bracket the root:

f(x)

Figure 5.4

x xL

xU

MEEM2036 Engineering Computing, part 7, ver 4

Bisection Method • Bisection method is a common Bracketing method • It uses an incremental search technique to find root. The basic principle is: – In general, if f(x) is real and continuous in the interval from xL and xU and f(xL) and f(xU) have opposite signs, i.e.

f(xL) f(xU) < 0 then there is at least one real root between f(xL) and f(xU)  Locating an interval where the function changes sign.  Dividing the interval into a number of subintervals. Each of these subintervals is searched to locate the sign change.  The process is repeated and the root estimate refined by dividing the subintervals into finer increments

39

MEEM2036 Engineering Computing, part 7, ver 4

Bisection Method (cont’) • The bisection method (alternatively called binary chopping, interval halving or Bolzano’s method) is one type of incremental search method in which the interval is always divided in half. • If the function changes sign over an interval, that particular interval will be sub-divided in half. • Each sub-interval will then be checked for sign change. • The sub-interval with the sign change will be sub-divided again into smaller subintervals • The whole process is repeated until the root is found or until the estimate error is less than a stopping criterion

40

MEEM2036 Engineering Computing, part 7, ver 4

Golden-Section Method • We also need to provide an interval that containing the optimal points – Say interval

41

MEEM2036 Engineering Computing, part 7, ver 4

42

Golden-Section Search (cont’)  Then, two interior points x1 and x2 are chosen according to the golden ratio R: d  R (xU  x L )  0.61803 (x U  x L )  0.61803  l 0 Eq 8.1 5 1 where R   0.61803 2

x1 = xL + d x2 = xU – d

f(x)

d

x1

x2 xL l1

For Golden ratio,

xU

l0 l1 = d

l1 l2 Eq 8.2  l0 l1

l2

l0  xU  xL  l1  l2 Eq 8.3

MEEM2036 Engineering Computing, part 7, ver 4

43

Golden-Section Search (cont’) • Substitute Eq 8.3 into Eq 8.2 l1 l  2 l1  l2 l1

Eq 8.4

• Take the reciprocal of Eq 8.4 l1  l2 l 1  l2 l1 let R 

l2 l1

Eq 8.5

 1 R 













1  R 2  R  1  0 Eq 8.6 R

 b  b2  4ac  1  1  4(  1)  1  5  0.61803 R   2a 2 2

MEEM2036 Engineering Computing, part 7, ver 4

Golden-Section Search (cont’) •

The function is evaluated at these two interior points. Two results can occur for finding a maximum value: i. If f(x1 ) > f(x2 ), the range of x from xL to x2 can be eliminated because it does not contain the maximum. Estimated xoptimal = x1 . For the next round of calculation, in this case, • • • • • • •

xLnew = x2old xUnew = xUold dnew = R*dold x1new = xLnew+ dnew Then calculate f new(x1 ) x2new = xUnew- dnew Then calculate f new(x2 )

44

MEEM2036 Engineering Computing, part 7, ver 4

45

Interval shrinkage Maximum

f(x)

eliminate

x1 xL

d d l0

xU

MEEM2036 Engineering Computing, part 7, ver 4

46

Interval shrinkage Maximum

f(x)

xLnew = x2old xUnew = xUold dnew = R*dold x1new = xLnew+ dnew x2new = xUnew- dnew

dnew dnew

xL new

xUnew

x2

x2new

xL

x1 new

x1 d

d l0

xU

MEEM2036 Engineering Computing, part 7, ver 4

• After that we need to evaluate f value at the new x1 and x2 • • • • • • •

xLnew = x2old xUnew = xUold dnew = R*dold x1new = xLnew+ dnew Then calculate f new(x1 ) x2new = xUnew- dnew Then calculate f new(x2 )

• However, we can actually save one f evaluation

47

MEEM2036 Engineering Computing, part 7, ver 4

48

new old =x x2 1

f(x)

dnew dnew

xLnew x2

xUnew x2new

xL

x1new

x1 d

xU

d l0 d new =R∙d old = R∙ (R∙l0old) = R 2 ∙ l0 old Eq 8.8 From Eq 8.6, R2 = 1 - R Eq 8.8 can be written as d new= (1-R) ∙ l0old This implies d new= l0 old- dold

Thus x2new = xUnew- dnew = xUold- (l0 old- dold ) = (xUold- l0 old)+ dold = xLold+ dold = x1old

MEEM2036 Engineering Computing, part 7, ver 4

49

new old =x x2 1

f(x)

dnew dnew

xLnew

xUnew

x2

x2new

xL

x1new

x1 d

d l0

xU

MEEM2036 Engineering Computing, part 7, ver 4

Thus, the algorithm •

The function is evaluated at these two interior points. Two results can occur for finding a maximum value: i. If f(x1 ) > f(x2 ), the range of x from xL to x2 can be eliminated because it does not contain the maximum. Estimated xoptimal = x1 . For the next round of calculation, in this case, • • • • • • •

xLnew = x2old xUnew = xUold dnew = R*dold x1new = xLnew+ dnew Then calculate f new(x1 ) x2new = xUnew- dnew Then calculate f new(x2 )

50

MEEM2036 Engineering Computing, part 7, ver 4

becomes •

The function is evaluated at these two interior points. Two results can occur for finding a maximum value: i. If f(x1 ) > f(x2 ), the range of x from xL to x2 can be eliminated because it does not contain the maximum. Estimated xoptimal = x1 . For the next round of calculation, in this case, • • • • • • •

xLnew = x2old xUnew = xUold dnew = R*dold x1new = xLnew+ dnew Then calculate f new(x1 ) x2new = x1old f new(x2 ) is equal to f old(x1 )

51

MEEM2036 Engineering Computing, part 7, ver 4

Key points • When selecting interior points using golden-section points, we only need to generate one new point in each iteration • The advantage is that we can save one function evaluation , and this can save a lot computational time when is complicated

52

MEEM2036 Engineering Computing, part 7, ver 4

Golden-Section Search ii.

If f(x2 ) > f(x1 ), then the range of x from x1 to xU can be eliminated because it does not contain the maximum. Estimated xoptimal = x2 . For the next round of calculation: • • • • • • •

iii.

•

•

xUnew = x1old xLnew = xLold dnew = R*dold x2new = xUnew - dnew Then calculate f new(x2 ) x1new = x2old f new(x1 ) is equal to f old(x2 )

Terminate when εa ≤ εs

Because the original x1 and x2 were chosen using the golden ratio, we do not have to re-calculate all the function values for the next iteration For finding the minimum, f(x1 ) > f(x2 ) change to f(x1 ) < f(x2 ) and f(x2 ) > f(x1 ) change to f(x2 ) < f(x1 )

53

MEEM2036 Engineering Computing, part 7, ver 4

54

Golden-Section Search (cont’) Maximum

f(x)

eliminate

x2 xL

x1 d

d

xU

MEEM2036 Engineering Computing, part 7, ver 4

55

Golden-Section Search (cont’) Maximum

f(x)

eliminate

d new=R∙d old

x2 new

x1new = x2old

xU

d new=R∙d old

xLnew= xLold

xUnew=x1old

d old = l0new

MEEM2036 Engineering Computing, part 7, ver 4

Golden-Section Search - Error Estimate • When an iteration in finding the optimal value is complete, the optimum will either fall in one of two intervals • If f(x2) > f(x1), the optimal value will be in the lower interval, ie between xL, x2 and x1 • If f(x1) > f(x2), the optimal value will be in the upper interval, ie between x2, x1 and xU • Because the interior points are symmetrical, either case can be used to define error. • We look at the example where the optimal point is at the upper interval.

56

MEEM2036 Engineering Computing, part 7, ver 4

57

Golden-Section Search – Error Estimate f(x) eliminate

Maximum

Considering the case when the maximum point is in interval between  and 

Δx

x1 xL Δx  x1  x2

d d

 xL  R(xU  xL )  xU  R(xU  xL )  xL  R(xU  xL )  xU  R(xU  xL )  xL  xU  2 R(xU  xL )  (2R  1)(xU  xL )  0.236(xU  xL ) Eq 8.9

xU

MEEM2036 Engineering Computing, part 7, ver 4

58

Golden-Section Search – Error Estimate f(x) eliminate

Maximum

Considering the case when the optimal point is between  and  Δx

x1 xL

d

Δx  x U  x 1

d

 xU  xL  R(xU  xL )  xU  xL  R(xU  xL )  ( 1  R)(xU  xL )  0.382(xU  x L ) Eq 8.10

xU

MEEM2036 Engineering Computing, part 7, ver 4

59

Golden-Section Search – Error Estimate • Based on Eq 8.9 and Eq 8.10, the maximum possible error for each iteration is (1-R)∙(xU – xL). Therefore εa can be calculated as follows:

 a  (1 - R)

xU  xL  100% xoptimal

Eq 8.11

MEEM2036 Engineering Computing, part 7, ver 4

60

Golden-Section Search - Summary

Continue on next slide…

MEEM2036 Engineering Computing, part 7, ver 4

Golden-Section Search - Summary

61

MEEM2036 Engineering Computing, part 7, ver 4

Example • Use the Golden-section search method to find the maximum of: x2 f(x)  2sinx  10

within the interval xL=0 and xU = 4. The true optimal value xoptimum = 1.4276. εs = 5%

62
...