4
$\begingroup$

How could one formulate the primal SDP for MaxCut in Mathematica.

I am aware of this tutorial using the dual:

https://www.wolfram.com/language/12/convex-optimization/max-cut-problem.html?product=mathematica

Thank you.

Edit to add further information:

What I tried (there LaplacianMatrix and e are functions from the dual example):

MCSDPPrimalValueAndMinimizer[graph_?GraphQ] := 
  Module[{L = LaplacianMatrix[graph], n},
   n = Dimensions[L][[1]];
   Return[
    SemidefiniteOptimization[-Tr[1/4 L . X], 
     Join[Table[
       Tr[e[i, n] . X] == 1, {i, 1, n}], {X \[VectorGreaterEqual] 0}],
      X \[Element] Matrices[{n, n}, Reals], {"PrimalMinimumValue", 
      "PrimalMinimizer"}]];
   ];

However, the values it returns are pretty off even for even order complete graphs --- they should match the optimal values of their maxcuts.

$\endgroup$
4
  • 2
    $\begingroup$ Please include in your question the code that you have tried and what comments you encountered. $\endgroup$
    – bbgodfrey
    Jun 22 at 18:16
  • $\begingroup$ Welcome to Mathematica.SE! I hope you will become a regular contributor. To get started, 1) take the introductory tour now, 2) when you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge, 3) remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign, and 4) give help too, by answering questions in your areas of expertise. $\endgroup$
    – bbgodfrey
    Jun 22 at 18:17
  • $\begingroup$ xxxx, please take a look at: mathematica.stackexchange.com/help/merging-accounts $\endgroup$
    – Kuba
    Jun 25 at 4:20
  • $\begingroup$ Thank you bbgodfrey. Thank you Kuba --- I merged my accounts (sorry for the mess). $\endgroup$
    – xxxx
    Jun 26 at 8:04
2
$\begingroup$

More of a comment, but this looks almost correct, the main issue is that instead of

VectorGreaterEqual[{X, 0}]

you may want to use

VectorGreaterEqual[{X, 0}, {"SemidefiniteCone", n}]
$\endgroup$
1
  • $\begingroup$ Thanks a lot ilian. Yes, that works. I am grateful. $\endgroup$
    – xxxx
    Jun 26 at 8:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.