Chapter 4

Chapter 4

Basic Concepts of Optimization

1
 CONTINUITY OF FUNCTIONS

•In carrying out analytical or numerical optimization you will

find it preferable and more convenient to work with continuous
Chapter 4

functions of one or more variables than with functions

containing discontinuities.
•A function of a single variable x is continuous at a point x0 if

2
Chapter 4 CONTINUITY OF FUNCTIONS

•Case A in Figure 4.1 shows a discontinuous function.

•For case B, the function of x has a "kink" in it, but f(x) does
satisfy the property of continuity.
•However, f'(x)=df(x)/dx does not. Therefore, the function in
case B is continuous but not continuously differentiable. 3
 CONTINUITY OF FUNCTIONS

•A discontinuity in a function may or may not cause difficulty

in optimization.
•In case A in Figure 4.1, the maximum occurs reasonably far
Chapter 4

from the discontinuity which may or may not be encountered in

the search for the optimum.
• In case B, if a method of optimization that does not use
derivatives is employed, then the "kink“ in f(x) is probably
unimportant, but methods employing derivatives might fail,

4
 DISCRETE FUNCTIONS

•Objective functions that allow only discrete values of the

independent variable(s) occur frequently in process design.
•Examples are the cost per unit diameter of pipe, insulation cost
Chapter 4

considered in Example 1.1.

•For a pipe, we might represent

the installed cost as a function
of the pipe diameter as shown
in Figure 4.2

5
 DISCRETE FUNCTIONS

•For most purposes such a cost function can be approximated as

a continuous function because of the relatively small
differences in available pipe diameters.
Chapter 4

•You can then disregard the discrete nature of the function and
optimize the cost as if the diameter were a continuous variable.

6
 DISCRETE FUNCTIONS

•If linear interpolation is used, then the extended function

usually has discontinuous derivatives at each of the original
diameters, as shown in Figure 4.3.
Chapter 4

•A remedy is to interpolate with quadratic or cubic functions

chosen so that their first derivatives are continuous at the break
points. Such functions are called splines.
•Once the optimum value of the diameter is obtained for the
continuous function, the discretely valued diameter nearest to
the optimum that is commercially available can be selected.

7
 4.2 NLP PROBLEM STATEMENT

•A general form for a nonlinear program (NLP) is

Chapter 4

•In this problem statement,

x : is a vector of n decision variables (x1, . ..,xn),
f : is the objective function, and
gi: are constraint functions.
The ai and bi are specified lower and upper bounds on the
constraint functions with ai<bi, and
8
 4.2 NLP PROBLEM STATEMENT

•A general form for a nonlinear program (NLP) is

Chapter 4

lj, uj : are lower and upper bounds on the variables with lj<uj.
If ai=bi, the ith constraint is an equality constraint.
•Problem 4.1 is nonlinear if one or more of the functions f, g1, .
. .,gn , are nonlinear.
•It is unconstrained if there are no constraint functions gi, and
no bounds on the xi, and
9
 4.2 NLP PROBLEM STATEMENT

•In linearly constrained problems all constraint functions gi are

linear, and the objective f is nonlinear.
•A linearly constrained problem with a quadratic objective is
Chapter 4

called a quadratic program (QP).

10
 4.2 NLP PROBLEM STATEMENT

•A vector x is feasible if it satisfies all the constraints. The set

of all feasible points is called the feasible region F.
• If F is empty, the problem is infeasible
Chapter 4

• A point (vector) x* is termed a local extremum (minimum) if

for all x in a small neighborhood (region) N in F around x* with

x distinct from x*.

11
 4.2 NLP PROBLEM STATEMENT

•Despite the fact that x* is a local extremum, other extrema may

exist outside the neighborhood N, meaning that the NLP
problem may have more that one local minimum if the entire
Chapter 4

space of x is examined.
•A global minimum occurs if Equation (4.2) holds for all x∈F.

12
 NLP GEOMETRY

•A typical feasible region for a problem with two variables and

the constraints
Chapter 4

•is shown as the unshaded region in Figure 4.4.

•Its boundaries are the straight and

curved lines xj=0 and gi(x)=0 for
i=1,2, j= 1,2.

13
Chapter 4 FUNCTION PLOT

14
Chapter 4 surf(x1,x2,fx)

15
 surf(x1,x2,fx)

35
Chapter 4

30

25

20
f(x)

15

10

0
6

4 6
5
4
2 3
2
0 1
0
-1
-2 -2
x2
x1
16
 contour3(x1,x2,fx,30)

35
Chapter 4

30

25

20
f(x)

15

10

0
6

4 6
5
4
2 3
2
0 1
0
-1
-2 -2
x2
x1 17
Chapter 4 contour3(x1,x2,fx,30)

18
Chapter 4 contour3(x1,x2,fx,30)

19
Chapter 4 contour3(x1,x2,fx,30)

6
6
5
5
4
4
3
3
2
2
1
1

0 0

x2 -1 -1 x1

-2 -2

20
Chapter 4 contour(x1,x2,fx)

6
15 15
25
25
5 10

10

20
20

4 5
15

15
10

3
15
x2

10
5
1
10

15
0
5
15
20

20
10
-1 10
25
25
15
15 21
-2
-2 -1 0 1 2 3 4 5 6
x1
Chapter 4 contour(x1,x2,fx)

6
15 15
25
25
5 10

10

20
20

4 5
15

15
10

5
3
15
x2

10
5
1
10

15
0
5
15
20

20
10
-1 10
25
25
15
15
-2
-2 -1 0 1 2 3 4 5 6
x1 22
 surfc(x1,x2,fx)

35
Chapter 4

30

25

20
f(x)

15

10

0
6

4 6
5
4
2 3
2
0 1
0
-1 23
-2 -2
x2
x1
 NLP GEOMETRY-EXAMPLE

•As another example, consider the problem

Chapter 4

24
Chapter 4 NLP GEOMETRY-EXAMPLE

25

20

15
6
f(x)

X: 3
10 Y: 4
5
Z: 0

4
5
3

0 2
8
7 1
6
5
4 3
2 x1
1 0
0
x2

25
 NLP GEOMETRY-EXAMPLE

25
Chapter 4

20

15
f(x)

10

5 X: 3
Y: 4
Z: 0 6
4
0 2
8 7 6 5 4 3 2 1 0
0
x1
x2

26
 25

20

15
X: 3
f(x)

10 Y: 4 6
Z: 0

5
4
0
8 2
6
4
2 x1
0 0
x2

27
 NLP GEOMETRY-EXAMPLE

•As another example, consider the problem

Chapter 4

28
29
 NLP GEOMETRY-2 DIMENSIONAL
7

6
Chapter 4

4
x2

3
X: 2
Y: 3
Z: 2

0
0 1 2 3 4 5 6 7
x1 30
Chapter 4 NLP GEOMETRY-2 DIMENSIONAL

31
Chapter 4 NLP GEOMETRY

•The feasible region is defined by linear constraints with a

finite number of corner points.
•The objective function, being nonlinear, has contours (the
concentric circles, level sets) of constant value that are not
32
parallel lines.
Chapter 4 NLP GEOMETRY

•The minimum value of f corresponds to the contour of

lowest value having at least one point in common with the
feasible region, that is, at x1*=2, x2*=3.
• 33
Chapter 4 MATLAB-FMINCON

34
Chapter 4 MATLAB-FMINCON

35
Chapter 4 MATLAB-FMINCON

36
Chapter 4 MATLAB-FMINCON

37
 •objective function f, with
two minima as shown in
Figure 4.7.
Chapter 4

•Note that the minimum at the boundary point x1=3, x2=2 is the
global minimum at f=3; the feasible local minimum in the
interior of the constraints is at f=4.
38
 4.3 CONVEXITY AND ITS APPLICATIONS

•Convex set
• A set of points (or a region) is defined as a convex set in n-
dimensional space if, for all pairs of points x1 and x2 in the set,
Chapter 4

the straight-line segment joining them is also entirely in the set.

Figure 4.9 illustrates the concept in two dimensions.

39
Chapter 4 CONVEX SET

40
 CONVEX SET

•The convex region may be closed (bounded) by a set of

functions, such as the sets A and B in Figure 4.9
Chapter 4

41
 CONVEX SET

•The convex region may be open (unbounded) as in Figure

4.12. Also, the intersection of any number of convex set is a
convex set.
Chapter 4

42
 CONVEX SET
•A mathematical statement of a convex set is:
•For every pair of points x1 and x2 in a convex set, the point x
given by a linear combination of the two points
Chapter 4

x = γx1+(1- γ)x2 0 ≤ γ≤1

is also in the set.

43
 CONVEX FUNCTION
A function f(x) defined on a convex set F is said to be a convex
function if the following relation holds
Chapter 4

where γ is a scalar with the range 0 ≤ γ ≤1.

If only the inequality sign holds, the function is said to be not
only convex but strictly convex.

If f(x) is strictly convex, -f (x) is strictly concave.

44
Chapter 4 CONVEX FUNCTION

A convex function cannot have any value larger than the values
of the function obtained by linear interpolation between x1 and
x2 (the cord between x1 and x2 shown in the top figure in Figure
45
4.10).
 CONVEXITY
Figure 4.10 illustrates both a strictly convex and a strictly
concave function.
Chapter 4

Linear functions are both convex and concave, but not strictly
convex or concave, respectively. 46
 CONVEX FUNCTION

An important result of convexity is

Chapter 4

The result is illustrated in Figure 4.11

47
Chapter 4 NLP GEOMETRY

In Fig. 4.11 a convex quadratic function is cut by the plane

f(x)=k. The convex set R projected on to the x1-x2 plane
48
comprises the boundary ellipse plus its interior.
 THE CONVEX PROGRAMMING PROBLEM

An important result from the concept of convexity

• For the nonlinear programming problem called the convex
programming problem
Chapter 4

in which
(a) f(x) is a convex function, and
(b) each inequality constraint is a convex function
the following property can be shown to be true
The local minimum of f(x) is also the global minimum.
49
 THE CONVEX PROGRAMMING PROBLEM

•Analogously, a local maximum is the global maximum of f (x)

if the objective function is concave and the constraints form a
convex set.
Chapter 4

50
 HESSIAN MATRIX

•For a scalar function, the matrix of second derivatives, called

the Hessian matrix, is.
Chapter 4

•H is symmetric.
If f has continuous second partial derivatives, then

51
 LEADING PRINCIPAL MINORS

A principal minor of order k (of Qn×n ) is

a submatrix found by deleting any n-k columns (and their
corresponding rows) from the matrix A.
Chapter 4

The leading principal minor of order k (Δk) is found by deleting

the last n-k columns and rows.

•The determination of convexity and concavity could be done

52
by using the determinants of principal minors of hessian matrix.
Chapter 4 LEADING PRINCIPAL MINORS

•the 1st order leading principal minor

•the 2nd order leading principal minor

•the 3rd order leading principal minor

•the 3rd order leading principal minor

53
 LEADING PRINCIPAL MINORS

For Example, for

1 2 1
 2 1 1
 
0 0 1
Chapter 4

•the leading principal minor (order 1) is 1 (A1=[1]);

•the leading principal minor (order 2) is

1 2 
A2   
2 1  1 2 1
 
•the leading principal minor (order 3) is itself. A3   2 1 1
0 0 1
54
 VECTOR-MATRIX PRODUCTS

(xn×1 and yn×1 are n-component vectors)

Chapter 4

•Equation is referred to as the inner product, or dot product, of

two vectors.

•If the two vectors are orthogonal, then xTy=0. This means that
the vectors x and y are perpendicular to each other.

55
 CONVEX FUNCTION

3. xTAx
Here A is a square matrix of dimension n×n and the product is a
scalar. Q=xT1×nAn×nxn×1
Chapter 4

If A is a diagonal matrix, then

xTx is a matrix rather than a scalar 56

 QUADRATIC FORMS

A quadratic form in the variables x1, x2, . . . , xn is a polynomial

function Q where all terms in the functional expression x1, x2, .
. . , xn have order two.
Chapter 4

Q(x1, x2, x3) = x12 + x22 + 3x2x3− x32 is a quadratic form in three
variables
f(x1, x2) = x12 − x22 + 3x1+ 2x2 is polynomial of degree two but
not a quadratic form.

57
Chapter 4 QUADRATIC FORMS

58
 QUADRATIC FORMS

Consider a function f given by f =x12−6x1x2+9x22.

We call f a quadratic form in two variables. We can write f in
matrix notation as
Chapter 4

1  2 6  x1 
f   x1 x2    x 
2  6 18  2 
If x is an n-vector, then the general expression for a quadratic
form is f =1/2xTAx, where A is a symmetric matrix.
A quadratic form can also be expressed in index notation as

59
 QUADRATIC FORMS

We can write f in quadratic form as

1  2 6  x1 
f   x1 x2    x 
Chapter 4

2  6 18  2 

 1 3  x1 
f   x1 x2 12   x 
 3 9  22  2 21

 x1 
 x1  3x2 3x1  9 x2 12    x12  3x2 x1  3x1 x2  9 x22
 x2 21
f  x12  6 x1 x2  9 x22

60
 GRADIENT VECTOR

The gradient vector (nabla symbol, ∇), is the vector of the first
partial derivatives of f(x) as follows
Chapter 4

61
 QUADRATIC FORMS,GRADIENT VECTOR, HESSIAN

It can easily be verified by direct computations that the gradient

vector and hessian matrix of a quadratic form can be
written as follows:
Chapter 4

62
 QUADRATIC FORMS
1 T
f  x  6 x1 x2  9 x2  x Ax
1
2 2

2
Find A
Chapter 4

A  Hessian matrix

f
 2 x1  6 x2
x1
f
 6 x1  18 x2
x2

  2f  2f 
 x 2 x 1x 2   2 6 
A H  2 
1

 f 
 f   6 18 
2

 2 
 x 2 x 1 x 2  63
 QUADRATIC FORMS

f  4 x12  x1 x2  5x22  2 x1 x3  4 x2 x3  6 x32  3x1 x4  5x2 x4  6 x3 x4  7 x42

 f x1   8 x1  x2  2 x3  3x4 
f x2    x1  10 x2  4 x3  5 x4 
f ( x )   
Chapter 4

Gradient  f x3   2 x1  4 x2  12 x3  6 x4 
   
f x4   3x1  5 x2  6 x3  14 x4 

  2 f x12  2 f x1x2  2 f x1x3  2 f x1x4   8 1 2 3 

 2  
  f x2x1  2 f x22  2 f x2x3  2 f x2x4   1 10 4 5 
Hessian H ( x)  2
  f x3x1  2 f x3x2 

2 4 12 6 
 2 f x32  f x3x4
2

 2   
 f x4x1  f x4x2
2
 2 f x4x3  2 f x42   3 5 6 14 

 8 1 2 3 
 1 10 4  5 
A 
2 4 12 6 
 
 3  5 6 14 

64
 TYPES OF QUADRATIC FORM
a quadratic form is positive definite if
Q=xTAx>0 for any nonzero vector x, and Q=xTAx=0 for vector
x=0 (also, A is called positive definite)
Chapter 4

65
 TYPES OF QUADRATIC FORM

a quadratic form is positive semidefinite if Q=xTAx≥0 for any

nonzero x. (also, A is called positive semidefinite)
Chapter 4

66
 TYPES OF QUADRATIC FORM

a quadratic form is negative definite if Q=xTAx<0 for any nonzero

x. A is negative definite if (−A) is positive definite.
Chapter 4

67
 TYPES OF QUADRATIC FORM

a quadratic form is negative semidefinite if Q=xTAx≤0 for any

nonzero x.
Chapter 4

68
 TYPES OF QUADRATIC FORM

a quadratic form is called indefinite if xTAx>0 for some

nonzero x and xTAx<0 for some other nonzero x.
Chapter 4

69
 TYPES OF QUADRATIC FORM

For a small sized matrices, Sylvester’s test, given below is

useful for checking whether a matrix is positive definite.
Chapter 4

Matrix A is positive definite if and only if the determinants of

all leading principal minors are positive.

70
Chapter 4 TYPES OF QUADRATIC FORM

71
 TYPES OF QUADRATIC FORM

For
4 2 0
2 9 0
 
0 0 2 
Chapter 4

4 2
A1  4  4 A2   32
2 9

4 2 0
A3  2 9 0  2(4  9  2  2)  64
0 0 2

72
 TYPES OF QUADRATIC FORM

For
2 0 2
0 4 4 
 
 2 4 6 
Chapter 4

2 0
A1  2  2 A2  8
0 4

2 0 2
A3  0 4 4  0
2 4 6

73
 EIGENVALUE TEST FOR DETERMINING THE SIGN OF A
QUADRATIC FORM
•All eigenvalues of a positive definite matrix are strictly
positive (λi>0 i=1,2,…,n).
Chapter 4

•All eigenvalues of a positive semidefinite matrix are

nonnegative (λi ≥ 0 i=1,2,…,n).
All eigenvalues of a negative definite matrix are negative (λi<0
i=1,2,…,n).
All eigenvalues of a negative semidefinite matrix are
nonnegative (λi≤0 i=1,2,…,n).

Indefinite if λi≤0 for some i and λi ≥ 0 for others. 74

Chapter 4 QUADRATIC FORMS

75
Chapter 4 Determination of convexity an concavity

76
 EXAMPLE 4.4 DETERMINATION OF POSITIVE-
DEFINITENESS OF A FUNCTION
Chapter 4

77
 f ( x ) 
 2 x1  x2  0 
1  2  x1  
  indefinite Hessien   x  (2, 4)
f ( x )
Chapter 4

 2  1  x1  2  0 
x2 

6
x 10

6
x 10 5

6 4
5
3
4
f(x)
3 2
f(x)

2
1
1
0
0
2000
-1 -1
2000 1000 2000
1000 0 0
0
-1000 -2000 -1000 -500 0 500 1000
78
1500 2000
-1000 -2000 -1500
-2000 -2000 x2
x2 x1 x1
 EXAMPLE: DETERMINATION OF CONVEXITY AND
CONCAVITY
Determine whether the following functions are convex or
concave.
Chapter 4

79
Chapter 4 CONVEX FUNCTION

80
Chapter 4 CONVEX FUNCTION

81
 4.5 NECESSARY AND SUFFICIENT CONDITIONS FOR AN
EXTREMUM OF AN UNCONSTRAINED FUNCTION

•Figure 4.16 illustrates the character of f(x) if the objective

function is a function of a single variable.
Chapter 4

82
 4.5 NECESSARY AND SUFFICIENT CONDITIONS FOR AN
EXTREMUM OF AN UNCONSTRAINED FUNCTION
Chapter 4

•An optimal point x* is completely specified by satisfying what

are called the necessary and sufficient conditions for optimality.

83
 NECESSARY CONDITION FOR AN EXTREMUM OF AN
SINGLE FUNCTION

•Let f be a real valued function defined on a domain

D. If f has a local extremum at an interior point c∈D, and if f ′
Chapter 4

is defined at c, then

df ( x)
f (c)  0
dx c

Proof.
•To show that f ′ (c) is zero at a local extremum, we show first
that f ′ (c) cannot be positive and second that it cannot be
negative. The only number that is neither positive or negative is
zero, so that is what f ′ (c) must be. 84
 NECESSARY CONDITION FOR AN EXTREMUM OF AN
SINGLE FUNCTION
•Suppose that f has a local maximum value at x=c so that
f(x)-f(c)≤ 0 for all values of x sufficiently close to c.
Chapter 4

• Since c is an interior point of domain D, f ′ (c) is defined by

f ( x )  f (c )
lim
x c xc
This means that the right-hand side and left-hand side limits
both exist at c and equal f ′ (c). When we examine these limits
separately, we find that

85
 NECESSARY CONDITION FOR AN EXTREMUM OF AN
SINGLE FUNCTION

•Similarly,
Chapter 4

•Therefore f ′ (c) = 0.
•The proof for minimum values is similar.

86
 NECESSARY CONDITION FOR AN EXTREMUM OF A TWO
VARIABLES FUNCTION

A necessary condition for a function f(x,y) of two variables to

have a maxima or minima at point (x*, y*) is that
Chapter 4

f
0
x (x*, y*)

f
0
y (x*, y*)

at the point (i.e. that the point be a stationary point).

87
 NECESSARY CONDITION FOR AN EXTREMUM OF A
MULTIPLE VARIABLES FUNCTION

A necessary condition for point point x*:(x1*, x2*, ... , xn*)T to be

a stationary point for the function f(x) is that the gradient of f(x)
Chapter 4

at x* equals zero:

 f (x) 
 x 
 1 
 f (x) 
f (x)   x2   0
 
 
 f ( x ) 
 xn 
88
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A
SINGLE VARIABLES FUNCTION

dy 1 d2y
y ( x)  y( x0 )   x  x0    x  x0   Higher Order Terms
2
2
dx x  x0 2! dx x  x0
Chapter 4

dy
x0 : Stationary Po int  0
dx x  x0

1 d2y
y ( x)  y ( x0 )   x  x0 
2

2! dx 2 x  x0

1 d2y
y ( x)  y ( x0 )   x  x0 
2

2! dx 2 x  x0 0
0

d2y
Local Minimum : y( x)  y( x0 )  0   0 Convex functuion
dx 2 x  x0

d2y
Local Maximum : y( x)  y( x0 )  0   0 Concave functuion
dx 2 x  x0 89
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A
SINGLE VARIABLES FUNCTION

d2y
0 unknown (We Can't judge)
dx 2 x  x0
Chapter 4

d2y 1 d3y
 0  y ( x)  y ( x0 )   x  x0 
3

dx 2 x  x0
3! dx3 x  x0

d3y 1 d4y
 0  y ( x)  y ( x0 )   x  x0 
4

dx3 x  x0
4! dx 4 x  x0

d4y 1 d5y
 0  y ( x)  y ( x0 )   x  x0 
5

dx 4 x  x0
4! dx5 x  x0

90
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A
SINGLE VARIABLES FUNCTION
Chapter 4

d2y d3y d n 1 y
 3   n 1 0
dx 2 x  x0
dx x  x0
dx x  x0

dny
0
dx n x  x0

1 dny
y ( x)  y ( x0 )   x  x0 
n

n ! dx n x  x0
Sign
Sign

91
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A
SINGLE VARIABLES FUNCTION

1 dny
y ( x)  y ( x0 )   x  x0 
n

n ! dx n
Chapter 4

Sign x  x0

Sign

n : even   x  x0   0
n

dny
 0  y ( x0 ) is min imum
dx n x  x0

dny
 0  y ( x0 ) is max imum
dx n x  x0

92
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A
SINGLE VARIABLES FUNCTION

1 dny
y ( x)  y ( x0 )   x  x0 
n

n ! dx n
Chapter 4

Sign x  x0

Sign

n : odd

x  x0   x  x0   0
n

x  x0   x  x0   0
n

infelection point
93
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A
SINGLE VARIABLES FUNCTION
•Suppose x* is a stationary point, f '(x*=0).
•Let n be the first higher order derivative that is not zero. The
Chapter 4

following conclusions can be made:

1. If n is even, then x* is a local optimum. Moreover

•If f n (x*)> 0 then x* is a local minimum
•If f n (x*)< 0 then x* is a local maximum

•2. If n is odd, then x* is neither a maximum nor a minimum. It

is an inflection (saddle) point. 94
 Example: Optimum points of a polynomial

•Consider the function : f(x) = 12x5 + 45x4 + 40x3

•The first derivative is :
f ' (x) = 60x4 + 180x3 + 120x2 = 60x2(x+1)(x+2)
Chapter 4

•The roots of f'(x)=0 are 0,−1,−2. These are the stationary

points.
•The second derivative of f is:
f″(x) = 240x3 + 540x2 + 240x
Evaluating the derivatives at the stationary points gives:
f″(0) = 0, f″(− 1)= 360, f ''(−2) = −240
It can be concluded that x = −1 is a local minimum and x = −2
95
is a local maximum.
 VECTOR NORM

•However, no conclusion can be reached for x=0. To

characterize this point, the third derivative needs to be
Chapter 4

evaluated:
f '''(x) = 720x2 + 1080x +240
f '''(0) =240 ≠ 0
Since the non zero highest derivative has an odd order (n=3), it
can be concluded from the theorem that x=0 is not an optimum
but an inflection (saddle) point.

96
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A TWO
VARIABLES FUNCTION

The Taylor Series of f (x,y) around (x*,y*) which we know to be

a stationary point is
Chapter 4

 f f
f  f    ( x  x )  ( y  y )
( x, y ) (x ,y )
x ( x , y  ) y ( x , y  )

1  2  f
2
   f
2
 2  f 
2
  (x  x )  2( x  x )( y  y )  (y  y )   ...
2!  x 2 xy y 2  ( x , y )

x  ( x  x ) & y  ( y  y  )

f f
f  f ( x , y  )
 x  y
( x, y )
x ( x , y  ) y ( x , y  )

1  2 2 f 2 f 2  f 
2
  x  2xy  y 2 
 ...
2!  x 2
xy y  ( x , y ) 97
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A TWO
VARIABLES FUNCTION

 2 f 2 f 
 x 2 xy 
 f f   x  1  x 
f  f   x      x y   2  y   ...
( x, y ) ( x , y  )
 y  ( x , y )  y  2  f  f   
Chapter 4

 
 xy y 2  ( x , y )

98
 4.5 SUFFICIENT CONDITIONS FOR AN EXTREMUM

•The taylor series expansion of f(x) about the presumed

extremum x*
Chapter 4

•where Δx = x-x*, the perturbation of x from x*. We assume all

terms in Equation (4.4) exist and are continuous, but will ignore
the terms of order 3 or higher [O3(Δx)].
•The necessary condition for a minimum or maximum of f(x) is
that the gradient of f(x) vanishes at x*

99
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A TWO
VARIABLES FUNCTION

•the third term establishes the character of the stationary point

(minimum, maximum, or saddle point).
Chapter 4

1 T

f (x)  f (x )   Δx H(x )Δx
2

x* is a local minimum if

•Similarly, x* is a local maximum if

100
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A TWO
VARIABLES FUNCTION

(a) If the Hessian matrix is positive definite, the stationary point

is a minimum.
Chapter 4

(b) If the Hessian matrix is negative definite, the stationary

point is a maximum.
(c) If the Hessian matrix is indefinite, the stationary point is a
saddle point.
(c) If the Hessian matrix is semi-definite, no conclusion about
the nature of the stationary point.

101
 SUFFICIENT CONDITION FOR AN EXTREMUM OF A TWO
VARIABLES FUNCTION
•we have the following outcomes
Chapter 4

102
 EXAMPLE

A container with an open top is to have 10 m3 capacity and be

made of thin sheet metal. Calculate the dimensions of the box if
it is to use the minimum possible amount of metal.
Chapter 4

Solution: Let A be the total area of metal used to make the box,
and let x and y be the length and width and z the height. Then
A=2xz+2yz+xy
Also
xyz = 10

103
 EXAMPLE
because the volume is 10 m3. This implies that z=10/xy .Putting
this into the formula for A gives:
Chapter 4

and for a stationary point we need ∂A/∂x = ∂A/∂y = 0. this

gives

104
 EXAMPLE

Since the zero root y=0 is obviously not consistent with having
Chapter 4

a volume of 10 m3 we reject y=0 and conclude that y3=20 so

that y=201/3=2.714 metres. From x=20/y2 we conclude x=2.714
metres also. To find z, use z=10/xy so that z=1.357m.
We have to show that these values do indeed give a minimum.
Now

105
 EXAMPLE

 2 A  2 A   40
Chapter 4


 x 2 xy   x3
1
H  2  
 A  A  1
2 40 
 2 
 yx y   y 3 

 40 
 2.1743 1  2 1
H     1  2  0,  2  2  2  11  3  0
 1 40  1 2 
 2.1743 
106
 EXAMPLE: CALCULATION OF EXTREMA

Identify the stationary points of the following function, and

determine if any extrema exist.
f ( x)  x13  x23  2 x12  4 x22  6
Chapter 4

f ( x )  (0, 0)
 3x1  4 x1  x1 (3x1  4)  0 
2
(0, 8 / 3)
x1   
  x  
f ( x )   (4 / 3, 0)
 3x2  8 x2  x2 (3x2  8)  0
2

x2  (4 / 3, 8 / 3)

 2 f ( x)
 6 x1  4
x12
 2 f ( x)
0
 2 f ( x) x1 x2
 6 x2  8
x22
107
 EXAMPLE: CALCULATION OF EXTREMA

  2 f ( x)  2 f ( x) 
 x 2 x1 x2  6 x1  4 0 
H ( x)   2 1  
  f ( x)  2 f ( x )  0 6 x2  8
 
Chapter 4

 x1 x2 x22 

4 0
H ( x ) x (0,0)   
0 8 


H1  4  0 

H 2  4  8  0  32  0
2
 H is Pos. Def. (0,0) is min point,f(0,0)=6

4 0 1  4 
0
0 8 2  8

108
 EXAMPLE: CALCULATION OF EXTREMA

  2 f ( x)  2 f ( x) 
 x 2 x1 x2  6 x1  4 0 
H ( x)   2 1  
  f ( x)  2 f ( x )  0 6 x2  8
 
 x1 x2 x22 
Chapter 4

4 0 
H ( x ) x (0, 8 )   
3 0 8


H1  4  0 
 418
H 2  4  8  0  32  0
2
 H is Indefinite. (0,-8/3) is saddle point,f(0,-8/3)=
 27
4 0   4 
0 1
0 8   2  8

109
 EXAMPLE: CALCULATION OF EXTREMA

  2 f ( x)  2 f ( x) 
 x 2 x1 x2  6 x1  4 0 
H ( x)   2 1  
  f ( x)  2 f ( x )  0 6 x2  8
 
 x1 x2 x22 
Chapter 4

 4 0 
H ( x ) x (  4 ,0)   
3 0 8 


H1  4  0 
 4 418
H 2  4  8  0  32  0
2
 H is Indefinite. (- ,0) is saddle point,f(0,-8/3)=
 3 27
4   0   4 
0 1
0 8 2  8 

110
 EXAMPLE: CALCULATION OF EXTREMA

  2 f ( x)  2 f ( x) 
 x 2 x1 x2  6 x1  4 0 
H ( x)   2 1  
  f ( x)  2 f ( x )  0 6 x2  8
Chapter 4

 
 x1 x2 x22 

 4 0 
H ( x ) x  (  4 ,  8 )   
3 3 0 8


H1  4  0  H is Negetive Definite

H 2  4  8  02  32  0  4 8 4 8
 (  ,  ) is local maximum point,f(  ,  )=6
4   0   4  3 3 3 3
0 1
0 8   2  8

111
 EXAMPLE 4.11 CALCULATION OF EXTREMA

Identify the stationary points of the following function, and

determine if any extrema exist.
Chapter 4

f ( x)  4  4.5x1  4 x2  x12  2 x22  2 x1 x2  x14  2 x12 x2

f ( x ) 
 4.5  2 x1  2 x2  4 x13  4 x1 x2  0 
x1 

f ( x ) 
 4  4 x2  2 x1  2 x12  0
x2 

112
Chapter 4 EXAMPLE 4.11 CALCULATION OF EXTREMA

 (1.94,3.85)

 x   (1.05,1.03)
 (0.61,1.49)

113
 EXAMPLE 4.11 CALCULATION OF EXTREMA

f ( x )
 4.5  2 x1  2 x2  4 x13  4 x1 x2  0
x1
f ( x )
Chapter 4

 4  4 x2  2 x1  2 x12  0
x2

 2 f ( x)
 2  12 x1  4 x2
2

x12

 2 f ( x)
 4
 2 f ( x) x22

 2  4 x1
x1 x2

114
 EXAMPLE 4.11 CALCULATION OF EXTREMA

  2 f ( x)  2 f ( x) 
 x 2 x1 x2   2  12 x12  4 x2 2  4 x1 
H ( x)   2 1  
  f ( x)  f ( x)
2   2  4 x1 4 
 
Chapter 4

 x1 x2 x22 

31.76 9.76
H ( x ) x (1.94,3.85)   
 9.76 4 
H1  31.794  0
H 2  31.76  4  9.762  31.78  0

31.76   9.76 1  0.91

0
9.76 4 2  34.85

115
 EXAMPLE 4.11 CALCULATION OF EXTREMA

  2 f ( x)  2 f ( x) 
 x 2 x1 x2   2  12 x12  4 x2 2  4 x1 
H ( x)   2 1  
  f ( x)  2 f ( x )   2  4 x1 4 
 
 x1 x2 x22 
Chapter 4

11.11 2.2 
H ( x ) x ( 1.05,1.03)  
 2.2 4 
H1  11.11  0
H 2  11.11 4  2.22  39.6  0

11.11   2.2 1  3.37

0
2.2 4 2  11.74
116
 EXAMPLE 4.11 CALCULATION OF EXTREMA

  2 f ( x)  2 f ( x) 
 x 2 x1 x2   2  12 x12  4 x2 2  4 x1 
H ( x)   2 1  
  f ( x)  f ( x)   2  4 x1
Chapter 4

2
4 
 
 x1 x2 x22 

0.505 4.44
H ( x ) x (0.61,1.49)  
 4.44 4 
H1  0.505  0
H 2  0.505  4  4.442  17.69  0

0.505   4.44 1  2.52

0
4.44 4 2  7.02
117
Chapter 4 EXAMPLE 4.11 CALCULATION OF EXTREMA

118
Chapter 4 FMINUNC

119
Chapter 4 FMINUNC

120
Chapter 4 FMINUNC

121
Chapter 4 FMINUNC

122
Chapter 4 EXAMPLE

123
 4.4 INTERPRETATION OF THE OBJECTIVE FUNCTION IN
TERMS OF ITS QUADRATICAPPROXIMATION

•If a function of two variables is quadratic or approximated by a

quadratic function
Chapter 4

Then the eigenvalues of H(x) can be calculated and used to

interpret the nature of f(x) at x*. Table 4.2 lists some
conclusions that can be reached by examining the eigenvalues
of H(x) for a function of two variables, and Figures 4.12
through 4.15 illustrate the different types of surfaces
corresponding to each case that arises for quadratic function.
124
By
 Chapter 4

125
Chapter 4 ELLIPTICAL-CIRCULAR CONTOURS

126
Chapter 4 HYPERPBOLIC CONTOURS

127
Chapter 4 HYPERPBOLIC CONTOURS

128
 Chapter 4

129
The End

130