Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

2 Answers

up vote -1 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|improve this answer
    
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 2 days ago
    
@CristóbalGuzmán Off-topic. Please refer to my comment dated Nov 15 '12 at 12:19 on Yiyong Feng's post. –  Did 2 days ago
    
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 2 days ago
show 1 more comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

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.