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$ Commented 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
    Commented 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
    Commented Mar 12, 2019 at 18:32

You must log in to answer this question.

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