## 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. 1. Артур says: