$d_A(x) = \inf_{a \in A} \|x-a\|$ is convex if and only if $A$ is convex 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.
 A: 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. 
A: 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.
A: 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.
