0
$\begingroup$

In https://inst.eecs.berkeley.edu/~ee127a/book/login/exa_ell_sep.html

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?

$\endgroup$

migrated from stats.stackexchange.com Oct 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.

  • $\begingroup$ 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. $\endgroup$ – Gumeo Oct 18 '15 at 11:39
3
$\begingroup$

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.

$\endgroup$

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.