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

share|cite|improve this question
up vote 2 down vote accepted

I have skipped some details below for brevity.

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.

share|cite|improve this answer
There seems to be some mistake in the last inequalities. – Ashok Apr 9 '12 at 7:17
Thanks @Ashok, I removed the errant '. – copper.hat Apr 9 '12 at 8:11
Perfect, thanks a lot! – Tom Jonathan Apr 9 '12 at 8:22
@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

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.