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

Question

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?

Answer 1

Suppose $C$ is also closed, there exists $z_1,z_2\in C$ such that $g(x)=||x-z_1||$, $g(y)=||y-z_2||$. Then $$\lambda g(x)+(1-\lambda)g(y)\ge ||\lambda x + (1-\lambda)y - \lambda z_1-(1-\lambda)z_2||.$$ Using the convexity of $C$, $z=\lambda z_1+ (1-\lambda)z_2\in C$. Hence, $$\lambda g(x)+(1-\lambda)g(y)\ge ||\lambda x + (1-\lambda)y - z||\ge g(\lambda x + (1-\lambda)y).$$ If $C$ is not closed, probably some limit argument may plus the above reasoning should work.

Answer 2

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

Answer 3

Consider any $x,y \in \mathbb{R}^n$, $\lambda \in (0,1)$. Note that by definition of $g$, we have

$\forall \frac{1}{2n}>0, x_n \in C$ such that $||x-x_n||<g(x)+\frac{1}{2n}$

$\forall \frac{1}{2n}>0, y_n \in C$ such that $||y-y_n||<g(y)+\frac{1}{2n}$

Set $z=\lambda x + (1-\lambda)y$ and $z_n = \lambda x_n + (1-\lambda)y_n \in C$ (from convexity). Now, we obtain

$||z-z_n|| = ||\lambda (x-x_n) + (1-\lambda)(y-y_n)|| \leq \lambda ||x-x_n||+(1-\lambda)||y-y_n||< \lambda g(x)+ (1-\lambda) g(y)+\frac{1}{n}$

$\implies inf_{n \in \mathbb{N} } \; ||z-z_n|| \leq inf_{n \in \mathbb{N} } \; [\lambda g(x)+ (1-\lambda)g(y)+\frac{1}{n}] = \lambda g(x)+ (1-\lambda) g(y)$

Note note that $(z_n)$ is a sequence in C (which follows from convexity). Hence,

$ g(z)= inf_{c \in C } \; ||z-c|| \leq inf_{n \in \mathbb{N} } \; ||z-z_n|| \leq \lambda g(x)+ (1-\lambda) g(y) $

$\implies g(\lambda x + (1-\lambda)y) \leq \lambda g(x)+ (1-\lambda) g(y)$

Hence, $g$ is convex.

Q.E.D.

I am not sure. It might be wrong.