So I am learning to do SDP relaxation on graph problems, and for this max cut problem I am given a 500*500 graph, and I am using the straightforward relaxation. $W$ is the weight matrix, $X = u u^T$ where $u$ is the original variables.

$$ \max < (I-W),X> $$ $$ s.t. X_{ii} = 1, \forall i$$ $$ X \succeq 0$$

Problem is:

The solver I am using is CVXOPT, for which I have to convert X into a REALLY long variable, and for CVXOPT I have to paraphrase the constraint into huge matrices (largest ~ 250000 * 125250, but sparse), and load them into the cvxopt.solver.sdp(), but at this line python simply gives up and crashes (jupyter notebook says the kernel has died). I have used CVXOPT's sparse matrix feature for the massive constraint matrices (cost vector must be dense), and it's still not working out.

So my question is: is there any way to work around this? I'm open to anything, rephrasing the problem, using a different solver, or maybe just write the damped newton method for log barrier method myself. I am contemplating about CVXPY, but seeing that it uses CVXOPT as one of its solvers, I don't think I want to waste my time if it's gonna come out the same, and similar reason for writing my own program.

  • $\begingroup$ When you say 500*500 graph, do you mean the graph has 500 vertices? $\endgroup$
    – Juho
    Feb 28 '18 at 7:12
  • $\begingroup$ This seems more appropriate for Computational Science. $\endgroup$ Feb 28 '18 at 7:56
  • $\begingroup$ yeah sorry, I meant 500 vertices (500*500 adj matrix) $\endgroup$
    – Donnie
    Feb 28 '18 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.