Show that $\|\pi_c(y)-x\|_2^2 + \|\pi_c(y)-y\|_2^2 \leq \|x-y\|^2$, $\forall x$ in closed convex set $C$

Question

Let $\mathcal{C}$ be the projection operator onto a closed convex set $\mathcal{C}$. Prove $\|\pi_c(y)-x\|_2^2 + \|\pi_c(y)-y\|_2^2 \leq \|x-y\|^2$, $\forall x \in \mathcal{C}$

In which $\pi_c(y)$ is the projection of $y$ on set $\mathcal{C}$.

I have tried to expand $\|x-y\|_2^2$ and apply Cauchy-Schwarz inequality to get
$\|\pi_c(y)-x\|^2 - \|\pi_c(y)-y\|_2^2 \leq \|x\|_2^2 -\|y\|_2^2-2\|\pi_c(y)\|(\|x\|_2+\|y\|_2)$
but this does not yield any useful result. I hope to get some insights

Answer 1

If $f$ is convex, then the constrained optimization problem $$\min_z f(z) \text{ subject to } z \in C$$ has the following first-order optimality condition: a point $z^*$ is optimal if and only if $$\langle \nabla f(z^*), x - z^* \rangle \ge 0, \text{ for all } x \in C.$$ The intuition is that at the optimizer, feasible directions must have increasing gradient.

---

• Use this fact for $f(z) = \|y-z\|^2$ to show that $$\langle \pi_C(y) - y, x - \pi_C(y) \rangle \ge 0.$$
• Write $x-y = (x-\pi_C(y)) + (\pi_C(y) - y)$ to expand $\|x-y\|^2$. You will get the two terms on the left-hand side plus a cross term which you should check to be nonnegative.