# 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9864588379859924, "perplexity": 83.51889097790279}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-26/segments/1466783399522.99/warc/CC-MAIN-20160624154959-00040-ip-10-164-35-72.ec2.internal.warc.gz"}