6
$\begingroup$

I am looking to solve a class of SDPs with complex entries, with the semi-definite cone $S^n$, $n$ around 5000 to 15000. Also, $m$, the number of equality/inequality constraints is close to $n$.

I tried SeDuMi and SDPT3 with CVX, but I quickly run out of memory for $n=1000, m=1000$ (I have about 50 GB available). Could you suggest other (free) SDP solvers that I could use?

I looked at the documentation for SDPA, and it claims to have much lower memory usage than the solvers mentioned above. In one of the cases, the memory use is claimed to be around 5% as SDPT3. The matrices in my problem aren't very sparse, but there are about 20% non-zeros.

Is YALMIP + SDPA is a good combination for my problem?

Please note that I have complex numbers involved, and I would like to avoid changing my formulation to convert everything into real, if possible.

Improve this question
$\endgroup$
1
  • $\begingroup$ Can you describe your objective function? $\endgroup$
    – nicoguaro ♦
    Oct 16, 2015 at 21:08

1 Answer 1

Reset to default
4
$\begingroup$

You can try using SCS, either the direct or indirect solver. SCS uses first-order methods, and hence may be able to solve larger problems than second-order solvers such as SDPT3, SeDuMi, MOSEK, etc. On the downside, given that it is a first-order solver, it can be very slow - but very slow may be better than not at all.

Paper: http://web.stanford.edu/~boyd/papers/pdf/scs.pdf

MATLAB code (need to make): https://github.com/cvxgrp/scs/tree/master/matlab

You can use SCS under YALMIP or under CVX 3.0 beta. Under CVX 3.0 beta, you can specify

cvx_solver scs

which will invoke the SCS direct solver. To invoke the SCS indirect solver, also do

cvx_solver_settings('use_indirect',true);
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ In addition to SCS you also have the first-order solver SDPNAL, also interfaced in YALMIP. $\endgroup$
    – Johan Löfberg
    Oct 16, 2015 at 16:05
  • $\begingroup$ Thanks. I looked into SCS solver as suggested. I am confused about the terminology in the related paper. In table 4, results are shown for 3 different sizes of problems. Could you clarify if the "number of variables" in that table corresponds to n^2 in the terminology I use above. If the desired semidefinite matrix is n×n, is the "number of varibles" as mentioned in SCS paper close to $n^2/2$ ? Also, why does the paper only talk about case n<m ? My problem doesn't satisfy that criterion. $\endgroup$
    – excel123
    Oct 17, 2015 at 1:53
  • $\begingroup$ CVX and YALMIP will take care of getting your problem into a form the solver can handle, and with YALMIP, you have a dualize option. I'm not sure this is correct, but perhaps your sparsity (0.2) times your n * m would be roughly comparable to the number of non-zeros in A. So m = n = 10000 would correspond to 2e7 non-zeros. However, I'm not sure that is correct and will reflect what CVX or YALMIP will pass to the solver. I'm sure Johan could give a more definitive answer, which perhaps depends on the entirety of your problem, which you have not shown. $\endgroup$
    – Mark L. Stone
    Oct 17, 2015 at 2:35
  • 1
    $\begingroup$ It all depends on the problem formulation, and how you interpret it. If you have one semidefinite $n\times n$ variable $X$ with a constrained trace, it would be wrong to say $n^2/2$ variables as that really doesn't align well with the computational complexity theory. It is a problem living in the n-dimensional primal semidefinite cone with 1 equality, i.e., if interpreted in the dual cone, it is a problem with $1$ variable, i.e., pretty simple. $\endgroup$
    – Johan Löfberg
    Oct 17, 2015 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.