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 \}\) |
|
|
Positive (or linear) cone |
\(\{s \mid s \geq 0 \}\) |
|
|
Box cone |
\(\{(t, s) \in \mathbf{R} \times \mathbf{R}^k \mid t l \leq s \leq t u \}\) |
|
|
Second-order cone |
\(\{(t, s) \in \mathbf{R} \times \mathbf{R}^k \mid \|s\|_2 \leq t \}\) |
|
\(\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) |
|
\(\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) |
|
\(\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 \}\) |
|
\(3 \times\) |
Dual exponential cone |
\(\{ (u,v,w)\in \mathbf{R}^3 \mid -u e^{v/u} \leq e w, u<0 \}\) |
|
\(3 \times\) |
Power cone |
\(\{ (x,y,z) \in \mathbf{R}^3 \mid x^p y^{1-p} \geq |z|\}\) |
|
\(3 \times\) |
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|\}\) |
|
\(3 \times\) |
Spectral cones (experimental)
Note
Spectral cones are experimental and must be explicitly enabled at compile
time by setting USE_SPECTRAL_CONES=1 (which also requires
USE_LAPACK=1). For example:
make USE_LAPACK=1 USE_SPECTRAL_CONES=1
or with CMake:
cmake -DUSE_LAPACK=ON -DUSE_SPECTRAL_CONES=ON ..
The flag also changes the public header: the spectral cone fields of
ScsCone (d, dsize, nuc_m, nuc_n,
nucsize, ell1, ell1_size, sl_n,
sl_k, sl_size) exist only when USE_SPECTRAL_CONES
is defined, so the struct is larger with it. Any code that includes
scs.h and links against a library built with spectral cones must
therefore be compiled with -DUSE_SPECTRAL_CONES as well. Neither
build system does this for you: the installed scs.h is the same
file in both cases, and the CMake targets do not pass the definition on to
the projects that link them. This applies even to programs that use none of
the spectral cones: the library reads these fields each time a problem is
set up (in scs_init, which scs calls), so they must be
present and set to zero (SCS_NULL for the arrays) when unused. A program compiled without the definition passes a struct that is
too short, and the library reads past the end of it.
The API and behavior of these cones may change in future releases. See Compile flags for more details.
The following cones are available when spectral cone support is enabled.
Name |
Description |
Entries in ScsCone |
Number of rows in \(A, b\) |
|---|---|---|---|
Log-determinant cone |
\(\{(t, v, X) \mid -v \log\det(X/v) \leq t,\; v > 0,\; X \succ 0 \}\) |
|
\(\displaystyle \sum_{i=1}^{\text{dsize}} \left(\frac{d_i(d_i+1)}{2} + 2\right)\) |
Nuclear norm cone |
\(\{(t, X) \mid \|X\|_* \leq t \}\) |
|
\(\displaystyle \sum_{i=1}^{\text{nucsize}} (m_i n_i + 1)\) |
\(\ell_1\) norm cone |
\(\{(t, x) \mid \|x\|_1 \leq t \}\) |
|
\(\displaystyle \sum_{i=1}^{\text{ell1\_size}} (\text{ell1}_i + 1)\) |
Sum-of-largest-eigenvalues cone |
\(\{(t, X) \mid \sum_{i=1}^{k} \lambda_i(X) \leq t \}\) |
|
\(\displaystyle \sum_{i=1}^{\text{sl\_size}} \left(\frac{n_i(n_i+1)}{2} + 1\right)\) |
The matrix \(X\) in these cones must be vectorized as follows. In the
log-determinant and sum-of-largest-eigenvalues cones \(X\) is symmetric and
is vectorized as for the semidefinite cone: the lower triangle
is stacked column-wise with the off-diagonal entries scaled by \(\sqrt{2}\),
which gives a vector of length \(n_i(n_i+1)/2\). In the nuclear norm cone
\(X\) is a general \(m_i \times n_i\) matrix and its entries are stacked
column by column with no scaling, which gives a vector of length
\(m_i n_i\). The scalar entries come first: the rows are stacked as
[t; v; vec(X)] for the log-determinant cone and as [t; vec(X)]
for the nuclear norm and sum-of-largest-eigenvalues cones.
The nuclear norm cone requires \(m_i \geq n_i\). Since \(\|X\|_* = \|X^\top\|_*\) a wide matrix can be handled by passing its transpose. The sum-of-largest-eigenvalues cone requires \(0 < k_i < n_i\) (for \(k_i = n_i\) the constraint is the linear inequality \(\text{Trace}(X) \leq t\)). SCS reports a cone validation error at setup if these conditions do not hold.
The log-determinant cone is the epigraph of the perspective of \(-\log\det\), so with \(v = 1\) minimizing \(t\) maximizes \(\log\det X\).
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
and the complex positive semidefinite cone is the set
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
and produces a vector consisting of the lower triangular real parameters scaled and re-arranged. In the real case, the result is
whereas in the complex case the result is
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
whereas in the complex case the inverse operation takes vector \(s \in \mathbf{R}^{k^2}\) and produces the matrix
So the cone definitions that SCS uses are
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}\)
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\):
using the fact that \(\text{vec}\) is linear, where \(b = \text{vec}(B)\) and
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)\).