Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.