Cones and inequalities

Pointed and salient convex cones in \(\mathbb{R}^n\) define a partial order therein.

In particular, a pointed, salient, convex cone \(\mathcal{K}\) induces a partial order \(\preceq_{\mathcal{K}}\) such that \(x \preceq_{\mathcal{K}} y\) if \(y-x\in\mathcal{K}\).

The idea is that by replacing the standard element-wise inequality \(\leq\) by an appropriate conic inequality \(\preceq_{\mathcal{K}}\) in a linear program, we generalize LPs to more general optimization problems while retaining their simple structure.

Indeed, all convex optimization problems can be represented as conic problems.

What is important is that all common convex sets can be represented in terms of conic inequalities using cones \(\mathcal{K}\) on which projection is numerically feasible.

Recall that for every convex cone \(\mathcal{K}\subseteq \mathbb{R}^n\), we define its dual as the following convex cone

\begin{eqnarray*} \mathcal{K}^{*} = \{y\in\mathbb{R}^n : x'y \geq 0, \text{ for all } x\in\mathcal{K}\}. \end{eqnarray*}

Hereafter, we list the convex cones which are supported by SuperSCS.

Zero cone

The zero cone is the set \(\mathcal{K}^{\mathrm{f}}_{n_{\mathrm{f}}} = \{0_{n_{\mathrm{f}}}\}\).

This is used to encode equality constraints.

Linear cone

The linear cone is the positive orthant \(\mathcal{K}^{\mathrm{l}}_{n_{\mathrm{l}}} = \{x\in\mathbb{R}^{n_{\mathrm{l}}}: x_i \geq 0, \forall i\}\)

SO cone

This is the Cartesian product of \(N_{\mathrm{q}}\) cones with dimensions \(n_{\mathrm{q},1},\ldots, n_{\mathrm{q},N_{\mathrm{q}}}\)

The cone is

\begin{eqnarray*} \mathcal{K}^{\mathrm{q}}_{n_{\mathrm{q},1},\ldots, n_{\mathrm{q},N_{\mathrm{q}}}} = \mathcal{K}^{\mathrm{q}}_{n_{\mathrm{q},1}} \times \cdots \times \mathcal{K}^{\mathrm{q}}_{n_{\mathrm{q}, N_{q}}}, \end{eqnarray*}

where \(\mathcal{K}^{\mathrm{q}}_{n}\) is the second-order cone of dimension \(n\), that is

\begin{eqnarray*} \mathcal{K}^{\mathrm{q}}_{n} = \{x = (t, y): t\in\mathbb{R}, y\in\mathbb{R}^{n-1}, \text{ so that } \|y\| \leq t\} \end{eqnarray*}

PSD cone

Let us first give a few necessary definitions. Given a symmetric matrix \(X\in\mathbb{R}^{k\times k}\) we define the vectorization operator as

\begin{eqnarray*} \mathrm{vec}(X) = \sqrt{2} \left( \textstyle\frac{X_{11}}{\sqrt{2}}, X_{2,1},\ldots, X_{k,1}, \textstyle\frac{X_{22}}{\sqrt{2}}, X_{3,2}, \ldots, X_{k,2}, \ldots, \textstyle\frac{X_{kk}}{\sqrt{2}} \right). \end{eqnarray*}

We further define the inverse operation, \(\mathrm{mat}\) which maps a vector of \(\mathbb{R}^{k(k+1)/2}\) to the matrix

\begin{eqnarray*} \mathrm{mat}(x) = \textstyle\frac{1}{\sqrt{2}} \begin{bmatrix} \sqrt{2}x_1 & x_2 & \cdots & x_k\\ x_{2} & \sqrt{2}x_{k+1} & \cdots & x_{2k-1}\\ \vdots & \vdots & \ddots & \vdots\\ x_{k} & x_{2k-1} & \cdots & \sqrt{2}x_{k(k+1)/2} \end{bmatrix}. \end{eqnarray*}

The above definitions preserve the inner product operations.

In particular

\begin{eqnarray*} \langle X,Y \rangle = \mathrm{tr}(X'Y) = \mathrm{vec}(X)'\mathrm{vec}(Y) = \langle \mathrm{vec}(X),\mathrm{vec}(Y) \rangle, \end{eqnarray*}

and

\begin{eqnarray*} \langle x,y \rangle = \langle \mathrm{mat}(x),\mathrm{mat}(y) \rangle. \end{eqnarray*}

We define the positive definite cone as

\begin{eqnarray*} \mathcal{K}^{\mathrm{s}}_{k} = \{x\in\mathbb{R}^{k(k+1)/2} : \mathrm{mat}(x) \text{ is positive semidefinite}\} \end{eqnarray*}

Furthermore, define

\begin{eqnarray*} \mathcal{K}^{\mathrm{s}}_{k_1,\ldots, k_{N_{\mathrm{s}}}} = \prod_{i=1}^{N_{\mathrm{s}}}\mathcal{K}^{\mathrm{s}}_{k_i}. \end{eqnarray*}

Exponential cone

Consider the following set in \(\mathbb{R}^3\)

\begin{eqnarray*} \mathcal{C}^{\mathrm{ep}} = \{(x,y,z)\in\mathbb{R}^3: y e^{x/y} \leq z, y>0\}. \end{eqnarray*}

The exponential cone is the closure of \(\mathcal{C}^{\mathrm{ep}}\)

\begin{eqnarray*} \mathcal{K}^{\mathrm{ep}} = \mathrm{cl}\mathcal{C}^{\mathrm{ep}}. \end{eqnarray*}

Define the Cartesian product of \(n_{\mathrm{exp}}\) such cones

\begin{eqnarray*} \mathcal{K}^{\mathrm{ep}}_{n_{\mathrm{ep}}} = \prod_{i=1}^{n_{\mathrm{ep}}}\mathcal{K}^{\mathrm{ep}}. \end{eqnarray*}

Dual exponential cone

The dual exponential cone is the set

\begin{eqnarray*} \mathcal{K}^{\mathrm{ed}} = \left\{ (u,v,w)\in\mathbb{R}^3: u\leq 0, w \geq 0, -u \log(-\textstyle\frac{u}{w})+u-v\leq 0 \right\}, \end{eqnarray*}

with \(0 \log(0/w)=0\) for all \(w\geq 0\).

This is the dual of the exponential cone.

We define

\begin{eqnarray*} \mathcal{K}^{\mathrm{ed}}_{n_{\mathrm{ed}}} = \prod_{i=1}^{n_{\mathrm{ed}}}\mathcal{K}^{\mathrm{ed}}. \end{eqnarray*}

Power cone

Given a parameter \(\alpha\in [0,1]\) we define the following cone in \(\mathbb{R}^3\)

\begin{eqnarray*} \mathcal{K}^{\mathrm{p}}_{\alpha} = \left\{ x=(x_1,x_2,x_3)\in\mathbb{R}^3: x_1\geq 0, x_2\geq 0, x_1^\alpha x_2^{1-\alpha} \geq |x_3| \right\}. \end{eqnarray*}

Now define the Cartesian product of \(N_{\mathrm{p}}\) such cones with parameters \(\alpha_1,\ldots, \alpha_{N_{\mathrm{p}}}\) as

\begin{eqnarray*} \mathcal{K}^{\mathrm{p}}_{\alpha_1,\ldots, \alpha_{N_{\mathrm{p}}}} = \prod_{i=1}^{{N_{\mathrm{p}}}} \mathcal{K}^{\mathrm{p}}_{\alpha_i}. \end{eqnarray*}

For \(\alpha\in (0,1]\), we define \(\mathcal{K}^{\mathrm{p}}_{-\alpha}\) to be the dual cone of \(\mathcal{K}^{\mathrm{p}}_{-\alpha}\), that is \(\mathcal{K}^{\mathrm{p}}_{-\alpha}=(\mathcal{K}^{\mathrm{p}}_{\alpha})^{*}\).

General cones

In SuperSCS, cones are described by the general form

\begin{eqnarray*} \mathcal{K} = \mathcal{K}^{\mathrm{f}}_{n_{\mathrm{f}}} \times \mathcal{K}^{\mathrm{l}}_{n_{\mathrm{l}}} \times \mathcal{K}^{\mathrm{q}}_{n_{\mathrm{q}_1},\ldots, n_{\mathrm{q},N_{\mathrm{q}}}} \times \mathcal{K}^{\mathrm{s}}_{k_{1},\ldots, k_{N_{\mathrm{p}}}} \times \mathcal{K}^{\mathrm{ep}}_{n_{\mathrm{ep}}} \times \mathcal{K}^{\mathrm{ed}}_{n_{\mathrm{ed}}} \times \mathcal{K}^{\mathrm{p}}_{\alpha_1,\ldots, \alpha_{N_{\mathrm{p}}}} \end{eqnarray*}

Cones in SuperSCS

MATLAB

In MATLAB, general cones are represented by structures.

The structure is straightforward and corresponds to the notation introduced above.

For example, let us have a look at the following cone

K.f  = 2;
K.l  = 5;
K.q  = [3, 9, 7];
K.s  = [2, 6];
K.ep = 10;
K.ed = 4;
K.p  = [0.1, -0.6, 0.9];

This corresponds to the following Cartesian product of cones:

\begin{eqnarray*} \mathcal{K} = \mathcal{K}^{\mathrm{f}}_{2} \times \mathcal{K}^{\mathrm{l}}_{5} \times \mathcal{K}^{\mathrm{q}}_{3,7,9} \times \mathcal{K}^{\mathrm{s}}_{2,6} \times \mathcal{K}^{\mathrm{ep}}_{10} \times \mathcal{K}^{\mathrm{ed}}_{4} \times \mathcal{K}^{\mathrm{p}}_{0.1, -0.6, 0.9} \end{eqnarray*}

Certain parameters can be omitted or set to 0 or [].

For example, the cone \(\mathcal{K}^{\mathrm{q}}_3\) can be written as

K.q = 3;

or, equivalently

K.f  = 0;
K.l  = 0;
K.q  = 3;
K.s  = [];
K.ep = 0;
K.ed = 0;
K.p  = [];

C

In C, cones are supported by the structure ScsCone.

In order to construct \(\mathcal{K}^{\mathrm{s}}_{k_1,\ldots, k_{N_{\mathrm{s}}}}\), \(\mathcal{K}^{\mathrm{p}}_{\alpha_1,\ldots, \alpha_{N_{\mathrm{p}}}}\) and/or \(\mathcal{K}^{\mathrm{q}}_{n_{\mathrm{q},1},\ldots, n_{\mathrm{q},N_{\mathrm{q}}}}\), we also need to specify the lengths of the corresponding arrays.

For example, in order to define \(\mathcal{K}^{\mathrm{q}}_{3,7,9}\) we do

ScsCone * cone;
scs_int number_of_soc_cones = 3;
cone = scs_malloc(sizeof(*cone));
cone->qsize = number_of_soc_cones;
cone->q = scs_malloc(number_of_soc_cones * sizeof(*cone->q));
cone->q[0] = 3;
cone->q[0] = 7;
cone->q[0] = 9;
// at the end, don't forget to free the cone (e.g., using #scs_free_data_cone)

The zero cone, the linear cone and the primal and dual exponential cones are defined very easily as follows:

cone->f  = 2;
cone->l  = 5;
cone->ep = 10;
cone->ed = 4;

Python

In Python, a cone is described as in MATLAB and in C (see above).

For example, the cone \(\mathcal{K} = \mathcal{K}^{\mathrm{f}}_{5} \times \mathcal{K}^{\mathrm{l}}_{3}\times \mathcal{K}^{\mathrm{q}}_{2,9}\) is

cone = {'f':5, 'l': 3, 'q':[2,9]}

See Also: ScsCone: the C Cones API; Saving and loading problems; SuperSCS tutorial

Table of Contents