For a convex set $K$, $x\in \mathbb{R}^d$ and $y=\Pi_K(x) $ (the projection of $x$ onto $K$), we want to show that for any $z\in K$ it holds that: $\|x-z\| \ge \|y-z\|$.

$$ $$

I'm not sure if the following proof is valid:

$$ y=\Pi_K(x) = \arg \min_{y\in K} ||y-x|| \Rightarrow \forall z\in K \langle y-x,y-z\rangle =0 $$ $$ ||y-x||^2_2+||y-z||^2_2=||x-z||^2_2 \quad (Pythagoras)$$ $$ \Rightarrow ||y-z||^2_2 \le ||x-z||^2_2 $$ $$ \Rightarrow||y-z|| \le ||x-z|| $$


The implication $$\arg \min_{y\in K} ||y-x|| \Rightarrow \forall z\in K \langle y-x,y-z\rangle =0$$ is not correct. Indeed, its conclusion is evidently false when $K$ is a ball; it can't be contained in a hyperplane as the equation $\langle y-x,y-z\rangle =0$ claims.

The correct conclusion is that $\langle y-x,y-z\rangle \le 0$. Indeed, for small $t>0$ the point $y+t(z-y)$ is in $K$, hence $$ \|y-x + t(z-y)\|^2 \ge \|y-x\|^2 $$ Expanding the left hand side leads to $\langle y-x , z-y \rangle \ge 0.$

The final step of proving the claim is: $$\|x-z\|^2 = \|x-y +y-z\| = \|x-y\|^2+2\langle x-y, y-z\rangle + \|y-z\|^2 \ge \|y-z\|^2 $$


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.