0
$\begingroup$

I'm having difficulties in proving that the projection of $$(s,y)\in R \times R^{n}$$ onto the second-order cone $$Q^{n+1} = \{(t,x) \in R \times R^n : \|x\|_2 \leq t \}$$ is $$ \frac{s+\|y\|_2}{2\|y\|_2} (\|y\|_2,y)$$ when $\|y\|_2 > s $ and $ \|y\|_2 > -s $.

I tried to first show that to minimize the distance, $x$ must be parallel to $y$, then I construct $$\alpha (\|y\|_2 + \epsilon,y)$$ and minimize the distance over $\alpha$ and $\epsilon$.

I indeed come up with two quadratic functions individually attains its minimum when $$\epsilon = 0$$ and $$\alpha = \frac{s+\|y\|_2}{2\|y\|_2}$$ but I still have $$-\frac{s^2(\|y\|_2+\epsilon)}{2\|y\|_2} - \frac{{\|y\|_2}^3}{2\|y\|_2 + \epsilon}$$ which attains its maximum when $$\epsilon = 0$$ As a result, I can't say the distance attains its minimum accordingly. Is there any other method or elementary method to prove the optimal solution is $$ \frac{s+\|y\|_2}{2\|y\|_2} (\|y\|_2,y)$$ when $\|y\|_2 > s $ and $ \|y\|_2 > - s $ ?

Improve this question
$\endgroup$
4
  • $\begingroup$ What is a "first-order" cone? $\endgroup$
    – Alex M.
    Commented Nov 7, 2017 at 14:47
  • $\begingroup$ Does $\|x\|_2$ mean the length of $x$ in the Euclidean metric? $\endgroup$
    – Ben McKay
    Commented Nov 7, 2017 at 15:37
  • $\begingroup$ The $(0.0), (s,y)$ and its projection must build a right-angled triangle. $\endgroup$
    – user35593
    Commented Nov 7, 2017 at 17:12
  • 2
    $\begingroup$ @ Alex: For $p\geq 1$, a $p$-th order cone is defined as $\{(t,x) \in \mathbb{R} \times \mathbb{R}^{n} : ||x||_{p} \leq t \}$. The second-order cone is same as Lorentz cone, ak.a. ice-cream-cone. This is standard terminology in optimization-control. $\endgroup$
    – Abhishek Halder
    Commented Nov 7, 2017 at 18:50

1 Answer 1

Reset to default
2
$\begingroup$

The proof can be found in H.H. Bauschke's 1996 doctoral dissertation: Projection Algorithms and Monotone Operators (p. 40, Theorem 3.3.6).

P.S. I wonder what the downvote is for.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If I am not mistaken, your case is $\alpha = 1$. So there is nothing to use, the theorem is indeed proving a formula for projection onto second order cone. The expression you are looking for is one with "otherwise" condition. $\endgroup$
    – Abhishek Halder
    Commented Nov 8, 2017 at 0:53

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