Lect 4 Unconstraint Optimization

Optimization of Functions of Multiple Variables: Unconstrained Optimization
Objectives
To study functions of multiple variables, which are more
difficult in graphical representation and tedious
calculations involved in mathematical analysis for
unconstrained optimization.
To study the above with the gradient vector and the
Hessian matrix.
To discuss the implementation of the technique through
examples
Necessary condition
In case of multivariable functions a necessary condition for a
stationary point of the function f(X) is that each partial
derivative is equal to zero.
 f
 x  x  
 
 1 
 f  
 x  x  
 2 
x f    0
 
  
 f 
  x 

 x n 
 
The gradient vector of f(X), at X=X*, defined as
above, must be equal to zero.
Note:
A matrix will be positive definite if all its Eigen values
are positive and the matrix will be negative definite if
its Eigen values are negative.
Another test that can be used to find the positive
definiteness of a matrix A of order n involves
evaluation of the determinants.
a 11 a1 2 a1 3
a 11 a1 2
A1  a11 A2  A3  a 2 1 a2 2 a23
a 21 a2 2
a 31 a3 2 a33
a11 a1 2 a1 3  a1 n
a 21 a2 2 a23  a2 n
An  a 3 1 a3 2 a33  a3 n

a n1 an 2 an3  an n
The matrix A will be positive definite if and only if all the
values A1, A2, A3, …. An are positive.
The matrix A will be negative definite if and only if the
sign of Aj is (-1)j for j = 1,2, …. n
If some of the Aj are positive and remaining Aj are zero,
then the matrix A will be positive semi definite.
Sufficient condition
For a stationary point X* to be an extreme point, the
matrix of second order partial derivatives (Hessian matrix)
of f(X) evaluated at X* must be:
1. Positive definite when X* is a point of relative
minimum
2. Negative definite when X* is a relative maximum point.
3. If some of the Eigen values of the Hessian at X* are
positive and some Negative, or if some are zero, the
stationary point, X*, is neither a local maximum nor a
local minimum.
EXAMPLE
Analyze the function

f  x  x  x  x  2x1 x2  2x1 x3  4x1  5x3  2
2
1
2
2
2
3
classify the stationary points as maxima, minima and
points of inflection
Solution
 f 
  
x 
 x1    2 x  2 x  2 x  4  0 
 f   1 2 3
x f    
x    2 x1  2 x 2
  0 
  
 x 2   2 x  2 x  5   0 
 f   3 1
  
x 
 x 3 
Example …contd.
Solving these simultaneous equations we get

X* =[½ ½ -2]
2 f 2 f 2 f
 2,  2,  2
 x12
x22
x32
2 f 2 f 2 f 2 f 2 f 2 f
  2,   0,  2
x1x2 x2 x1 x2 x3 x3x2 x1x3 x3x1
Example …contd.
Hessian of f(X) is
  2 2 2 2 2 2
H  2  2 0   I  H   2   2 0  0
2 0  2  2 0 2

(λ+2) (λ+2) (λ+2)-2 (2)(λ+2)+2 (2) (λ+2)= 0
 (λ+2)[ λ2 + 4 λ + 4 – 4 + 4]=0
(λ+2)3 = 0
 λ1 = -2 λ2 = -2 λ3 = -2
Since all Eigen values are negative, the function attains a
Maximum at the point [½ ½ -2]
Saddle point
In case of function of two variables, f(x, y), the Hessian
matrix may be neither negative nor positive definite at a
point (x*,y*) at which

f f
  0
x y
In such case the point (x*,y*) is called saddle point.
The characteristic of a saddle point is that it corresponds to a
relative minimum or maximum of f(x, y) with respect to one
variable, say, x (the other variable being fixed at y = y*) and
the relative minimum or maximum of f(x, y) with respect to
second variable, y (the other variable being fixed at x*)
Example
Consider the function
f  x, y   x  y
2 2
Solution:
f f
For this function,  2x  2 y
x y
The first order derivatives are zero at (0,0)

The Hessian matrix of f at (0,0) is given by
2 0 2 0
H    H  I  0
0  2 0 2
  2     2    0  4    0    2 or   2
2
Since this matrix is neither positive definite nor negative
definite the point (0,0) is saddle point.
Example
Find the extreme points of the function
f  x1, x2   x  x  2x  4x  6
3
1
3
2
2
1
2
2
 Solution:
The necessary conditions for the existence of an extreme
point are
f
 0  x1  3 x1  4   0
 x1
f
 0  x2 3 x2  8  0
x2
These equations are satisfied at the points (0,0) , (0,-8/3)
(-4/3, 0) and (-4/3,-8/3)
To find nature of these points we use sufficiency conditions.
The second order partial derivatives of f are
 f
2
 f
2
  6 x1  4    6 x2  8 
 x1
2
x 2
2
 f 2
0
 x1 x 2
Solution
The Hessian matrix of f is given by
6x1  4 0 
H  
 0 6 x2  8 
The nature of the extreme points are given below
(0,0) - positive definite – relative minimum – f (0,0) =6
(0,-8/3) - In definite – saddle point – f (0,-8/3) = 418/27
 (-4/3,0 ) - In definite – saddle point – f (-4/3,0 ) = 194/27
(-4/3,-8/3) - negative definite - relative maximum
f (-4/3,-8/3) =50/3
THANK YOU

Lect 4 Unconstraint Optimization

Uploaded by

Copyright:

Available Formats

Lect 4 Unconstraint Optimization

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lect 4 Unconstraint Optimization

Uploaded by

Copyright:

Available Formats

Optimization of Functions of Multiple Variables: Unconstrained Optimization

Analyze the function

Solving these simultaneous equations we get

The first order derivatives are zero at (0,0)

You might also like