# Is minimum of convex envelope the same as minimum of the original function?

Hello everyone my question is:

$Question:$ Consider a function $f:X \rightarrow \mathbf R$ where $X$ is a convex subset of $\mathbf{R}^n$. The convex envelope of $f$ over $X$ is defined as the pointwise supremum of convex under-estimator of $f$, denoted as $g$. I want to ask if the minimum of $f$ over $X$ is the same as the minimum of $g$ over $X$?

This sounds intuitive but I am not sure if this is true. If yes, how to prove it rigorously? And then does it mean we can use convex envelopes to replace any non-convex function to make some hard non-convex optimization easy?

Thank you in advance!

• Just note that constant function $g_0=\inf_X f$ is a convex under-estimator of $f$. So $g_0\le g \le f$ and $\inf_X g =\inf_X f$. (It does not mean that replacing $f$ by $g$ makes life easier, especially if to compute $g(x)$ you have to solve the optimization problem for all $x$). Nov 12 '12 at 8:48
• Thanks Pietro for your answer! Such a short and elegant proof! Nov 12 '12 at 9:05

## 1 Answer

If $g(x)\leqslant f(x)-\varepsilon$ for some $x$ in $X$ such that $f(x)$ is the minimum of $f$ on $X$, then the function $h=\max\{g,f(x)\}$ is a convex under-estimator of $f$ such that $h\geqslant g$ everywhere and $h\gt g$ around $x$. This contradicts the definition of $g$.

• The function $h=\max \{g,f(x)\}$ might not be convex especially when $f(x)$ is nonconvex.
– user28039
Nov 12 '12 at 8:45
• Thanks Didier! But I wonder if $h$ is a convex function? If seems that $h$ maybe non-convex when $f$ is non-convex. Nov 12 '12 at 8:53
• Yes, h is convex. Note that h is the maximum of a (covex) function and a number (not a function).
– Did
Nov 15 '12 at 12:16
• The whole point is when $f$ is not convex Apr 16 '14 at 14:30
• @CristóbalGuzmán Off-topic. Please refer to my comment dated Nov 15 '12 at 12:19 on Yiyong Feng's post.
– Did
Apr 16 '14 at 14:36