Exploiting PSD Redundancies in Matrix variables


#1

Hello,

I’m trying to code an SDP that tries to exploit the chordal sparsity of my matrix. One of the constraints looks like this:

\begin{bmatrix} A &B_i\\ B_i^T & C_i \end{bmatrix} \succeq 0, \quad \forall i = 1, \dots, K, \quad A\succeq 0

where A\in R^{M\times M}, B_i\in R^{M\times S} and C_i\in R^{S\times S}. Due to the structure of the problem, only the diagonal entries of C_i are used by the other constraints and the objective function, making the off-diagonal entries of C_i free variables. Given that, one can rewrite the above constraint as:

\begin{bmatrix} A &B_i(j)\\ B_i(j)^T & C_i(j,j) \end{bmatrix} \succeq 0, \quad \forall i = 1, \dots, K, \forall j = 1, \dots, S, \quad A\succeq 0

where B_i(j) is the j’th column of B_i (this comes from the theory of chordal sdp’s and Grone’s Theorem). The result is that I have S·K constraints of size (M+1)x(M+1). My question is the following: As the top-left MxM principal submatrix of all these constraints is A, and A is also constrained to be PSD, is there a way that I can exploit that in CVX? Is CVX already aware of this if I were to declare the constraint as:

A >=0
for j = 1:k
[A,B_i(:,j);B_i(:,j)’,C_i(j,j)] >= 0
end
(and I would also loop this w.r.t. the index i).

In case CVX couldn’t see the redundancy in this form, is there a particular notation I could use to make CVX aware of it? Schur complement notation would reduce this into a scalar inequality, but I know already that CVX won’t accept that. Any help is greatly appreciated!

Thanks!