[Math] Proving a function is convex if its epigraph is convex.

convex-analysis

Background

In the question here, a proof is given for the following statement:

$$f\text{ is convex} \implies \operatorname{epi}(f)\text{ is convex}$$

Since it is known that

$$f\text{ is convex} \iff \operatorname{epi}(f)\text{ is convex},$$

I would like to prove

$$f\text{ is convex} \impliedby \operatorname{epi}(f)\text{ is convex}$$

specifically.

Current attempt

Suppose $\operatorname{epi}(f)$ is convex, and that we have:

  1. $x,\,y \in \operatorname{dom}(f)$
  2. $\theta \in [0,\,1]$.
  3. $t_1 \in \mathbb{R}$ s.t. $f(x_1) \leq t_1$
  4. $t_2 \in \mathbb{R}$ s.t. $f(x_2) \leq t_2$

Let $z := \theta x + (1 – \theta) y$.

Then, we know

\begin{equation*}
\begin{aligned}
& (x,\,t_1) \in \operatorname{epi}(f) \wedge (y,\,t_2) \in \operatorname{epi}(f) \implies (z, \theta t_1 + (1 – \theta) t_2) \in \operatorname{epi}(f)\\
& \implies f(z) \leq \theta t_1 + (1 – \theta) t_2
\end{aligned}
\end{equation*}

We also know

$$\theta f(x) + (1 – \theta) f(y) \leq \theta t_1 + (1 – \theta) t_2$$

And this is where I get stuck: the above inequality is not useful in showing that $f$ is convex because
$$ (\theta f(x) + (1 – \theta) f(y) \leq \theta t_1 + (1 – \theta) t_2) \wedge (f(z) \leq \theta t_1 + (1 – \theta) t_2) \nRightarrow (f(z) \leq \theta f(x) + (1 – \theta) f(y))$$

Question

And so my question is: is there some other consequence of $\operatorname{epi}(f)$ being convex that we should use for this proof, or am I missing a clue within the information listed above?

Best Answer

You can adjust the proof a little bit to make it work. Here is how. Since $(z,\theta t_{1} + (1-\theta)t_{2}) \in \operatorname{epi}(f)$ by convexity of this set, we get $$f(z) \leq \theta t_{1} + (1-\theta)t_{2}. (1)$$ However, since $t_{1}$ is an arbitrary number that is bigger than $f(x)$ (by our choice) and $t_{2}$ is likewise (bigger than $f(y)$). We can take the limit in (1) as $t_{1} \to f(x)$ and $t_{2} \to f(y)$ to conclude that $f(z) \leq \theta f(x) + (1-\theta)f(y)$.

Taking limits seems to be a useful technique because it preserves inequality :)

Related Question