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

I want to convert matrix a=[-5 2; 6 1] into positive definite matrix.

[Roger Stafford]

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]

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.

Answer 1

[Roger Stafford]

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.

[Matt J]

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.

Answer 2

[Matt J]

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.

[kartik pandya]

hello When I execute this program, an error message appears. I have taken lambda=1.

hessian is [2 3 2; 3 4 -1; 0 4 -4;]
Error in ==> Hess_Neg_pos at 9
   Hessian=Hessian + eye(size(Hessian))*((lambda - min(d))*(d<0))

[Matt J]

Should be

Hessian=Hessian + eye(size(Hessian))*((lambda - min(d))*min(d<0))

But the Hessian you've shown is non-symmetric, which shouldn't be the case.

[kartik pandya]

Ok Now i condiser symmetric matrix. Still the error exists as mentioned below

function [ Hessian ] = Hess_Neg_pos() % Detailed explanation goes here 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 lambda=1; Hessian=[-1 2 3; 2 8 10; 3 10 -40;] [V,D]=eig(Hessian) d=diag(D) Hessian=Hessian + eye(size(Hessian))*(lambda - min(d))*(d<0); end

   error:
??? Error using ==> plus
Matrix dimensions must agree.

Error in ==> Hess_Neg_pos at 10 Hessian=Hessian + eye(size(Hessian))*(lambda - min(d))*(d<0);

[Matt J]

I can't read your code. You need to highlight your lines of code separate from your text and hit this button:

[kartik pandya]

function [ Hessian ] = Hess_Neg_pos()

lambda=1; Hessian=[-1 2 3; 2 8 10; 3 10 -40;] [V,D]=eig(Hessian) d=diag(D) Hessian=Hessian + eye(size(Hessian))*(lambda - min(d))*(d<0); end

[Matt J]

I don't think you used the

button to format your code. The lines of code would be readably auto-spaced and be in a separate font from your text.

[Matt J]

kartik pandya Commented:

function [ Hessian ] = Hess_Neg_pos()
lambda=1;
Hessian=[-1 2 3; 2 8 10; 3 10 -40;]
   [V,D]=eig(Hessian)
     d=diag(D)
     Hessian=Hessian + eye(size(Hessian))*(lambda - min(d))*(d<0);
end

[Matt J]

 dmin=min(d);
 Hessian=Hessian + eye(size(Hessian))*(lambda - dmin)*(dmin<0);

[kartik pandya]

ok . it works. thank you for your help.