Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.