Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
+1 for context and giving it some serious thought before posting. – Arturo Magidin Mar 21 '11 at 16:43
$\ell_2$ usually denotes the space of all square-summable sequences; do you mean the usual Euclidean norm? – Arturo Magidin Mar 21 '11 at 16:45
i dont think you need to use convexity again (you only need it to show that the point is unique). the $y_n$ seem to be going to both $y$ and $y'$. argue that they cant using the triangle $x,y,y'$ (look at $|x-x_n|$ small wrt $|y-y'|$) – yoyo Mar 21 '11 at 17:14
@yoyo: I presume you meant "compactness"? It's true that you don't need compactness again and it's only there to show that the point is unique; you do need convexity again, though, since otherwise the nearest point could "jump". – joriki Mar 21 '11 at 17:17
@joriki: actually, you don't need compactness at all, requiring $K$ to be closed and convex suffices. You can show that any sequence approximating the distance of $x$ to $K$ is Cauchy by considering the midpoints of that sequence and using the parallelogram law. – t.b. Mar 21 '11 at 19:43
up vote 7 down vote accepted

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$.

share|cite|improve this answer
I understand the proof and the idea behind. Very nice. Thanks. – echoone Mar 23 '11 at 3:28
@echoone: You're welcome. (I'm glad you understand the idea, too :-) – joriki Mar 23 '11 at 8:58

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.