Sparsity in Semidefinite Programming

[Marek Tyburec]

Dear all,

I would like to kindly ask regarding sparsity in semidefinite optimization. Let us now consider that some (my) problem involves a positive semidefinite variable X. We further know that some (not so small) portion of X equals to zero and we also know the corresponding (i,j) entries in X (sparsity pattern of X). My question is how to incorporate this knowledge into the optimization problem formulation in an efficient manner? I work with C++ Mosek fusion api.

Obviously, I can create the matrix variable, and set the corresponding (i,j) entries of X to zeros using element-wise equalities. Unfortunately, this makes the problem larger as the sparsity information is not exploited by the optimizer, and thus the solution time increases. Clearly, I aim at the exact opposite.

What is the most appropriate approach to do this?

Thanks for your answer,

Marek

[Joachim Dahl]

I think you should try to exploit "chordal sparsity".  Lieven Vandenberghe and Martin Andersen wrote an extensive survey on the topic:

http://www.seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf

I think of it as a preprocessing step for the SDP solver, and it's not a straightforward thing to do or implement, but probably your best bet at exploiting general sparsity in SDP.

--
You received this message because you are subscribed to the Google Groups "mosek" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mosek+unsubscribe@googlegroups.com.
To post to this group, send email to mo...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Marek Tyburec]

Thanks for your answer. So if I understand this correctly, solution of the toy problem

minimize  x
subject to X >= 0, where
X = [x 2 1; 1 3 2; 1 2 3]

requires to create X and formulate element-wise equalities, so that the solver uses internal 6+1 scalar variables, and this number can not be reduced without reformulation the problem. Am I right?

Marek

Dne pondělí 26. března 2018 11:09:46 UTC+2 Joachim Dahl napsal(a):

To unsubscribe from this group and stop receiving emails from it, send an email to mosek+un...@googlegroups.com.

[Joachim Dahl]

That is not how I think of chordal completions and sparsity. In the simplest case you have a block-diagonal semidefinite variable X.  That should be exploited by treating multiple independent semidefinite variables rather that a large single semidefinite variable with zeros on the off-diagonal blocks.  If the matrix is almost block diagonal you can treat is a block-diagonal matrix if you add additonal equality constraints for the elements outside the block-diagonal pattern.  That is called a "chordal conversion".

But you will have to read the survey I mentioned (or other ressources) if you want to proceed in that direction.  There's much more to it than can be explained via this forum.

On Mon, Mar 26, 2018 at 12:00 PM, Marek Tyburec <marek....@gmail.com> wrote:

So if I understand this correctly, solution of the toy problem

minimize  x
subject to X >= 0, where
X = [x 2 1; 1 3 2; 1 2 3]

with the analytical solution easily computable by hand requires to create X and formulate element-wise equalities, so that the solver requires 6+1 scalar variables in total (and this number can not be reduced). Am I right?

Marek

Dne pondělí 26. března 2018 11:09:46 UTC+2 Joachim Dahl napsal(a):

I think you should try to exploit "chordal sparsity".  Lieven Vandenberghe and Martin Andersen wrote an extensive survey on the topic:

To unsubscribe from this group and stop receiving emails from it, send an email to mosek+un...@googlegroups.com.

To post to this group, send email to mo...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Connor Holmes]

I am trying to implement a general method to exploit chordal sparsity in SDPs. I have a method for identify cliques in my problem and the required constraints between them. I am wondering what is the most efficient way to implement this in MOSEK. Two methods come to mind:

1. Define a large matrix, X, representing the large (completable) matrix. Add constraints to enforce that specific submatrices are PSD.
   
2. Define PSD matrices as variables for each clique and enforce equality constraints between the cliques.

The first method makes the rest of the problem easy, because my existing affine constraints and cost can be applied directly to the large matrix X. My concern is that it maybe overparameterizes the problem.

[Erling D. Andersen]

All other things equal then the bigger matrix variables the higher the computational cost. So to me it sounds like option 1 is a bad idea.

[Connor Holmes]

I have implemented a method to exploit the chordal sparsity, but what I am finding is that the "overlap" constraints that are introduced to ensure consistency between the decomposed SDP variables are increasing the runtime considerably. I have read that this can happen due to the size of the (dense) Schur complement of the KKT equations that must be solved at each iteration. However, these overlap constraints are extremely sparse. Is there any way to tell Mosek to leverage this sparsity or change how it solves the KKT system?

[Erling D. Andersen]

Mosek exploits the sparsity in the constraint matrix. Only I can change the way the KKT system is solved by changing the code.

Have you seen

https://scholar.google.dk/citations?view_op=view_citation&hl=da&user=3I3Gs2cAAAAJ&sortby=pubdate&citation_for_view=3I3Gs2cAAAAJ:vV6vV6tmYwMC

Is your original problem on LMI (=dual form) or primal form? 

[Connor Holmes]

It is in primal form. I thought that the form would not matter because of the self dual embedding. Is one form more efficient if you have many constraints?

 I did apply a merging strategy and that helped, but I haven't seen this article yet. Thanks for the tip, I will take a look.

To view this discussion visit https://groups.google.com/d/msgid/mosek/415c1098-dc0f-480c-9f8e-5027f96d07b2n%40googlegroups.com.

[Michal Adamaszek]

Hi,

Regarding the primal/dual issue have a look at the discussion we had in this thread

https://groups.google.com/g/mosek/c/xP_KtAJ3xSQ

Michal