Failed to solve SDPLib

[Nagisa Sugishita]

I would like to use Mosek to solve max-cut and graph-partitioning problems in
SDPLib (`mcp500-1` and `gpp500-1`; https://github.com/vsdp/SDPLIB). However,
when I fed data and ran Mosek, it consumed a substantial amount of memory
(please refer to the attached screenshot), eventually leading to the
termination of the process by the OS. I have included the relevant data, code,
and log messages, along with the setup details below.

Mosek Version: 10.1
Platform: Mac
API: Python Fusion
Chip: Apple M1 Pro
Memory: 32 GB
OS: macOS 14.1.1
Data and Code: Attached

I encountered a similar issue when running it on a Linux server with 64GB of
memory. I came across a paper [1] where the authors successfully solved
identical instances on a machine with the same memory size (64GB). So I suspect
I did something wrong and failed to solve the instances.

[1] https://arxiv.org/pdf/1901.10887.pdf

Could you help me figure out what went wrong? I appreciate any comments or
feedback. Thank you very much for your help in advance.

Best regards,
Nagisa

[Michal Adamaszek]

You have a large and very sparse LMI, so the correct approach is to solve it in dual form to avoid a huge number of constraints. You are exactly in the situation as in example 8.7 here:

https://docs.mosek.com/modeling-cookbook/duality.html#semidefinite-duality-and-lmis

When Mosek has an automatic dualizer for SDPs it will do it for you internally. Until then you can either formulate and input the dual yourself, and then extract the dual solution as the original primal and vice versa, or use some modeling tool that dualizes before calling Mosek and does this work transparently for you. I think each of CVX, Yalmip, CVXPY would do it for you in this case.

Michal

[Nagisa Sugishita]

Dear Michal,

Thank you for your quick and kind reply. I provided the dual problem to Mosek,
and it quickly solved the problem. I really appreciate your help. I have
attached the code in case someone finds it useful in the future.

I have noticed a few instances in this forum where feeding the dual of a
problem significantly helps the solver. However, I do not understand when and
why this happens. If it is not too much trouble, could you point me to some
materials explaining these points?

Best regards,
Nagisa

[Michal Adamaszek]

The key point is that the memory and time complexity of the Mosek algorithm for SDP grows quickly with the number of linear constraints that contain semidefinite variables, so it is best to choose a formulation which minimizes the number of such constraints. This is related to the Schur complement, see in http://docs.mosek.com/slides/ismp2012/sdo.pdf

If you have an LMI (written like in the Fusion code)

minimize c^Tx

s.t   A_0 + \sum_i A_ix_i >> 0

then this is just syntactic shorthand for

minimize c^Tx

s.t   A_0 + \sum_i A_ix_i - X == 0

        X >> 0

so you have n(n+1)/2 individual linear constraints involving the elements of X (n=dim X). The dual is

max -<S, A_0>

st      <A_i,S> = c_i

          S >> 0

(up to me messing up some signs, maybe) and has only as many constraints as terms in the LMI.

M.

[Nagisa Sugishita]

Dear Michal,

Thank you very much for your prompt response once again. Your explanation clarified everything. Also, thank you for sharing the document. The concise introduction seems very helpful in gaining an overview of the IPM for SDP. I truly appreciate all of your assistance!

Best regards,
Nagisa

[Michal Adamaszek]

Now that we have turned this thread into a small FAQ about LMIs and dualization let me also add for the benefit of other readers that:

* Yalmip and CVX detect LMI structure and dualize before calling Mosek, achieving the effect we discussed here,

* CVXPY, as far as I understand, dualizes always, so it achieves the desired effect for LMIs but can have an adverse effect for problems written correctly in "primal" form

* Mosek will likely do this internally at some point, but as of yet (version 10) it cannot dualize SDPs

* The motivating examples are in https://docs.mosek.com/modeling-cookbook/duality.html#semidefinite-duality-and-lmis