1
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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$). $\endgroup$
    – Pietro Majer
    Commented Nov 12, 2012 at 8:48
  • $\begingroup$ Thanks Pietro for your answer! Such a short and elegant proof! $\endgroup$
    – Victor
    Commented Nov 12, 2012 at 9:05

1 Answer 1

Reset to default
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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