$d_A(x) = \inf_{a \in A} \|x-a\|$ is convex if and only if $A$ is convex

Question

Let $A \subset \mathbb{R}^n$ be closed and $d_A(x) = \inf_{a \in A} \|x-a\|$. I need to show that $d_A$ is convex if and only if $A$ is convex.

I have no good ideas in either direction. Can somebody please give me a hint?

For the direction ($\Longleftarrow$), my attempt was:

Let $a_1 := \operatorname*{argmin}_{a \in A} \|x-a\|, a_2 := \operatorname*{argmin}_{a\in A} \|y-a\|$, then:

\begin{align*} d_A(x) &= \inf_{a \in A} \|\lambda x + (1 - \lambda)y - a\| = \inf \|\lambda(x-a) + (1-\lambda) (y-a)\|\\ &\leq \lambda \|x-a_1\| + (1-\lambda)\|y-a_2\| = \lambda d_A(x) + (1-\lambda)d_A(y) \end{align*}

However, I'm not sure whether the inequality in the third step is actually correct.

Answer 1

In case $A$ is convex: For $x_i \in A$ let $a_i = \operatorname{argmin}_{a\in A} \| x_i - a \|$, which is an element of $A$ as $A$ is closed. For $t\in (0,1)$ we have $(1-t)a_1 + ta_2 \in A$ as $A$ is convex and thus $$d_A((1-t)x_1 + tx_2) \le \| (1-t)x_1 + tx_2 - ((1-t)a_1 + ta_2)\| \le (1-t) d_A(x_1) + t d_A(x_2).$$

In case $d_A$ ist convex: For $x,y\in A$ and $t\in (0,1)$ show that $d_A( (1-t) x + ty) = 0$ and thus $(1-t)x+ty\in A$ as $A$ is closed.

Answer 2

Let $A$ be convex. Let $x,y$ be arbitrary.

Then $d(tx+(1-t)y)=\inf_{a\in A}\|tx+(1-t)y-a\|\le$

$\le t\inf_{a\in A}\|x-a\|+(1-t)\inf_{a\in A}\|y-a\|=td(x)+(1-t)d(y)$.

UPDATE. The proof of the inequality. Assume that $t\inf_{a\in A}\|x-a\|+(1-t)\inf_{a\in A}\|y-a\|<\inf_{a\in A}\|tx+(1-t)y-a\|$. So there are $a_1,a_2$ from $A$ such that $t\|x-a_1\|+(1-t)\|y-a_2\|<\inf_{a\in A}\|tx+(1-t)y-a\|$.

But $a=ta_1+(1-t)a_2$ lies in $A$ since it is convex.

So we have $t\|x-a_1\|+(1-t)\|y-a_2\|<\|tx+(1-t)y-a\|$ for this $a$.

But $\|tx+(1-t)y-a\|=\|t(x-a_1)+(1-t)(y-a_2)\|\le t\|x-a_1\|+(1-t)\|y-a_2\|$ by triangle inequality. This is the contradiction.

Answer 3

For arbitrary functions $g,h : \mathbb{R}^{n} \to \mathbb{R}$ there is only an inequality like $$ \inf(g) + \inf(g) \leq \inf(g+h). $$ In your special case, where $g,h$ are norms, it is actually easy to give an explicit counterexample to your question: $$ 1 = \inf \{\left\|x+(1-x)\right\| : x \in [0,1]\} \leq \inf\{\left\|x\right\|+ \left\|1-x\right\|: x\in [0,1]\} $$ so the infimum of the sum is actually bigger or equal than one. On the other hand $$\inf\{\left\|x\right\|: x \in [0,1]\} = \inf\{\left\|1-x\right\| : x \in [0,1]\} = 0,$$ so the sum of the infima is equal to zero.