A property of projection on a convex and closed set

Question

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?

Answer 1

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

Answer 2

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.