Sparse matrix linear matrix inequality


#1

I have an SDP problem with n variables where n can be of order of tens of thousands.
There are also O(n) SDP constraints. These can be described using linear matrix inequalities M_i > 0.
These M_i matrices are rather small (3x3).
One way to tackle this is to add these many small LMI constraints one after the other using a loop.
This seems to be rather slow though.
I was thinking of constructing a large matrix with all the constraints such that the matrix has some sort of block diagonal structure. In this case, the CVX program will eventually have a single large LMI constraint rather than many small LMI constraints. However, for this to fit into memory, one needs to use a sparse matrix.

My question is whether CVX can handle sparse matrices and if so, is there a way to do the construction of this matrix efficiently, possibly by avoiding the loop?

If this is not possible then my next question would be: is this a limitation of the way CVX is designed or is this related to the underlying solvers that are available out there? For example, will I benefit from trying to utilize a solver like Mosek (or any other) directly?


(Erling D.Andersen) #2

MOSEK likes many small matrix variables rather than a few big ones. Here

https://themosekblog.blogspot.com/2018/08/solving-sdp-with-millions-of-matrix.html

is big problem with many small matrix variables MOSEK has solved.

I would think many small LMIs are much better than a few big ones.


#3

Thanks. It’s good to know that.
Should I deduce that using CVX to specify these many small LMIs is a bad idea and one must use MOSEK directly to get reasonable performance?


(Erling D.Andersen) #4

What I am sure about is that calling Mosek directly is the fastest you can get but is not as easy as using cvx.

I would try it out for small to medium size models in cvx and then move Mosek, when you know what model you want to solve.