SCS - Splitting Conic Solver

An R interface to the Splitting Conic Solver (SCS).

Definitions

SCS solves the following problem: $$ \begin{equation} \begin{array}{rlrlcrlrl} primal & & & & & dual & & & \ & \min_x & c^\top x & & \qquad \qquad & & \max_y & -b^\top y & \ & s.t. & Ax + s & = b & & & s.t. & -A^\top y + r & = c \ & & (x, s) & \in \mathbb{R}^n \times \mathcal{K} & & & & (r, y) & \in {0}^n \times \mathcal{K}^* \ & & & & \text{Equation (1)} & & & & \end{array} \end{equation} $$
Where the cone $\mathcal{K}$ can be any Cartesian product of the following cones:

$$ \begin{array}{|lll|} \hline \text{Name} & \text{Definition} \ \hline \text{zero cone} & {x|x=0} \text{ (dual to the free cone} {x|x \in \mathbb{R} }\text{)} \ \text{positive orthant} & \left{x|x \geq 0 \right} \ \text{second-order cone} & \left{(t, x) \ | \ ||x||_2 \leq t, x \in \mathbb{R}^n, t \in R \right} \ \text{positive semidefinite cone} & \left{ X \ | \ min(eig(X)) \geq 0, \ X = X^T, \ X \in \mathbb{R}^{n \times n} \right} \ \text{exponential cone} & \left{(x,y,z) \ | \ y e^{\frac{x}{y}} \leq z, \ y > 0 \right} \ \text{dual exponential cone} & \left{(u,v,w) \ | \ -u e^{\frac{v}{u}} \leq e w, u < 0 \right} \ \text{power cone} & \left{(x,y,z) \ | \ x^a * y^{(1-a)} \geq |z|, \ x \geq 0, \ y \geq 0 \right} \ \text{dual power cone} & \left{ (u,v,w) \ | \ \left(\frac{u}{a}\right)^a * \left(\frac{v}{(1-a)}\right)^{(1-a)} \geq |w|, \ u \geq 0, \ v \geq 0 \right} \ \hline \end{array} $$

Usage

scs(A, b, obj, cone, control)

Important Note

The order of the rows in matrix $A$ has to correspond to the order given in the table "Cone Arguments", which means means rows corresponding to primal zero cones should be first, rows corresponding to non-negative cones second, rows corresponding to second-order cone third, rows corresponding to positive semidefinite cones fourth, rows corresponding to exponential cones fifth and rows corresponding to power cones at last.

Arguments

$$ \begin{array}{ll} A & \text{a matrix of constraint coefficients} \ b & \text{a numeric vector giving the primal constraints} \ obj & \text{a numeric vector giving the primal objective} \ cone & \text{a list giving the cone sizes} \ control & \text{a list giving the control parameters} \end{array} $$

Cone Arguments

Control Arguments

Note on Semidefinite Cones

To transform an SDP problem into the form shown in Equation (1), a half-vectorization should be performed on the matrices $F_i$ and the strictly lower triangular values have to be scaled by $\sqrt{2}$. Furthermore to get the matrix solution an inverse transformation has to be performed on the results. $$ \begin{equation} \begin{array}{lrl} \min_x & c^\top x & \ s.t. & \sum_{i=1}^m x_i F_i & \succeq F_0 \ & A x & = b \
\end{array} \end{equation} $$ where $F_i \in R^{n \times n}$ are symmetric matrices, for more information see e.g. ("Vandenberghe and Boyd (1996) Semidefinite Programming" or "Andersen et al. (2011) Interior-Point Methods for Large-Scale Cone Programming")

$$ F_i = \begin{pmatrix} f_{11} & f_{12} & \dots & f_{1m} \ f_{21} & f_{22} & \dots & f_{2m} \ \vdots & \vdots & \ddots & \vdots \ f_{m1} & \dots & \dots & f_{mm} \end{pmatrix} \ vec(F_i) = (f_{11}, \sqrt{2} f_{21}, \dots, \sqrt{2} f_{m1}, \ \ f_{22}, \sqrt{2} f_{32}, \dots, \sqrt{2} f_{m2}, \ \ f_{m-1,m-1}, \sqrt{2} f_{m,m-1}, \ \ f_{mm})^\top \ G = \left( vec(F_1), \dots, vec(F_m) \right) \ h = vec(F_0) $$ and the new $A$ matrix $A^{new}$ is given by,

$$ A^{new} = \begin{pmatrix} A \ G \end{pmatrix} , \ \ \ b^{new} = \begin{pmatrix} b \ h \end{pmatrix} \ . $$

Example

A <- matrix(c(1, 1), ncol=1)
b <- c(1, 1)
obj <- 1
cone <- list(f = 2)
control <- list(eps = 1e-3, max_iters = 50)
sol <- scs(A, b, obj, cone, control)
sol

Reference

Brendan O’Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd (2013). \ \ "Conic optimization via operator splitting and homogeneous self-dual embedding" \ \ URL http://arxiv.org/abs/1312.3039