Consider a function $f:\mathbb{R}^{n} \to \mathbb{R}$ and epi $f$ = {$(x,t) \in \mathbb{R}^{n+1}: x \in \mathbb{R}^{n}$, $t \geq f(x)$}

Can someone help prove this statement:

A function is convex if and only if its epigraph is a convex set.

Thank you.

  • 1
    $\begingroup$ Can you provide some more context for this? $\endgroup$ – Adam Hughes Sep 10 '14 at 4:09
  • $\begingroup$ @IAmNoOne Actually, it is a theorem $\endgroup$ – Ludwig M Apr 28 at 17:06

Put $\Gamma = \text{epi}(f)$. Suppose first that $f$ is convex, and let $(x_1, t_1), \dots, (x_n, t_n)\in \Gamma$. For any $\lambda_1, \dots, \lambda_n\in [0, 1]$ with $\sum \lambda_i = 1$, the point $(x, t) = \lambda_i \sum (x_i, t_i) = (\sum \lambda_i x_i, \sum \lambda_i t_i)$ has $$t = \sum \lambda_i t_i \geq \sum \lambda_i f(x_i) \geq f\left(\sum \lambda_i x_i\right) = f(x).$$ Hence $(x, t)\in \Gamma$, and $\Gamma$ is convex. The converse is entirely similar.

| cite | improve this answer | |
  • 6
    $\begingroup$ For the converse, consider boundary points of the epigraph, s.t. give you $t_i=f(x_i)$. Then you'll have $f(x)\le \sum \lambda_i t_i = \sum \lambda_i f(x_i) $ $\endgroup$ – Oleg Melnikov May 10 '16 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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