# Why is this an example of second order cone program?

We are trying to separate two ellipses using a hyperplane

The resulting "SOCP" is given as:

$$\min\limits_a \|R_1^Ta\|_2 + \|R_2^Ta\|_2$$

$$\text{subject to } a^T\hat{x}_2 - a^T\hat{x}_1 = 1$$

where $a \in \mathbb{R}^n, \hat{x}_i \in \mathbb{R}^n$ and $R_i$ are some $n \times n$ matrix

Of course this blew my mind because it looks absolutely nothing like a SOCP

According to Wiki: https://en.wikipedia.org/wiki/Second-order_cone_programming

Our program should have the form:

$$\min f^Tx$$

$$\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m$$ $$Fx = g \$$ $f \in \mathbb{R}^n, \ A_i \in \mathbb{R}^{{n_i}\times n}, \ b_i \in \mathbb{R}^{n_i}, \ c_i \in \mathbb{R}^n, \ d_i \in \mathbb{R}, \ F \in \mathbb{R}^{p\times n},$and $g \in \mathbb{R}^p. x\in\mathbb{R}^n$

Right off of the bat we see that our objective function is not linear in $a$, in fact it is a quadratic form $\sqrt{a^TR_1R_1^Ta}$.

The constraints are also suspicious but there are some potential to be massaged into a good cone inequality.

Can someone please advise as to how why the proposed optimization problem is SOCP and whether the objective function can be made into a standard SOCP format?

## migrated from stats.stackexchange.comOct 18 '15 at 14:46

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

• Maybe look into how you can formulate a quadratic program as a SOCP. Here is a paper that takes one example in section 2.1. You probably want to look at the dual problem and formulate that as a SOCP. – Gumeo Oct 18 '15 at 11:39

## 1 Answer

A very common trick in convex programming is to encode a function as a constraint set. For example, if $f$ is a convex function, then the unconstrained minimization problem:

$$\min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x})$$ is equivalent to minimizing a linear function over a convex set in higher dimensions: $$\begin{gathered}\min_{(\mathbf{x},t) \in \mathbb{R}^{n+1}} t\\ \text{subject to: } f(\mathbf{x}) \le t\end{gathered}$$

So using this standard technique, the given program is equivalent to one with a linear objective, a linear constraint, and second order cone constraints: $$\begin{gathered}\min_{a,t_1,t_2} t_1 + t_2\\ \text{subject to } a^T\hat{x}_2 - a^T\hat{x}_1 = 1\\ \|R_1^Ta\|_2 \le t_1\\ \|R_2^Ta\|_2 \le t_2 \end{gathered}$$ To put it in the standard form of an SOCP, you'd need to stack the variables $a,t_1,t_2$ into a single vector.