Solution violates positive semidefinite constraint


#1

I am trying to solve an SDP problem where M = [n x n] symmetric matrix and k is an integer 1 <= k <= n-1 , D = [1, e'; e, eye(n-1)] where e is a vector of 1s.

cvx_begin sdp
    variable X(n,n) symmetric
    maximize(trace(M*X))
    diag(X) == 1;
    trace(D*X) == 4*k;
    X >= 0;
cvx_end

I end up with a matrix X that has a small negative eigenvalue. Is that expected? I would like to add the absolute value of this negative eigenvalue to the diagonal elements of X and use that as a PSD matrix. Are there better ways to get a completely PSD matrix X.


(Mark L. Stone) #2

This seems like a solver tolerance issue.

One approach would be to change your constraint to

X - small_number * eye(n) >= 0

where small_number is a small positive number which is just big enough to ensure that the minimum eigenvalue of the solution X is non-negative. You may have to experiment a bit to get a good value. The absolute value of your original small magnitude negative eigenvalue might be in the ballpark.

Your proposed approach would be another way, which is not all that different, except that you may possibly be increasing “non-compliance” with your other constraints. You’ll have to decide exactly how critical compliance with the various constraints is.


(Michael C. Grant) #3

I think your idea is just fine.


(Mahdi Khojastehnia) #4

Hello, I am new to CVX. So I just have read this conversation and I have a question about it.
In this CVX script, if I write:

variable X(m,n) symmetric
X==semidefinite(m,n);

and remove X >= 0; then will I get the same answer?

let me tell you my question more precisely. what is the different between ''variable R(n,n) semidefinite ‘’ and ‘‘variable R(m,n) symmetric R==semidefinite(n,n);’’.
I mean is there any differences between these two definitions as both of them mean that R is the real PSD matrix.
generally speaking, if I have one constraint that is R is PSD, how can I write it in CVX? for example which one is true?
1- variable R(n,n) complex semidefinite
2- variable R(n,n) hermitian R >= 0

Thank you for your help.


(Mark L. Stone) #5

There are multiple equivalent ways of specifying a semidefinite or hermitian semidefinite constraint. Take your choice. Use of >= 0 to impose a semidefinite or hermitian semidefinite constraint requires CVX to be in sdp mode.

Note that symmetric, hermitian, semidefinite, and hermitian_semidefinite matrices must be square.
X==semidefinite(m,n) only takes one argument of semidefinite, per the documentation, but it appears that a 2nd argument can be provided, which appears to be ignored. I recommend staying with the one argument.


(Mahdi Khojastehnia) #6

Thank you for your explanation.
In my script, m and n are equal to each other. ( I wrote R(m,n) in a case that if m and n are not equal then I will understand that sth is wrong)

So, What I understood is that no ways are preferable. Am I right? Because I am a little confused.
I mean if I just write variable R(n,n) complex semidefinite, then there is no need to mention anything related to R? By just this command, R is complex positive semidefinite and there is no need to write R <=0 or variable R(n,n) hermitian. Am I right ?!!

Thanks.


(Mark L. Stone) #7

Yes. > = 0 or == semidefinite(n) or == hermitian_semidefinite(n) are only needed if they are applied to a CVX expressions, such as a concatenated matrix, but they can also be applied to CVX variables.


(Mahdi Khojastehnia) #8

Thank you so much for your reply.
Now I get it.