Continuity of a function that maps a point to the closest point on a compact convex set

Question

Let $K$ be a nonempty compact convex subset of $\mathbb R^n$ and let $f$ be the function that maps $x \in \mathbb R^n$ to the unique closest point $y \in K$ with respect to the $\ell_2$ norm. I want to prove that $f$ is continuous, but I can't seem to figure out how.

My thoughts: Suppose $x_n \to x$ in $\mathbb R^n$. Let $y_n = f(x_n)$ and let $y = f(x)$. By the compactness of $K$, there is a convergent subsequence $(y_{k_n})$ that converges to some $y' \in K$. If $y \ne y'$, then $\|x-y\| < \|x-y'\|$. Furthermore, any point $z \ne y$ on the line segment joining $y,y'$ also satisfies $\|x-y\|<\|x-z\|$. I don't know where to go from here. Any tips?

Answer 1

Consider two points $a$ and $b$, and for simplicity and without loss of generality, assume $f(a)=0$. Then the line through $f(a)$ and $f(b)$ can be described by $\lambda f(b)$, and all points with $0\le\lambda\le1$ are in $K$. The point nearest to some point $c$ on this line is determined by

$$(\lambda_c f(b) - c)\cdot f(b)=0$$

(the vector from the nearest point to $c$ is perpendicular to the line), which gives

$$\lambda_c =\frac{c\cdot f(b)}{f(b)\cdot f(b)}\;,$$

where we can divide by $f(b)\cdot f(b)$ since the case $f(b)=0=f(a)$ obviously doesn't destroy continuity. We know that $f(a)$ is the closest point to $a$ in $K$, and $f(b)$ is the closest point to $b$ in $K$. It follows that $\lambda_a \le 0$ and $\lambda_b \ge 1$. Putting everything together, we have

$$\|f(b)-f(a)\|=\|f(b)\|=1\|f(b)\|\le(\lambda_b-\lambda_a)\|f(b)\|=\frac{(b-a)\cdot f(b)}{f(b)\cdot f(b)} \|f(b)\| \le \|b-a\|\;.$$

Thus, for given $\epsilon$, you can take $\delta=\epsilon$ to get $\|b-a\|<\delta\Rightarrow \|f(b)-f(a)\|<\epsilon$.

Answer 2

Another way, for the record:

Since $f(a)$ is optimal, $$(f(b) - f(a))\cdot (a - f(a)) \le 0.$$ Similarly, since $f(b)$ is optimal, $$(f(b)-f(a))\cdot(f(b) - b)\le 0.$$

When we sum these two inequalities and rearrange, we get $$\begin{align}\|f(a)-f(b)\|^2&\le (f(b)-f(a))\cdot(b-a) \\ & \le \|a-b\|\|f(a)-f(b)\|,\end{align}$$ with the second inequality by Cauchy-Schwarz. Dividing through, we are done.