1
$\begingroup$

Let $f_C$ be the convex envelope of $f$ on a non-empty convex set $C \subset \mathbb{R}^n$

I need to show that $\{ x^∗ \in C : f(x^∗) \leq f(x), \forall x \in C \} \subset \{x^∗ \in C : f_C(x^∗) \leq f_C(x), \forall x \in C \}.$

Right now, I can show that: $\{ x^∗ \in C : f(x^∗) \leq f(x), \forall x \in C \} \subseteq \{x^∗ \in C : f_C(x^∗) \leq f_C(x) \forall x \in C\}$

However, I need a counterexample to show that the equality in the subset relation does not hold.

For reference: The convex envelope of $f$ on $C$, denoted $f_C : C \rightarrow R$ is a convex function such that $f_C(x) \leq f(x) \forall x \in C$. The definition also requires that if $g$ is any other convex function on $C$ for which $g(x) \leq f(x), \forall x \in C$ then $f_C(x) \geq g(x), \forall x \in C$.

EDIT: Sorry for this, turns out that there was a typo and the $\subset$ should have actually been a $\subseteq$. After all, f could be a convex function in which case, it would be the same as it's convex hull.

2 Answers 2

0

EDIT: Sorry for this, turns out that there was a typo and the ⊂ should have actually been a ⊆. After all, f could be a convex function in which case, it would be the same as it's convex hull.

0

Take the function $f(x)=x^2 (x-1)^2$ on $I=[-2,2]$, then the global minimum of f are $0,1$. If $f_C$ is its convex envelope, then you showed that 0,1 are global minimum for $f_C$ but then all the points in $[0,1]$ must be global minimum. (or in the general case, the global minimum of $f_C$ will contain the convex hull of the global minimum of $f$).