You can also use a hack to make the matrix positive definite: mineig = minimum(eigvals(M)) M -= mineig * eye(M)
(And in case you're working on max-cut you can also use M = (M - mineig * eye(M)) / (1-mineig) so that the linear constraints in the semidefinite program are still satisfied by the new matrix M.) Best, David