## Projection on a convex set is closer to any point of the set

A useful little fact for constrained optimization. Let  $\mathcal{X}$  be a convex set, and consider  $x \in \mathcal{X},$  $y \notin \mathcal{X},$  and its projection on  $\mathcal{X}:$

$\displaystyle \Pi_{\mathcal{X}}(y) = \min_{x \in \mathcal{X}} \|x-y\|_2.$

As quickly follows from the separation theorem with hyperplane containing $\Pi_{\mathcal{X}}(y),$  for any  $x \in \mathcal{X}$  the angle between  $\displaystyle \Pi_{\mathcal{X}}(y)\, y$  and  $\displaystyle \Pi_{\mathcal{X}}(y)\, x$  is obtuse.  Consequently, the following “Pythagorean inequality” holds for any  $x \in \mathcal{X}$  (note the inequality direction and also that the norm is squared):

$\displaystyle \|y-\Pi_{\mathcal{X}}(y)\|_2^2 + \|\Pi_{\mathcal{X}}(y) - x\|_2^2 \le \|y-x\|_2^2.$

In particular, the projection of any external point  $y$  is closer to each point of the set than the initial point:

$\displaystyle \|\Pi_{\mathcal{X}}(y) - x\|_2^2 \le \|y-x\|_2^2.$

This fact is used in the analysis of the  Subgradient Projection Method,  a basic method for nonsmooth constrained optimization.