A property of projection on a convex and closed set Let $S$ be a convex and closed set. The projection onto $S$ is defined as $P_S(x) = argmin_{y \in S} ||x-y||_2$.
I want to show that if $x \in S$, then for any $y$, 
$$
\langle P_S(y) -x,P_S(y) -y\rangle \leq 0
$$
where $\langle.,.\rangle$ is the inner product. Any suggestion? What does this statement imply?
 A: Hint: if $y \in S$, then $P_S(y) = y$ and $\langle P_S(y) -x,P_S(y) -y\rangle =0$
If $y \not\in S$, then let $z = P_S(y)$, let $H$ be the hyperplane orthogonal to the line segment $yz$ and passing through $z$ and let $U$ be the closed halfspace with $H$ as its boundary that does not contain $y$. Then you can show that $S \subseteq U$ (because if $x \in S \setminus U$, there is a point on the line segment $xz$ that is nearer to $y$ than $z$). But
$$
U = \{ x \mid \langle z - x, z -y\rangle \le 0 \}.
$$
(The geometric implication of the inequality is that $x$ and $y$ are separated by $H$.)
A: Rough sketch of proof:
Find the directional derivative of the function $z \mapsto \|z - y\|_2^2$ at the minimizer $z=P_S(y)$ in the direction $x - P_S(y)$. It will be related to the inner product you have written.
Intuitively, the directional derivative along such directions $x - P_S(y)$ (from $P_S(y)$ to other points of $S$) must be nonnegative. If such a directional derivative is negative, you could take a tiny step away from $P_S(y)$ in that direction and decrease the value of the function $z \mapsto \|z - y\|_2^2$, contradicting the definition of $P_S(y)$ being the minimizer.

Geometric intuition:
You can draw a picture of the two vectors in the inner product. The inequality means that the angle between these two vectors is obtuse.
