Proving property of Euclidean projection minimization problem Let $X \subseteq \mathbb{R}^n$ be a convex set and $y \not\in X$. Suppose $x^*$ is the Euclidean projection of $y$ onto $X$. That is, $x^*$ is the optimal solution to
$$ \min_{x\in X}\frac{1}{2}\|x-y\|_2^2. $$
I want to prove that
$$\frac{1}{2}\|x-y\|_2^2 - \frac{1}{2}\|x^* - y\|_2^2 \geq \frac{1}{2}\|x-x^*\|_2^2.$$
What I've tried:
I tried breaking up the L2-norm into a summation to prove the statement directly. Something like this:
\begin{align*}
\frac{1}{2}\|x-x^*\|_2^2 & = \frac{1}{2}\sum_{i=1}^{n}(x-x^*)_i^2\\
& \hspace{2cm} \vdots\\
& \le \frac{1}{2}\sum_{i=1}^{n} (x_i-y_i)^2 - (x^*_i - y_i)^2
\end{align*}
But I got stuck in the process. I think I am going about this wrong, as it doesn't look like I can prove a statement such as $(a-b)^2 \le (a-c)^2 - (b-c)^2.$ This looks like something akin to the triangle inequality. Any help would be appreciated!
 A: The necessary and sufficient condition for a point $x^*\in X$ to be a global minimum of a differentiable convex function $f$ over the convex set $X$ is
\begin{equation}
\langle \nabla f(x^*), x-x^* \rangle \ge 0\quad \forall x\in X.\tag{*}
\end{equation}
This can be proved as follows.
If $x^*$ satisfies $(*)$ then $f(x) \ge f(x^*) + \langle \nabla f(x^*), x-x^* \rangle \ge f(x^*) \ \forall x\in X$, which means $x^*$ is a global minimum of $f$ over $X$. To prove the converse, let $x^*$ be a global optimum and assume that there exists $x\in X$ such that $\langle \nabla f(x^*), x-x^* \rangle < 0$. Define $h(t) = f(x^* + t(x-x^*))$ for $t\in [0,1]$, we have
$$h'(t) = \langle \nabla f(x^* + t(x-x^*)), x-x^* \rangle \implies h'(0) = \langle \nabla f(x^*), x-x^* \rangle < 0.$$
Therefore, for $t > 0$ small is enough, we have $h(t)< h(0)$, i.e. $f(x^* + t(x-x^*)) < f(x^*)$, which is a contradiction of $x^*$ being a global optimum.
Now back to the main question. Applying $(*)$ with $f(x) = \frac{1}{2}\|x-y\|_2^2$ we obtain $$\langle x^*-y, x-x^* \rangle \ge 0\quad \forall x\in X.$$
Adding $\frac{1}{2}\|x^*-y\|_2^2 + \frac{1}{2}\|x-x^*\|_2^2$ to both sides of the above, we obtain the desired inequality.
Note that you can obtain a direct proof, instead of using $(*)$, by replacing $f$ by $\frac{1}{2}\|x-y\|_2^2$ in the above proof of $(*)$. The resulting proof is simple and elementary enough. Try that yourself! (Actually I was hesitating between the direct proof and the above proof for the answer, but finally decided that the latter would be better for the readers to see the picture.)
