# Show minimum distance to a convex set is a convex function.

Show that

$$g(x)=\inf_{z \in C}\|x-z\|$$ where $$g:\mathbb{R}^n \rightarrow \mathbb{R}$$, $$C$$ is a convex set in $$\mathbb{R}^n$$ (nor close neither bounded), and $$\|\cdot\|$$ is a norm on $$\mathbb{R}^n$$. Let $$x,y$$ be in $$\mathbb{R}^n$$. We need to show that

$$g(\lambda x +(1-\lambda)y) \leq \lambda g(x)+ (1-\lambda)g(y) \tag{1}$$

I tried the following:

$$\|\lambda x +(1-\lambda)y-z\| \leq \lambda\| x -z\| + (1-\lambda)\| y-z\| \,\, \forall {z \in C}$$ Since

$$g(\lambda x +(1-\lambda)y)=\inf_{z \in C}\|\lambda x +(1-\lambda)y-z\| \leq \|\lambda x +(1-\lambda)y-z\| \,\, \forall {z \in C}$$

So

$$g(\lambda x +(1-\lambda)y)=\inf_{z \in C}\|\lambda x +(1-\lambda)y-z\| \leq \lambda\| x -z\| + (1-\lambda)\| y-z\| \,\, \forall {z \in C}$$

I do not know how to handle the right hand side and apply infimum in a right way because the following is not correct in general

$$\inf_{z \in C}\|\lambda x +(1-\lambda)y-z\| \nleq \lambda \inf_{z \in C} \| x -z\| + (1-\lambda) \inf_{z \in C} \| y-z\|$$

Or maybe my initial way to prove the convexity is wrong. Can you complete my proof or show the claim using another way?

• Hint: you can prove this for any jointly convex function $f(x,z)$, not just for $f(x,z) = ||x-z||$. – LinAlg Dec 2 '18 at 23:44

## 1 Answer

Hint: try starting from the opposite direction, consider the subadditivity of the infimum and see if you can show it that way

• Your statement is not an answer, please write it as a comment and delete your answer. – Saeed Dec 3 '18 at 4:17