MCL 742: Design and Optimization
Handout on Positive Definiteness, Negative Definiteness, Semi-definiteness.
Let us consider a function(, ) = 2 + 2 + 2 , which can be written in matrix-vector
form as given below:
(, ) = T where = [] and = [
is a pure quadratic form.
]. For any symmetric matrix , the product T
Positive Definiteness
Now the question is, what condition on , and ensure that the quadratic form (, ) is positive
definite?
Note: The above given function (, ) will be positive definite if and only if, for any real value
of and y, the function value is positive.
(i)
If 2 + 2 + 2 is positive definite, then necessarily > 0.
If we look at = 1, = 0, then (, ) is equal to and this must be positive.
(ii)
Similarly for = 0, = 1, then (, ) is equal to and this must be positive, i.e.
> 0.
Does these conditions > 0 and > 0 guarantee that (, ) is always positive? The answer is
no because a large value of the cross term 2 can pull the function value below zero, e.g.
(, ) = 2 2 + 4 + 2 is not positive definite because at = 1 and = 1 it has the
function value equal to -1. So, what else is required for positive definiteness of this quadratic
function?
It is the size of , compared to the and , that must be controlled. Now we are looking at the
square form of the above quadratic function
(, ) = 2 + 2 + 2 = ( + (/))2 + ( 2 /) 2
The first term will never negative if > 0. But it can be zero and then second term must be
positive. The term has coefficient ( 2 /). The last requirement for positive definiteness is that
this coefficient must be positive.
(iii)
If 2 + 2 + 2 is positive definite, then necessarily > 2 .
In combination, the condition > 0 and > 2 are just right and they guarantee > 0.
Negative Definiteness
The quadratic function is negative definite if and only if < 0 and > 2 .
Singular Case = : The second term in the square form disappears to leave only the first
square- which is either positive semidefinite, when > 0, or negative semidefinite, when < 0.
The prefix semi allows the possibility that (, ) can equal zero, as it will at the point = , =
.
Saddle point <
This condition occurred when dominated and . It also occurs if and have opposite signs.
Then two directions give opposite results- in one direction increases, in the other it decreases.
These quadratic forms are indefinite, because they can take either sign. So we have a stationary
point* that is neither a maximum nor a minimum. It is called a saddle point.
*A stationary point is that at which the first derivatives of the function are zero. For pure quadratic
0
form given above, = [ ] is a stationary point.
0
Positive Definiteness of Higher Dimension Matrix
For a real symmetric matrix to be positive definite
T > 0 for all nonzero real vector .
All the eigenvalues of satisfy > 0.
All the upper left submatrices k have positive determinants.
All the pivots (without row exchanges) satisfy dk > 0.
Positive Semi-definiteness of Higher Dimension Matrix
For a real symmetric matrix to be positive definite
T 0 for all nonzero real vector .
All the eigenvalues of satisfy 0.
No principal submatrices have negative determinants.
All the pivots (without row exchanges) satisfy dk 0.
Negative Definiteness of Higher Dimension Matrix
For a real symmetric matrix to be positive definite
T < 0 for all nonzero real vector .
All the eigenvalues of satisfy < 0.
A matrix is negative definite if its k-th order leading principal minor is negative
when k is odd, and positive when k is even.
All the pivots (without row exchanges) satisfy dk < 0.
Negative Semi-definiteness of Higher Dimension Matrix
For a real symmetric matrix to be positive definite
T 0 for all nonzero real vector .
All the eigenvalues of satisfy 0
All the pivots (without row exchanges) satisfy dk 0.
