# 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 Wikipedia 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?

• 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. Oct 18, 2015 at 11:39
• The first link is down. Mar 7, 2022 at 12:41

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.