# Low computation speed of large-scale semidefinite programming

Hi guys,
I’m using CVX to solve the following semidefinite programming but the speed is pretty slow.

min trace(AX)

s.t.
(1)trace(B_i X) <= b_i, i=1,…,n

(2)X>=0;

(3)rI - V’XV >= 0

Constraint 1 is series of linear constraints while constraint (2) and (3) are semidefinite constraints. X is in R^(110x110), V is in R^(110x109). When I remove constraint (3), cvx can compute pretty fast. However, when I keep it, it may take me almost one hour to solve this program. Is it reasonable? Is constraint (3) really so complicated, give it’s linear matrix inequality?

I’ll appreciate your help a lot.

Yes, this is reasonable, I am afraid. Semidefinite programming is slow, particularly if there are a lot of constraints. With (3) removed, there are not very many constraints, but (3) adds thousands of them. Try all the solvers to see which one is fastest for you.

Yes, I have tried different solver in CVX, among which the best one is sedumi. However, it is still not fast enough.

Thanks!

[update]
Yep I just tried the solver Mosek_7. To solve the aforementioned problem, it needs about 25 minutes. Though it is twice faster than sedemi(it needs about one hour), but it performance is not as good as sedemi.

I wonder it is still reasonable to take so long a time!

I assume you tried MOSEK. Was SeDuMi really faster? Would you be willing to give us (=MOSEK) the problem. I can tell you how to dump the problem to disk easily.

Yep I just tried the sovler Mosek_7. To solve the aforementioned problem, it needs about 25 minutes. Though it is twice faster than sedemi(it needs about one hour), but it performance is not as good as sedemi.

I don’t think you can expect better performance. You have 12100 variables, split into two semidefinite cones, and 6000 constraints or more. That’s not large for an LP, but for an SDP, it definitely is.

I assume you mean MOSEK is fast but SeDuMi is more accurate. It your is problem numerically you can tighten the stopping tolerances. Also MOSEK v8 should be more accurate. We hope to beat SeDuMi in that area too.

Also large semidefinite variables and many linear equality constraints usually means long solution times.

I appreciate all of your help a lot!!! Thanks!