Formulate SDP as Conic optimization in SCS format

[nickari]

I'm trying to solve a problem of the form

Minimize -log(det(A)) s.t. A = A' >> 0 (i.e. A is symmetric positive semidefinite) v_i' A v_i <= 1

where the vectors v_i all have ||v_i||_2 = 1. SCS solves this problem quickly and reasonably accurately - however, using a parser to convert from the above form to the form required by SCS takes almost as long as actually solving the problem. Given that the application I'm working on needs to be as fast as possible, it seemed like an obvious step to formulate the problem in the format SCS expects directly and not rely on a parser like CVX. After doing some research, it seems like the standard approach to expressing problems of this type is something like

Minimize -t s.t. M = [A, Z' ; Z, diag(Z)] M >> 0 Z is lower triangular t <= sum(log(diag(Z))) -(v_i' A v_i - 1) >= 0

where M, A, and Z are matrix variables, t is a scalar variable, and the vectors v_i are inputs. This is a combination of linear, PSD cone, and exponential cone (or power cone if instead you set t <= (prod(diag(Z))^(1/m)) constraints, and so is solvable by SCS. Following the readme, I arranged the constraints in the order of zero cone (the constraints on the upper triangular entries of Z), positive orthant (the constraints on v_i' A v_i), the PSD constraints on [A, Z' ; Z, diag(Z)], and then the exponential cone constraints on t. However, the solutions I get when attempting to pass this into SCS are gibberish, and comparing with the results from using a parser show that I am missing several constraints (at least).

My issue is essentially this: in what format does SCS expect PSD constraints in the data matrix A (and how are they expressed), does the column order of A matter at all (I understand that the row order has to follow the order of cones listed in the readme), and is there any documentation of how to set this sort of problem up for direct input to SCS, or is the assumption that a parser will be used?

[bodono]

First, if you're using cvxpy then it has the ability to cache the formulation of the problem so you only pay the parsing cost once.

Second, are you doing the transformation listed in the README?:

Semidefinite Programming

SCS assumes that the matrix variables and the input data corresponding to semidefinite cones have been vectorized by scaling the off-diagonal entries by sqrt(2) and stacking the lower triangular elements column-wise. For a k x k matrix variable (or data matrix) this operation would create a vector of length k(k+1)/2. Scaling by sqrt(2) is required to preserve the inner-product.

To recover the matrix solution this operation must be inverted on the components of the vector returned by SCS corresponding to semidefinite cones. That is, the off-diagonal entries must be scaled by 1/sqrt(2) and the upper triangular entries are filled in by copying the values of lower triangular entries.

More explicitly, we want to express Tr(C X) as vec(C)'*vec(X), where the vec operation takes the k x k matrix

X = [ X11 X12 ... X1k X21 X22 ... X2k ... Xk1 Xk2 ... Xkk ] and produces a vector consisting of

vec(X) = (X11, sqrt(2)X21, ..., sqrt(2)Xk1, X22, sqrt(2)*X32, ..., Xkk).

[nickari]

Yes, I am doing that transformation. Basically what's throwing me off is that while I understand how to determine the order of the rows in the data matrix A (following the order specified in the readme), I do not understand what determines the ordering of the columns. My initial guess is that the columns can be ordered however you want (as long as the relevant entries in the b vector are reordered accordingly), but I'm unsure about this and I haven't been able to figure it out one way or the other. The other question I have is how SCS actually expects PSD constraints to be expressed in the data matrix A (there are multiple ways to do this, and examining results hasn't helped me narrow it down).

[bodono]

The order of the columns is arbitrary, though it will affect the order of the x variables so must be consistent with the c vector, the column order doesn't affect b.

I'm not sure what your second question means, the problem SCS solves is

minimize        c'x
subject to      Ax + s = b
                s in K

maximize        -b'y
subject to      -A'y == c
                y in K^*

so you as a user can target the primal or dual formulation, whichever is easier. This is made even simpler by the fact that the semidefinite cone of matrices is self-dual (ie K_sdp = K^*_sdp). Is the question about how to express your particular problem in this canonical form?