# Convex relaxation for the complement of Lorentz cone

Is it possible to obtain a convex relaxation for $$\{ (x,t): t \le \|x\|_2\} \in \mathbb{R}^{d+1}$$ where $x \in \mathbb{R}^d$ and $\|x\|_2$ is the usual Euclidean norm, by moving to higher dimensions and projecting back (the so-called lifting)?

-
The image of a convex set under projection (and any linear map) is convex, so the answer appears to be negative. I may have misunderstood the question. – user53153 Feb 27 '13 at 6:33
Thanks. You are right. What I mean is something which approximates this set in some sense. – passerby51 Feb 27 '13 at 16:21
... I am even open to nonlinear maps as projections if the result is useful. (The question is more or less open-ended.) In deriving convex relaxations/approximations to many problems of interest, this set or its sister $\{ (X,t) : t I \preceq X\}$ comes up. – passerby51 Feb 27 '13 at 16:30
One can map the half-plane $\{t\le 0\}$ onto $\{t\le \|x\|\}$ by a reasonably explicit nonlinear map. Would this help? – user53153 Feb 27 '13 at 16:48
It might. Not quite sure without seeing it. Could you give more details if it is not too much effort? – passerby51 Feb 28 '13 at 18:21

The cone $\{ (x,t): t \le \|x\|_2\}$ cannot be the image of a convex set under a linear map. But it can be realized as the image of the halfspace $\{ (x,t): t \le 0 \}$ set under the following nonlinear map: $F(t,x) = (t+\|x\|_2,x)$. The map is a bijection, the inverse being $F^{-1}(t,x) = (t-\|x\|_2,x)$. It is a kind of shear deformation.