Projections onto convex sets and Lipschitz condition 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).
 A: (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.
A: 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.
