0
$\begingroup$

Consider the compact convex set $X = \{ x \in \mathbb{R}^n \mid x \geq 0, \ \underline{1}^\top x = 1 \}$.

I am wondering if the projection onto $X$ is the composition of the projection on $[0,1]^n$ and the projection onto $\{x \mid \underline{1}^\top x = 1\}$, namely if $$ P_X(\cdot) = P_{ [0,1]^n }\left( P_{ \{x \in \mathbb{R}^n \mid \underline{1}^\top x = 1\} }(\cdot) \right). $$

Comment: the projection onto $X$ is defined as $P_X(x) := \arg \min_{y \in X} \left\| x-y\right\| $.

$\endgroup$
1
$\begingroup$

No, it is not.

$H=\{x\;|\;\underline 1^\top x=1\}$ is a hyperplane, $[0,1]^n$ a hypercube, and $X$ is a simplex which results from intersecting these two. But the problem is that the second projection may well leave the hyperplane and therefore result in a point outside the simplex.

Here is an example for $n=3$: Consider the point $(8,8,-15)$ which already lies in $H$. Its projection onto $X$ would be $(\frac12,\frac12,0)$ which has distance $\frac{15}2\sqrt6\approx18.4$. But the corner of the cube at $(1,1,0)$ has distance $\sqrt{323}\approx18.0$ so it is closer.

$\endgroup$
3
  • 1
    $\begingroup$ @Adam: Adding such a requirement changes nothing, since you can still find points which project onto the example point. E.g. $P_H(-2, -2, -25)=(8,8,-15)$ so there you are back in the example case I stated, even from an all-negative starting point. $\endgroup$ – MvG Apr 27 '14 at 8:42
  • $\begingroup$ Right, thanks. Is the claim still false if the argument is non-positive? Namely, $P_X(x)=P_{[0,1]^n}\left(P_H(x) \right)$ for all x s.t. $x \leq 0$? $\endgroup$ – user693 Apr 27 '14 at 8:42
  • $\begingroup$ Thanks also for this last comment. Now I am thinking about the projection of non-positive vectors onto $H = \{x \mid 1^\top x = 1\}$ and then onto the simplex $S = \{ x \mid x \geq 0, 1^\top x \leq 1 \}$. Namely I am thinking whether $P_X(x) = P_{ S }\left( P_X(x) \right)$ for all $x$ such that $x \leq 0$. $\endgroup$ – user693 Apr 27 '14 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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