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

-
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$). –  Pietro Majer Nov 12 '12 at 8:48
Thanks Pietro for your answer! Such a short and elegant proof! –  Victor Cheng Nov 12 '12 at 9:05

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

-
Thanks Didier! But I wonder if $h$ is a convex function? If seems that $h$ maybe non-convex when $f$ is non-convex. –  Victor Cheng 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 –  Cristóbal Guzmán 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
OK. However, you are assuming a minimizer exists. You should adapt your answer to the case the infimum is not attained. –  Cristóbal Guzmán Apr 16 '14 at 14:56

The function $h=\max \{g,f(x)\}$ might not be convex especially when $f(x)$ is nonconvex.

-
Thanks for this comment on my answer (which should have been posted as a comment on my answer and not as an answer). Let me suggest that you read the answer again, focussing on the distinction between functions and constants. –  Did Nov 15 '12 at 12:19