# Proof that $d\left(\mathbf{x},S\right)=\displaystyle\min_{\mathbf{y}\in{S}}\,\|\mathbf{x}-\mathbf{y}\|$ is convex

I'm wondering if the following is sufficient to show that for a closed, convex set $S$ $$d\left(\mathbf{x},S\right)=\displaystyle\min_{\mathbf{y}\in{S}}\|\mathbf{x}-\mathbf{y}\|$$ is convex.

Definition of convexity: $$f\left(\theta\mathbf{x} + \left(1-\theta\right)\mathbf{y}\right)\leq\theta f\left(\mathbf{x}\right) + \left(1-\theta\right)f\left(\mathbf{y}\right),\,\,\forall \mathbf{x}\in \mathbb{R}^{n},\,\,\mathbf{y}\in{\mathrm{dom}\left(f\right)}$$

Convexity for this function: $$\min_{\mathbf{z}\in{S}}\,\|\left(\theta\mathbf{x} + \left(1-\theta\right)\mathbf{y}\right)-\mathbf{z}\|\leq\theta\cdot\min_{\mathbf{y}\in{S}}\,\|\mathbf{x}-\mathbf{y}\| + \left(1-\theta\right)\cdot\min_{\mathbf{z}\in{S}}\,\|\mathbf{y}-\mathbf{z}\|,\,\,\,\theta\in\left[0,1\right]$$

Let $\theta=0$, then the above equation reduces to $$\min_{\mathbf{z}\in{S}}\,\|\mathbf{y}-\mathbf{z}\|\leq\min_{\mathbf{z}\in{S}}\,\|\mathbf{y}-\mathbf{z}\|,$$ which is true.

Let $\theta=1$, then it reduces to $$\min_{\mathbf{z}\in{S}}\,\|\mathbf{x}-\mathbf{z}\|\leq\min_{\mathbf{y}\in{S}}\,\|\mathbf{x}-\mathbf{y}\|.$$

Are these two facts alone enough to state that $d$ is convex?

-
In your second equation, you are using the same symbol $y$ to denote two different points. The equation should start with $\min_{z\in S}\|(\theta x + (1 - \theta)y - z\|\leq\cdots$. –  William Feb 12 '12 at 3:09
You have to specify what $S$ satisfies. At least, $S$ should be closed (otherwise the minimum does not exist) and convex (otherwise you can take two points in $S$ but some point on the line segment is not in $S$). –  Hawii Feb 12 '12 at 3:54
It is not enough to verify $f(\theta x + (1-\theta y)) \leq \theta f(x) + (1-\theta)f(y)$ for $\theta=0,1$. Those cases are trivial for any function; a convex function must satisfy the inequality for $\theta \in (0,1)$. –  sdcvvc Feb 12 '12 at 7:49

Let us note that $d(x,S)=D(x)$ with $D(x)=\inf\limits_{u\in S}d(x,u)$ and let us show that the function $D$ is convex.

Fix $x$ and $y$ in $\mathbb R^n$ and $\theta$ in $[0,1]$, and let $z=\theta x+(1-\theta)y$. For every $u$ in $S$ and $v$ in $S$, $\theta u+(1-\theta)v$ is in $S$ by convexity of $S$, hence $D(z)\leqslant\|w\|$ with $w=z-(\theta u+(1-\theta)v)$.

Now, $w=\theta(x-u)+(1-\theta)(y-v)$ hence the triangular inequality yields $\|w\|\leqslant(\ast)$ with $(\ast)=\|\theta(x-u)\|+\|(1-\theta)(y-v)\|$. By the scalar homogeneity of the norm, $(\ast)=\theta\|x-u\|+(1-\theta)\|y-v\|$.

To sum up, for every $u$ and $v$ in $S$, $$D(z)\leqslant\theta\|x-u\|+(1-\theta)\|y-v\|,$$ hence $$D(z)\leqslant\inf\limits_{(u,v)\in S\times S}\theta\|x-u\|+(1-\theta)\|y-v\|.$$ Since $\inf\limits_{(u,v)\in S\times S}a(u)+b(v)=\inf\limits_{u\in S}a(u)+\inf\limits_{v\in S}b(v)$ for every functions $a$ and $b$, one gets $$D(z)\leqslant\inf\limits_{u\in S}\theta\|x-u\|+\inf\limits_{v\in S}(1-\theta)\|y-v\|=\theta\inf\limits_{u\in S}\|x-u\|+(1-\theta)\inf\limits_{v\in S}\|y-v\|,$$ that is, $D(z)\leqslant\theta D(x)+(1-\theta)D(y)$ as desired.

-

You DO need the triangle inequality. If $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, then via the triangle inequality $$f\left(\theta\mathbf{x} + \left(1-\theta\right)\mathbf{y}\right)\leq f\left(\theta\mathbf{x}\right) + f\left(\left(1-\theta\right)\mathbf{y}\right).$$ The right hand side of that equation is equal to $\theta f\left(\mathbf{x}\right) + \left(1-\theta\right)f\left(\mathbf{y}\right)$. Plugging this in to the definition of convexity allows us to see that $f$ is convex.

-