Let $K$ be a nonempty closed, convex subset of $R^d$. Prove that if $x\notin K$, then there exists a unique point $y\in K$ that is closest to $x$.

Question

Let $K$ be a nonempty closed, convex subset of $R^d$. Prove that if $x\notin K$, then there exists a unique point $y\in K$ that is closest to $x$.

My attempt: Suppose y and z are 2 different point that are both closest to x. Then,

$||x-y||=\mbox{inf}\{||x-a||: a \in S\}$ and $||x-z||=\mbox{inf}\{||x-b||: b \in S\}$. Consider the midpoint $w$ of the line that joins y to z. Then

$w=\frac{||y-z||}{2}=\frac{||y-x+x-z||}{2}\le \frac{||x-y||+||x-z||}{2}\le \frac{||x-a||+||x-b||}{2}$ for any $a \in S$. I don't know how to go from here; I thought the midpoint would be zero since we are trying to show that these 2 points are the same point, so is the midpoint formula I used incorrect? Also can you use $a$ for both infimums or do I have to use $a$ and $b$ distinctly for y and z as I did?

Answer 1

A couple remarks: there are two parts to this question, existence and uniqueness. Let's start with existence. Since the function $f_x\colon\mathbb{R}^n \to \mathbb{R}$ defined by $f_x(u) = \| x-u\|$ is continuous (exercise), and $K$ is closed and nonempty, we can fix $u_0 \in K$ and remark that $$\inf_{y\in K} f_x(y) = \inf_{y\in K,\; \|x-y\| \leq \|x-u_0\|} f_x(y)$$ Convince yourself of this, then see if you can prove that $$\{y\in K \mid \|x-y\| \leq \|x-u_0\|\}$$ is compact. (Hint: write it as an intersection of the closed set $K$ with a bounded sublevel set for $f_x$.) It follows from basic analysis that the infimum is attained so existence follows. Note that we haven't used any convexity yet, so we suspect that we will have to use it to prove uniqueness.

To show uniqueness, you are on the right track with considering the midpoint (this is where convexity comes in to guarantee the midpoint will belong to $K$). Try to show that $\|y-z\| = 0$ while making use of the fact that the midpoint is in $K$. I offer you the following hint: use the parallelogram law $$\|u - v\|^2 + \|u+v\|^2 = 2(\|u\|^2 + \|v\|^2)$$ for an appropriate choice of $u$ and $v$.

Answer 2

Suppose you’ve proven for any $x$ that $$R:= d(x, K) := \inf \{d(x, y): y \in K \}$$ always exists, and there is always at least one point $a$ which achieves the infimum (ie $d(x, a) = R$).
If there’s more than one such point for some $x$, say $d(x, a) = d(x, b) = R$ for distinct points $a, b,$ then every point on the line segment connecting $a$ to $b$ is both inside $K$ (by convexity) and in the interior of $B(x, R)$ (since $n$-spheres are convex). That means there are points in $K$ closer to $x$ than $R$, which contradicts the minimality of $R$. Done.