Hi,

I solve a SDP problem using SeDuMi and SDPT3 the matrix A (Ax=b) is sparse of size 904000*130069 and the percentage of nonzero elements is 0.001%. You think that this is the limit and is there any tool to exploit more this sparsity?

Thank you

Impossible to say unless you post the code. We have successfully setup an LP problem with 20000000 variables, so it all depends on the structure.

What do you mean by structure? my initial problem is different I transform in a SDP problem than I make some reformulation to write it in the input form of SeDuMi or SDPT3, and I get the matrix A of size 904000*130069 with 0.001% nonzero elements, the matrix A doesn't have a special form nether its submatrices.

If you want to exploit things beyond sparsity, some other structure has to be exploited. Sparsity is exploited by all solvers.

Is it one large SDP, or many small, are all variables occurring in all constraints, or some few which distribute over many constraints, is there any correlative sparsity structure, are there any bounds on variables as in copositive relaxations, is the problem/solution sparse in both primal and dual space etc etc etc

Well my problem looks like this

min c'x
s.t M_i>=0, i=1,...,n "matrices that should be positif semidefinite"
L_j==0, j=1,...,m "some lineare equalities"
C>=0 "the compacity constraint"

In this problem the sparsity is already exploited, then I transform the problem on Ax=b (all the matrices, lineare eqyalities and the compacity constraint are inside vectorized), and you see I get <1% of nonzeros elements, I am I making me clear.


I want to know if it's possible to exploite more the structure of the matrix A and to know the limit of size that I can reach.

Thanks

Your problem desciption does not say much, as it doesn't say which variables you have, which constraints they enter, and what the constraints look like.

As I said, if the problem has any of the above mentioned structure, or other structure, there are tailed algorithms to exploit it. Either by manually reformulating the problem to a smaller standard problem or by using specific solvers. sdpa for instance has some structure exploiting variants. Alternatively, there are first-order solver which don't exploiit structure primarily, but at least makes huge problem tractable (sdpnal for instance)

As for size, it depends on the problem. I can easily generate an SDP with millions of variables that I can solve easily by exploiting structure (for instance, if the SDP is diagonal and reduces to an LP). There is a lot of research going on in the field of symmetry reductions etc. However, here you have to really study the original model, it is very hard to do anything once you've compiled everything to numerical data