1
$\begingroup$

Consider the closed convex set

$$ C = \{ x \in R^n : \alpha \| x \| + \langle c, x \rangle \leq 0 \}, $$

for constants $\alpha > 0$, $c \in R^n$.

My question is whether the Euclidean projection $x \mapsto \arg \min_{y \in C} \|y-x \|$ admits a simple closed form solution as it does for the second order cone

$$ K = \{ (x, t) \in R^{n+1} : \alpha \|x\| + t \leq 0 \}. $$

$\endgroup$
2
  • $\begingroup$ what's the answer for $K$? $\endgroup$ Mar 12, 2019 at 14:41
  • 1
    $\begingroup$ In both cases you can write the conditions as $x^TAx\leq 0$ for some symmetric matrix A. The boundary is the set with $=0$ and the tangent space is the kernel of A. From this it should be possible to compute the projection. However I dont know if there is an explicit formula. $\endgroup$
    – user35593
    Mar 12, 2019 at 16:40

1 Answer 1

1
$\begingroup$

Assume wlog $\|c\|=1$. $C = \{0\}$ if $\alpha > 1$, while it is the ray $(-\infty, 0] c$ if $\alpha = 1$. So let's suppose $0 < \alpha < 1$.

If $y = t c + w$ where $t \in \mathbb R$ and $\langle c, w\rangle = 0$, then $y \in C$ iff $t \le - \alpha \|w\|/\sqrt{1-\alpha^2}$. If $x \notin C$, we write $x = s c + u$, $\langle c, u \rangle = 0$ and taking $y$ in the boundary of $C$ we want to choose $w$ to minimize $$ \|x - y \|^2 = (s + \alpha \|w\|/\sqrt{1- \alpha^2})^2 + \|w - u\|^2$$ Clearly we want $w = r u$ for some $r > 0$, and I get $$ r = 1 - \alpha^2 - \frac{s \alpha}{\|u\|} \sqrt{1-\alpha^2} $$

$\endgroup$
1
  • $\begingroup$ That looks great. Thank you! $\endgroup$
    – yon
    Mar 12, 2019 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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