Projections onto convex sets and Lipschitz condition

Question

Let $K\subset\mathbb{R}^n$ be a non-empty convex set. Let $\pi_K$ be the projection onto $K$, that is, $$\pi_K(x)=\mathrm{argmin}_{k\in\mathbb{R}^n}\{\|x-k\|_2:k\in K\}.$$ Let $\|\cdot\|_2$ denote the Euclidean $2$-norm. I want to show that for all $x,y\in\mathbb{R}^n$, we have $$\|\pi_K(x)-\pi_K(y)\|_2\le \|x-y\|_2.$$

An article I am reading claims this is trivial, but I'm not sure how to proceed. It seems intuitively true if $K$ is a projection onto a subspace, say onto $K=\mathrm{span}(e_1,\dots,e_k)$ for some $k<n$ (since in the last few coordinates, nothing is contributing to the $2$-norm).

Answer 1

Note that since $K$ is convex from definition of the projection you have for all $k \in K$ and $\lambda \in (0 ,1)$ that $$ \| x - \pi_{K} (x) \|^2 \leq \|x -(\lambda k +(1- \lambda) \pi_{K} (x)) \|^2 = \| x - \pi_{K} (x) - \lambda (k - \pi_{K} (x)) \|^2$$ By opening up the above norm-squared and letting $\lambda \to 0$, you can conclude that $$ \langle x - \pi_{K} (x) \; , \; k - \pi_{K} (x) \rangle \leq 0 \quad \quad \forall k\in K $$ similarly $$ \langle y - \pi_{K} (y) \; , \; k - \pi_{K} (y) \rangle \leq 0 \quad \quad \forall k\in K $$

Now by settting $k = \pi_{K} (y)$ in first inequality and then $k = \pi_{K} (x)$ in the second inequality, afteradding later inequality we have $$ \langle x-y + (\pi_{K}(y) - \pi_{K} (x) ) \; , \; \pi_{K}(y) - \pi_{K} (x) \rangle \leq 0 $$ Thus $$ \| \pi_{K}(y) - \pi_{K} (x)\|^2 \leq \langle x-y \; , \; \pi_{K}(y) - \pi_{K} (x) \rangle \leq \; \| y -x \| \; \| \pi_{K}(y) - \pi_{K} (x)\| $$ This gives you the desired inequality.

Answer 2

(This is a rewrite of an egregiously incorrect previous answer.)

I have always found the usual proof of this fact a little unsatisfactory and lacking in geometric intuition. Here is a more intuitive proof.

$K$ needs to be closed to ensure that a $\min$ exists.

We can assume that $\pi_K(x) \neq \pi_X(y)$ otherwise the result is trivial.

Let $L$ be the line $p(t) = \pi_K(x)+t (\pi_K(y)-\pi_K(y))$ and let $P$ be the orthogonal projection onto this line. It is straightforward to show that $\|P\| = 1$, and hence $\|Px-Py\| \le \|x-y\|$. This is the essential fact here.

Let $t_x,t_y$ be such that $p(t_x) = Px, p(t_y) = Py$. Note that we must have $t_x \le 0$ and $t_y \ge 1$, as otherwise the definition of $\pi_K(x)$ or $\pi_K(y)$ would be contradicted. Then $\|Px-Py\| = \|p(t_x)-p(t_y)\| = (t_y-t_x) \| \pi_K(x)-\pi_K(y)\| \ge \| \pi_K(x)-\pi_K(y)\|$.

Addendum:

To see why $t_x \le 0$, let $\phi(t)=\|x-p(t)\|^2 = \|x-Px\|^2+(t-t_x)^2\|\pi(x)-\pi(y)\|^2$.

Note that $\phi$ is convex, strictly decreasing for $t \le t_x$ and strictly increasing for $t \ge t_x$. Also note that $p(t) \in K$ for $t \in [0,1]$ so $\phi(t) \ge \phi(0)$ on $t \in [0,1]$.

In particular, we must have $t_x \le 0$ otherwise $\phi$ would be strictly decreasing on $[0,t_x]$ which would be a contradiction.