Cones

The cone \(\mathcal{K}\) can be any Cartesian product of the following primitive cones.

Name	Description	Entries in ScsCone	Number of rows in \(A, b\)
Zero cone	\(\{s \mid s = 0 \}\)	z length of cone.	z
Positive (or linear) cone	\(\{s \mid s \geq 0 \}\)	l length of cone.	l
Box cone	\(\{(t, s) \in \mathbf{R} \times \mathbf{R}^k \mid t l \leq s \leq t u \}\)	bu, bl correspond to \(u,l\) and are arrays of length \(\max(\text{bsize}-1, 0)\) where bsize is total cone length.	bsize
Second-order cone	\(\{(t, s) \in \mathbf{R} \times \mathbf{R}^k \mid \|s\|_2 \leq t \}\)	q array of SOC lengths with qsize elements, each \(q_i\) is total length of that cone.	\(\displaystyle \sum_{i=1}^{\text{qsize}} q_i\)
Positive semidefinite cone	\(\{ s \in \mathbf{R}^{k(k+1)/2} \mid \text{mat}(s) \succeq 0 \}\) (See note)	s array of PSD cone lengths with ssize elements, each \(s_i = k_i\) in description.	\(\displaystyle \sum_{i=1}^{\text{ssize}} \frac{s_i(s_i+1)}{2}\)
Complex positive semidefinite cone	\(\{ s \in \mathbf{R}^{k^2} \mid \text{mat}(s) \succeq 0 \}\) (See note)	cs array of PSD cone lengths with cssize elements, each \(cs_i = k_i\) in description.	\(\displaystyle \sum_{i=1}^{\text{cssize}} cs_i^2\)
Exponential cone	\(\{ (x,y,z) \in \mathbf{R}^3 \mid y e^{x/y} \leq z, y>0 \}\)	ep number of cone triples.	\(3 \times\)ep
Dual exponential cone	\(\{ (u,v,w)\in \mathbf{R}^3 \mid -u e^{v/u} \leq e w, u<0 \}\)	ed number of cone triples.	\(3 \times\)ed
Power cone	\(\{ (x,y,z) \in \mathbf{R}^3 \mid x^p y^{1-p} \geq |z|\}\)	p array of \(p\in[-1,1]\) powers with psize elements, positive entries correspond to power cone.	\(3 \times\)psize (total for primal and dual power cone)
Dual power cone	\(\{ (u,v,w)\in \mathbf{R}^3 \mid \left(\frac{u}{p}\right)^p \left(\frac{v}{1-p}\right)^{1-p} \geq |w|\}\)	p array \(p\in[-1,1]\) powers with psize elements, negative entries correspond to dual power cone (sign is flipped).	\(3 \times\)psize (total for primal and dual power cone)

Note: The rows of the data matrix \(A\) correspond to the cones in \(\mathcal{K}\). The rows of \(A\) must be in the order of the cones given above, i.e., first come the rows that correspond to the zero cones, then those that correspond to the positive orthants, then the box cone, etc.

Within a cone the rows should be ordered to agree with the mathematical description of the cone as given above. For instance, the box cone is defined as \(\{(t, s) \in \mathbf{R} \times \mathbf{R}^k \mid t l \leq s \leq t u \}\) and consequently the variable vector is stacked as [t;s], ie, t comes first then s. Similarly, the exponential cone is defined as \(\{ (x,y,z) \in \mathbf{R}^3 \mid y e^{x/y} \leq z, y>0 \}\) and therefore the variable vector is stacked as [x, y, z], etc.

Semidefinite cones

The real positive semidefinite cone of matrices is the set

\[\{S \in \mathbf{R}^{k \times k} \mid S = S^\top,\ x^\top S x \geq 0 \ \forall x \in \mathbf{R}^k \},\]

and the complex positive semidefinite cone is the set

\[\{S \in \mathbf{C}^{k \times k} \mid S = S^\dagger,\ x^\dagger S x \geq 0 \ \forall x \in \mathbf{C}^k \},\]

and for short we use \(S \succeq 0\) to denote membership. SCS vectorizes these cones in a special way which we detail here.

SCS assumes that the input data corresponding to positive semidefinite cones have been vectorized by scaling the off-diagonal entries by \(\sqrt{2}\) and stacking the real parameters of the lower triangle column-wise. For a \(k \times k\) real matrix variable (or data matrix) this operation creates a vector of length \(k(k+1)/2\), whereas for a \(k \times k\) complex matrix it creates a vector of length \(k^2\). Scaling by \(\sqrt{2}\) is required to preserve the inner-product.

This must be done for the rows of both \(A\) and \(b\) that correspond to semidefinite cones and must be done independently for each semidefinite cone.

More explicitly, we want to express \(\text{Trace}(Y^\dagger S)\) as \(\text{vec}(Y)^\dagger \text{vec}(S)\), where the \(\text{vec}\) operation takes the \(k \times k\) matrix

\[\begin{split}S = \begin{bmatrix} S_{11} & S_{12} & \ldots & S_{1k} \\ S_{21} & S_{22} & \ldots & S_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ S_{k1} & S_{k2} & \ldots & S_{kk} \\ \end{bmatrix}\end{split}\]

and produces a vector consisting of the lower triangular real parameters scaled and re-arranged. In the real case, the result is

\[\text{vec}(S) = (S_{11}, \sqrt{2} S_{21}, \ldots, \sqrt{2} S_{k1}, S_{22}, \sqrt{2}S_{32}, \dots, S_{k-1,k-1}, \sqrt{2}S_{k,k-1}, S_{kk}) \in \mathbf{R}^{k(k+1)/2},\]

whereas in the complex case the result is

\[\begin{split}\text{vec}(S) = (S_{11}, \sqrt{2} \Re(S_{21}), \sqrt{2} \Im(S_{21}), \ldots, \sqrt{2} \Re(S_{k1}), \sqrt{2} \Im(S_{k1}), S_{22}, \\\sqrt{2}\Re(S_{32}), \sqrt{2}\Im(S_{32}), \dots, S_{k-1,k-1}, \sqrt{2}\Re(S_{k,k-1}), \sqrt{2}\Im(S_{k,k-1}), S_{kk}) \in \mathbf{R}^{k^2}.\end{split}\]

To recover the matrix solution this operation must be inverted on the components of the vectors returned by SCS corresponding to each semidefinite cone. 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. Explicitly, in the real case the inverse operation takes vector \(s \in \mathbf{R}^{k(k+1)/2}\) and produces the matrix

\[\begin{split}\text{mat}(s) = \begin{bmatrix} s_{1} & s_{2} / \sqrt{2} & \ldots & s_{k} / \sqrt{2} \\ s_{2} / \sqrt{2} & s_{k+1} & \ldots & s_{2k-1} / \sqrt{2} \\ \vdots & \vdots & \ddots & \vdots \\ s_{k} / \sqrt{2} & s_{2k-1} / \sqrt{2} & \ldots & s_{k(k+1) / 2} \\ \end{bmatrix} \in \mathbf{R}^{k \times k},\end{split}\]

whereas in the complex case the inverse operation takes vector \(s \in \mathbf{R}^{k^2}\) and produces the matrix

\[\begin{split}\text{mat}(s) = \begin{bmatrix} s_{1} & (s_{2} - i s_3) / \sqrt{2} & \ldots & (s_{2k-2} - is_{2k-1}) / \sqrt{2} \\ (s_{2} + i s_3) / \sqrt{2} & s_{2k} & \ldots & (s_{4k-5} - is_{4k-4}) / \sqrt{2} \\ \vdots & \vdots & \ddots & \vdots \\ (s_{2k-2} + is_{2k-1}) / \sqrt{2} & (s_{4k-5} + is_{4k-4}) / \sqrt{2} & \ldots & s_{k^2} \\ \end{bmatrix} \in \mathbf{C}^{k \times k},\end{split}\]

So the cone definitions that SCS uses are

\[\begin{split}\mathcal{S}_\mathbf{R}^k = \{ \text{vec}(S) \mid S \succeq 0\} = \{s \in \mathbf{R}^{k(k+1)/2} \mid \text{mat}(s) \succeq 0 \}.\\ \mathcal{S}_\mathbf{C}^k = \{ \text{vec}(S) \mid S \succeq 0\} = \{s \in \mathbf{R}^{k^2 } \mid \text{mat}(s) \succeq 0 \}.\end{split}\]

Example

For a concrete example in Python see Low-Rank Matrix Completion. Here we consider the real positive semidefinite cone constraint over variables \(x \in \mathbf{R}^n\) and \(S \in \mathbf{R}^{k \times k}\)

\[B - \sum_{i=1}^n \mathcal{A}_i x_i = S \succeq 0\]

where data \(B, \mathcal{A}_1, \ldots, \mathcal{A}_n \in \mathbf{R}^{k \times k}\) are symmetric. We can write this in the canonical form over a new variable \(s \in \mathcal{S}_+^k\):

\[\begin{split}\begin{align} s &= \text{vec}(S)\\ &= \text{vec}(B - \sum_{i=1}^n \mathcal{A}_i x_i) \\ &= \text{vec}(B) - \sum_{i=1}^n \text{vec}(\mathcal{A}_i) x_i \\ &= b - Ax \end{align}\end{split}\]

using the fact that \(\text{vec}\) is linear, where \(b = \text{vec}(B)\) and

\[A = \begin{bmatrix} \text{vec}(\mathcal{A}_1) & \text{vec}(\mathcal{A}_2) & \cdots & \text{vec}(\mathcal{A}_n) \end{bmatrix}\]

i.e., the vectors \(\text{vec}(\mathcal{A}_i)\) stacked columnwise. This is in a form that we can input into SCS. To recover the matrix solution from the optimal solution returned by SCS, we simply use \(S^\star = \text{mat}(s^\star)\).