Convexity of a second order cone

Question

Does the following set define a second order cone? Anyway, is it a convex set?

$(x,t)$ so that $\lVert(Ax+b)\rVert^{2} \le t(c^{t}x+d)$

$x \in R^{n}$

(A being a matrix, b,c vectors of the appropriate dimensions and d a scalar)

Thank you!

Answer 1

Strictly speaking it's not convex. For example, if $A=c=1$, $b=d=0$, then the set is given by $x(x-t) \le 0$, which is the union of the sectors $t \le x \le 0$ and $0 \le x \le t$.

However, if you make the additional restrictions $t\ge0$ and $c^Tx+d \ge 0$, then the resulting set can be expressed as a second order cone constraint.

$$ \begin{gathered} ||A x + b||^2 \le t(c^Tx + d) \\ c^Tx + d \ge 0 \\ t \ge 0 \end{gathered} \Leftrightarrow \left\| \begin{bmatrix} 2 (Ax + b) \\ c^Tx + d - t \end{bmatrix} \right\| \le c^Tx + d + t $$

This is the trick from the section on hyperbolic constraints in this paper on SOCPs: http://www.stanford.edu/~boyd/papers/socp.html

In general, the original set can be expressed as a union of two convex sets: $$ ||A x + b||^2 \le t(c^Tx + d) \Leftrightarrow (x,t) \in C_1 \cup C_2 $$

$$ C_1 = \left\{ (x,t) \ : \ \left\| \begin{bmatrix} 2 (Ax + b) \\ c^Tx + d - t \end{bmatrix} \right\| \le c^Tx + d + t \right\}\\ C_2 = \left\{ (x,t) \ : \ \left\| \begin{bmatrix} 2 (Ax + b) \\ c^Tx + d - t \end{bmatrix} \right\| \le -c^Tx - d - t \right\} $$