Projecting a point onto a convex set decreases its distance from each point of that set

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||$$

1 Answer

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$$