# Epigraph of closed convex hull of a function


What I have to prove is: $\epi(\co f) = \co(\epi f)$

Let me show you what I've done.

\begin{align} \epi(\co f) &= \left \{ (x, \lambda) \in X\times \overline{\mathbb{R}} \mid \lambda \geq \co f(x) \right \} \\ &= \left \{ (x, \lambda) \in X\times \overline{\mathbb{R}} \mid \forall \psi \ \text{affine minorant of } f: \lambda \geq \psi(x)  \right \} \\ &= \left \{ (x, \lambda) \in X\times \overline{\mathbb{R}} \mid \forall \psi \ \text{affine minorant of } f: (x, \lambda) \in \epi(\psi)  \right \} \\ &= \bigcap\limits_{\substack{\psi \text{ affine minorant of }f}} \epi (\psi) \end{align}

Since every $\epi(\psi)$ is a closed and convex set that contains $\epi f$, it follows that $\text{epi}(\co f)$, is closed convex that contains $\epi f$. Furthermore, $\co(\epi f)$ is the intersection of every closed convex set that contains $\text{epi} \ f$, we've got the inclusion $\text{epi}(\co f) \supseteq \co(\epi f)$

For the other inclusion. Assume that there exists $(x_0, \lambda_0) \in \epi (\co f)\setminus \co(\epi f)$. Using Hahn-Banach, we can strictly separate $(x_0, \lambda_0)$ from $\co(\epi f)$, i.e there exists $(x^*,r) \in X^*\times \mathbb{R},(x^*,r) \neq (0,0), \exists c \in \mathbb{R}$ such that $$x^*(x_0) + r\lambda_0 < c < x^*(x) + r \lambda \qquad \forall (x, \lambda) \in \co(\epi f)$$

It's clear that $r\geq 0$. Otherwise, we can take $\lambda$ large enough and contradicts the inequality. Also, $r \neq 0$, in other case, $x^*$ would be a bounded function which leads to the conclusion $x^* \equiv 0$, but that contradicts the fact that $(x^*, r) \neq (0,0)$. Thus, we have that $r>0$. WLOG, let's take $r=1$, what we have is: $$\exists x^* \in X^*, c_1 \in \mathbb{R} : \quad x^*(x_0) + \lambda_0 < c_1 < x^*(x) + \lambda \qquad \forall (x, \lambda) \in \co(\epi f)$$

Here is where I think there should be a contradiction, but I can not realize what it is. I only have noticed that $(x_0, \co f(x_0)) \notin \co(\epi f)$.

Any ideas?

Regards.

Edit:

Since $\epi f \subseteq \co \left (\epi f\right )$, in the last inequality we can choose $\lambda = f(x)$. Hence, we have $$-x^*(x) +x^*(x_0) + \lambda_0 < -x^*(x) + c_1 < f(x)$$ Therefore, both $-x^*(x) +x^*(x_0) + \lambda_0$ and $-x^*(x) + c_1$ are affine functions everywhere less than $f$. By definition of $\co f$: $$\co f(x_0) \geq -x(x_0) + c_1 > -x^*(x_0) + x^*(x_0) + \lambda_0 = \lambda_0$$

On the other hand, $(x_0, \lambda_0) \in \epi \left ( \co f \right ) \Longrightarrow \lambda_0 \geq \co f(x_0) \ \longrightarrow \longleftarrow$

• One of the differences between \text{} and \operatorname{} is that with \operatorname{epi} f you don't need to manually add spacing between "epi" and "f". – Michael Hardy Oct 27 '14 at 1:05
• @MichaelHardy Thanks for the advice. I didn't know that I was able to define commands in the latex version of the page. – Sorombo Oct 27 '14 at 1:25