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}\)
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 symmetric 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 for short we use \(S \succeq 0\) to denote membership. SCS vectorizes this cone in a special way which we detail here.

SCS assumes that 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 \times 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.

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 S)\) as \(\text{vec}(Y)^\top \text{vec}(S)\), where the \(\text{vec}\) operation takes the (assumed to be symmetric) \(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 elements scaled and arranged as

\[\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}.\]

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, 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}\]

So the cone definition that SCS uses is

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

Example

For a concrete example in python see Low-Rank Matrix Completion. Here we consider the symmetric 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)\).