Semidefiniteness Error by CVX

(ata) #1

Hello,
My objective function is y’Ky + y’*L, which is quadratic. I know that in order this to be convex, K must be positive semidefinite.

In my case K is a sparse 25x25 matrix and its eigen values are roughly:
1st eigen value: 1000
2nd eigen value: 1
3rd eigen value: 0.5
4th eigen value: 0.2
and the rest is all zero.

I get an an error from function quad_form(), when i run cvx:
“The second argument must be positive or negative semidefinite”.

Even though all eigen values are non negative, how do i not have semidefinite matrix of K.

My code is
cvx begin
variable y(25,1)
minimize y’Ky + y’*L
cvx end

Ps: There are some constraint equalities as well, but they dont affect whether I get this error or not.

(Mark L. Stone) #2

It’s possible that one or more eigenvalues evaluate to be very slightly negative (I don’t know exactly how CVX is evaluating definiteness), thereby triggering the error. What does min(eig(K)) evaluate to? From a practical perseptive, you may be in precarious territory if chol(K) fails.

Perhaps you can add a very small positive number to the diagonal to make it numerically psd.

(ata) #3

Alright, that’s what I thought at first but min(eig(K))>=0 turns true whereas min(eig(K)) is equal to perfect 0.

Also the matrix K can be written as R*R’ and hence chol(K) does not fail.

I also tried changing scale of the parameters so that K would be different, (i.e. km/h to m/s etc). But that didn’t help.

(Mark L. Stone) #4

min(eig(K)) exactly being zero makes it precarious. Try K + small_number*eye(25) instead of k for small_number equal to 1e-6 or so.

(Mark L. Stone) #5

If you have the factorization K = R*R', you can reformulate y'*K*y as
x = R’*y
x’*x

CVX is sure to accept that.

(ata) #6

Thank you very much, it works!

(ata) #7

So the code is:

K = K +epseye(25);
A = chol(K);
b = 0.5
pinv(A)*L;

cvx_begin
variable x(25,1)
minimize norm(A*x+b,2)
cvx_end

I kind of turn the objective function into LS

(Erling D.Andersen) #8

You write you know K=RR’. Why not just let A=R’. Of course you have to figure out b.

If you do that you save chol(K).