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} $$


$$ 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?

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.