Overview

The epigraph of a function is a geometric object that collects every point lying on or above the graph of the function. Formally, for a function f from a vector space X to the extended real line, the epigraph is the set of pairs (x,r) with f(x) ≤ r. The epigraph provides a way to study properties of f by examining a subset of the product space X × R rather than working pointwise on values of f.

Definition and basic properties

Given f: X → (−∞,+∞], the epigraph is defined as epi(f) = {(x,r) ∈ X × R : f(x) ≤ r}. Two elementary but important equivalences are frequently used in analysis and optimization:

  • f is convex if and only if epi(f) is a convex subset of X × R.
  • f is lower semicontinuous (lsc) if and only if epi(f) is a closed set when X is a topological space.

Examples

Simple instances illustrate the shape of an epigraph. For a linear function in R^n, f(x)=a·x+b, epi(f) is a closed half-space { (x,r) : r ≥ a·x+b } in R^{n+1}. For the convex quadratic f(x)=x^2 on R, the epi is the region above the parabola, i.e. {(x,r): r ≥ x^2}. The indicator function of a set C, I_C, has epi(I_C) equal to C × [0,∞), reflecting that the function takes value 0 on C and +∞ outside.

Uses in optimization and analysis

Epigraphical representations are widely used to reformulate optimization problems. A minimization of f(x) can be written as minimize r subject to f(x) ≤ r, which places the objective as a linear coordinate and moves nonlinearity into a constraint. Convex optimization routinely employs this epigraph form to expose convexity and to derive dual problems. The concept of epi-convergence (epigraphical convergence) is a mode of functional convergence useful in variational analysis and in the study of stability of minimizers.

The hypograph is the complementary notion that collects points on or below the graph. The etymology of "epigraph" comes from Greek roots meaning "upon the graph". For further technical development and proofs of the statements above, see standard references in convex analysis and variational methods; for a quick pointer, consult an entry on the epigraph or general resources about the inequality-based definition of epigraphs.