0
$\begingroup$

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?

  • 0
    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)$.2012-02-12

2 Answers 2

2

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.

0

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.