Welcome to MathOverflow

Question

0

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!

flag	asked Nov 12 at 8:02 Victor Cheng 1●2

1

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 at 8:48

Thanks Pietro for your answer! Such a short and elegant proof! – Victor Cheng Nov 12 at 9:05

Didier Piau · Accepted Answer · 2012-11-12 08:22:36Z UTC

0

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

answered Nov 12 at 8:22

Didier Piau
4,193●1●10●15

	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 at 8:53
	Yes, h is convex. Note that h is the maximum of a (covex) function and a number (not a function). – Didier Piau Nov 15 at 12:16

Yiyong Feng · Answer 2 · 2012-11-12 08:45:59Z UTC

0

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

answered Nov 12 at 8:45

Yiyong Feng
21●2

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. – Didier Piau Nov 15 at 12:19

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.