Sparse Semidefinite Variable

1

Hi everyone,

Is it possible to declare a SDP variable with a fixed and known sparsity pattern so that these nonzero entries are optimization variables?

The trouble I’ve encountered is that I used an equality constraint to impose the sparsity pattern I want, but CVX also treats the entries I want to be zero as variables that end up being really small at the optimal solution. But I want CVX not to regard them as variables to be small precisely because I want to reduce the number of variables and thereby reduce computation time.

For instance, CVX has some built-in feature to declare a SDP variable as banded and this reduces the number of variables, how to do something similiar using user-prescribed sparsity patterns?

2

I don’t believe you can directly do what you want. You can, however, build up a matrix via concatenation, where some of the items being concatenated are zeros.

variables a b c d
X = [a 0 b;0 c 0;b 0 d];
X == semidefinite(3)

Some of the items being concatenated could be matrix or vector CVX variables.

variable A(3,3) symmetric
variable B(3,3) symmetric
variable C(3,3) upper_triangular
X = [A C;C’ B];
X == semidefinite(6)

1 Like
3

For your information the x=0 end up being explicit in the model fed to optimizer.
No one knows how to exploit them in an efficient way.

1 Like
4

I’ve noted that is so.
What puzzles me however is that when I use a CVX “native to declare” sparsity pattern - e.g. banded semidefinite variable X -

variable X(size,size) banded( fraction of size) semidefinite;

the number of variables of the optimization problem is reduced from (size)^2 the number of entries in the main diagonal and specified super/subdiagonals. So I got what I actually wanted.

But I’ve tried exploiting other patterns that might give me improved efficiency, for instance, enforcing some super/sub-diagonals to be zero while keeping others as variables. But I want them to be exactly zero, that is, structural zeros as opposed to optimization variables that will be minimized.

What puzzles me it that the first approach gets me where I wanted but when I try the approach suggested by @Mark_L_Stone, my structural zeros are in fact optimization variables that in fact turn out to be nearly zero but do not get me the speed up in computation time I want by declaring to be zeros in the first place.

I still wonder why the first works whereas the second does not. Any thoughts would be welcome @Erling

5

Probably, CVX developer @mcg is the only one who can definitively answer, and he is not very active on this forum.

1 Like
6

You can try to find the ph.d. thesis of @mcg and go trough the documentation. Maybe, they reveal a clever reformulation trick that Cvx use.

I would be interested in knowing what that is.

1 Like
7

@mcg’s thesis

1 Like
8

Great advice! I’ll read it and will be happy to share it with you both (@Mark_L_Stone and @Erling ) should I manage to discover it.

9

Before you get your hopes too high, read this extract from the thesis, which corresponds to an ancient version of CVX.

5.2.1 Improving the cvx framework
Vector and matrix support
As mentioned, the current version of the cvx modeling framework supports only scalar variables and parameters. As a result, models that involve vectors or matrices must be specified with separate variables and parameters declared for each element, as was done for the examples in §5.1

Here is a slightly newer reference (maybe just reflects a delay in the publication process, so not really newer material) https://web.stanford.edu/~boyd/papers/pdf/disc_cvx_prog.pdf, but i don’t think you’ll find what you want in there either.

You could try to read through the CVX source code, although I suspect that would be rather challenging.

1 Like