1
$\begingroup$

I realize that a second-order cone is a cone, and thus an SOCP is a type of conic problem. However, to me it doesn't seem so apparent, looking at their equations. Could someone explain how one could convert an SOCP to Conic program (and show the math involved)? As an example: If there's an SOCP of the form: \begin{aligned} & \text{minimize} & & \mathbf{f}^\intercal\mathbf{x} \\ & \text{subject to} & & {\|\mathbf{A}_i \mathbf{x}+\mathbf{b}_i \|}_2 \leq \mathbf{c}_{i}^{T} \mathbf{x}+d_i \quad \quad i=1,\ldots,m\\ & & & \mathbf{Fx = g} \end{aligned} where $\mathbf{x} \in \mathbb R ^n$ is the optimization variable, $\mathbf{A}_i \in \mathbb R^{n_i \times n}$, $F \in \mathbb R ^{p \times n}.$
How can it has to be converted to the form:
\begin{aligned} & \text{minimize} & & \mathbf{c}^\intercal\mathbf{x} \\ & \text{subject to} & & \mathbf{Mx+p} {\preceq}_K 0\\ & & & \mathbf{Qx = r}. \end{aligned}
where $K$ (which will be the cone of the $m$ second-order cones combined?). Both the forms have been picked up from Boyd's Convex Optimization book.

$\endgroup$
1
$\begingroup$

Let $\mathcal{Q}^{n_i}\subseteq\mathbb{R}^{n_i}\times\mathbb{R}$ be the second-order cone of dimension $n_i+1$. Then using your notation, we have $c=f$, $Q=F$, $r=g$, and $$M=-\begin{bmatrix} A_1 \\ c_1^T \\ A_2 \\ c_2^T \\ \vdots \\ A_m \\ c_m^T \end{bmatrix} \quad p=-\begin{bmatrix} b_1 \\ d_1 \\ b_2 \\ d_2 \\ \vdots \\ b_m \\ d_m \end{bmatrix} \quad K = \mathcal{Q}^{n_1} \times \mathcal{Q}^{n_2} \times \dots \times \mathcal{Q}^{n_m}.$$ That's it! Once you understand this, then you will see that really there is no need to be so dogmatic about your single-cone form. There's no reason you can't do this: \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & M^{(i)} x + p^{(i)} \succeq_{K^{(i)}} 0, ~i=1,2,\dots, m \\ & Q x = r \end{array} Using $\succeq$ instead of $\preceq$ avoids those pesky negative signs above.

$\endgroup$
  • $\begingroup$ I think there's a typing mistake. The c1, c2, ... cm, in M will be transposed, yes? Otherwise, there will be dimension mismatch. $\endgroup$ – Mihir Aug 3 '15 at 14:37
  • $\begingroup$ Yes, you're right. Thanks! I've made the change. $\endgroup$ – Michael Grant Aug 3 '15 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.