# distance inequality for a point in a convex set closest to a given point outside of the set

Let $C$ be a closed convex subset of a Hilbert space $H$, let $\omega \in C$, $\tau \notin C$. According to the Hilbert projection theorem, there is a unique point $\tau' \in C$ such that $\Vert \tau - \tau' \Vert = \min_{\sigma \in C} \Vert \tau - \sigma \Vert$.

Drawing a picture, it seems obvious to me that $\Vert \omega - \tau' \Vert \leq \Vert \omega - \tau \Vert$. However, I don't know how to prove it. Can anyone help me?

-

First, notice that $C$ is contained in a half-space that separates the set from $\tau$, specifically $\langle w-\tau,\tau'-\tau \rangle \geq ||\tau-\tau'||^2$. This is the first order optimality condition for the distance minimization problem. (To see this, note that $|| (\lambda w + (1-\lambda) \tau')-\tau||^2 - ||\tau'-\tau||^2 \geq 0$, $\forall \lambda \in [0,1]$, by convexity. Now expand the expression, divide across by $\lambda>0$ and then let $\lambda \rightarrow 0$. )
Then form the following estimate: $|| w - \tau||^2 = ||w - \tau' + \tau' - \tau||^2 = || w - \tau'||^2 + 2 \langle w-\tau',\tau'-\tau \rangle + ||\tau' - \tau||^2$ $= || w - \tau'||^2 + 2 (\langle w-\tau,\tau'-\tau \rangle -||\tau' - \tau||^2)+ ||\tau' - \tau||^2$ $\geq || w - \tau'||^2 + ||\tau' - \tau||^2$. This is slightly stronger than the result you were looking for.
@copper.hat, I am wondering, in $\mathbb{R}^n$, whether the result you have proved holds only for $\ell_2$-norm (i.e., only in Hilbert spaces). – Ashok Apr 9 '12 at 14:36
I don't know about only in Hilbert space. If you choose the $l_{\infty}$ norm it is not true. Take $C = \{ (x_1,x_2) | x_2 \geq 1 \}$, and $\tau = 0$. Choose $\tau' = (1,1)$, it is easy to see this minimizes the $l_{\infty}$ norm. Now choose $w = (-1,1)$. Then $||w-\tau'|| = 2$, whereas $||w-\tau|| = 1$, which violates the desired inequality. – copper.hat Apr 9 '12 at 17:06