MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
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. – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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