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

$\endgroup$
2
  • $\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, 2015 at 11:39
  • $\begingroup$ The first link is down. $\endgroup$ Mar 7, 2022 at 12:41

1 Answer 1

5
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .