Optimization output does not satisfy a semidefinite constraint


The below code is simple semidefinite programming which approximates the max-cut problem. However, my output matrix X does not seem to satisfy the semidefinite constraint and has a minimum eigenvalue -1, while the constraint is satisfied until n = 999. I would be grateful if someone let me know the problem here. Thanks!

n = 1000;

A = randn(n, n);
A = A + A’;
A = A - diag(diag(A));
one = ones(n, 1);

cvx_begin sdp
variable X(n,n) symmetric
maximize(sum(dot(X, A)))
subject to
diag(X) == one
X >= 0

fprintf(‘mineigval: %f\n’,min(eig(X)))

I duplicated your experience using SDPT3. However, i obtained what appeared to be correct results using SeDuMi and Mosek. Therefore, this appears to be a bug in either SDPT3 or the CVX/SDPT3 interface. I have no further diagnosis.

1 Like

Thanks for your reply! I would use other solvers instead.