How can I convert a negative definite matrix into positive definite matrix?

20 views (last 30 days)
kartik pandya
kartik pandya on 15 Jul 2014
Edited: Matt J on 24 Jul 2014
I want to convert matrix a=[-5 2; 6 1] into positive definite matrix.
  2 Comments
Roger Stafford
Roger Stafford on 15 Jul 2014
The matrix a = [-5 2; 6 1] is not negative definite! The expression z'*a*z for the column vector z can be either positive or negative depending on z. In other words, it has both a negative and a positive eigenvalue.
What kind of conversion do you allow on 'a' while endeavoring to make it positive definite?
kartik pandya
kartik pandya on 16 Jul 2014
Hello, Thanks for you answer. I am using Modified Newton's method to minimize a function. In this method, for obtaining a descent direction the Hessian should be positive definite in every iteration. If it is Negative definite then it should be converted into positive definite matrix otherwise the function value will not decrease in the next iteration. so I am looking for any instruction which can convert negative Hessian into positive Hessian.

Sign in to comment.

Sign in to answer this question.

Accepted Answer

Roger Stafford
Roger Stafford on 18 Jul 2014
The modified Newton's method attempts to find points where the gradient of a function is zero. If the Hessian at such a point is not positive definite, this will not in general be a point of local minimum value for the function but merely a stationary point. If it has a negative eigenvalue, then it most certainly will not be a local minimum.
All this is straightforward. However, I fail to see the point in arbitrarily adjusting the Hessian to force it to be positive definite. In doing so you are no longer adhering to the modified Newton's method, which is pointless. You are not going to find the minimum this way. If you were to succeed in making the Hessian positive definite at a point of zero gradient, you might erroneously jump to the conclusion that you had already arrived at a valid local minimum.
If you find yourself at a point of zero gradient where the Hessian has one or more negative eigenvalues, you need to temporarily abandon the Newton method and proceed down in the direction of one of the corresponding eigenvectors in order to descend further until you find a valid local minimum with all positive eigenvalues. Doing this is distinctly different from arbitrarily forcing all the eigenvalues of the Hessian to be positive. Sir Isaac would turn over in his grave at the very notion.
  1 Comment
Matt J
Matt J on 18 Jul 2014
Edited: Matt J on 24 Jul 2014
If you were to succeed in making the Hessian positive definite at a point of zero gradient, you might erroneously jump to the conclusion that you had already arrived at a valid local minimum.
That's true, but there are still situations when it can make sense to compute a positive definite approximation to the Hessian. When you are not at a point of zero gradient, you still need some way of finding a direction of descent when there are non-positive eigenvalues. The Newton direction, computed from a non-positive definite Hessian, can be unreliable as a way of computing a direction of descent. Consider, for example a function which looks locally like the following at x=y=0
f(x,y)= (x^2-y^2)/2 + x + y
The non-zero gradient [1,1] at x=y=0 tells you that you are not at a local minimum, yet the Newton direction, computed from the exact Hessian and gradient, is the vector [0,0] and gives no information about where to step. The best you can do is step in the direction of the gradient or some positive definite scaling of it. This would be equivalent to taking a Newton step with some positive definite substitute for the Hessian.

Sign in to comment.

More Answers (1)

Matt J
Matt J on 18 Jul 2014
Edited: Matt J on 18 Jul 2014
You could switch temporarily to steepest descent at iterations where the Hessian is found to have negative eigenvalues. This is equivalent to replacing the Hessian with eye(N), which is of course positive definite.
Alternatively, you might be able to get better use of the Hessian if you do something similar to the Levenberg-Marquardt method, i.e., for some lambda>0
[V,D]=eig(Hessian);
d=diag(D);
Hessian=Hessian + eye(size(Hessian))*(lambda - min(d))*(d<0);
However, the best alternative might be to use an Optimization Toolbox solver, if you have it. The trust-region algorithm of fminunc, for example, can take advantage of negative Hessian eigenvalues to get further descent at zero gradient points, along the lines of what Roger was saying.
  9 Comments
Show 7 older comments
Matt J
Matt J on 23 Jul 2014
dmin=min(d);
Hessian=Hessian + eye(size(Hessian))*(lambda - dmin)*(dmin<0);

Sign in to comment.

Categories

Find more on Eigenvalues & Eigenvectors in Help Center and File Exchange

Tags

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!