Prove that almost every convex function can be represented as a point-wise supremum of a family of its global underestimators. In Convex Optimization by Boyd and Vandenberghe, I read that:  

If for each $y \in A$, $f(x, y)$ is convex in $x$, then the
  function $g$, defined as
  $g(x) = \sup f(x, y)$ over all $y \in A$
  is convex in $x$.  Here the domain of $g$ is
  $\text{dom} g = \{x | (x, y) \in \text{dom} f, \text{for all}\  y \in A, \sup f(x, y) < \infty \ \text{over all}  \ y \in A\}$.

It also says that the converse is true except for a few cases. 
That is, almost every convex function can be represented as a point-wise supremum of a family of its global underestimators. How do I prove that?
 A: The statement is a bit imprecise, since (as far as I'm aware) there's no standard way of defining a measure on the space of convex functions from $\mathbb R^n \rightarrow \mathbb R \cup \{\infty\}.$ However the follow is true, which is what I think the author is getting at:
We say a function $f : \mathbb R^n \rightarrow \mathbb R \cup \{\infty\}$ is lower semicontinous if for all $x \in \mathrm{dom} f,$
$$ f(x) \leq \liminf_{y \rightarrow x} f(y) = \lim_{\varepsilon \rightarrow 0} \inf_{|x-y|<\varepsilon} f(y). $$
Note that in terms of epigraphs, a convex function is lower semicontinous if and only if $\mathrm{epi} f$ is closed. Therefore if $f$ can be written as a pointwise supremum of its global underestimators, then by considering epigraphs we get $f$ is lower semicontinous.
I claim the converse is true.

Theorem If $f$ is a lower semicontinous convex function, then for all for all $x \in \mathbb R^n,$
  $$ f(x) = \sup\{\ g(x) \mid g \text{ affine, }\ g \leq f \}.$$

A proof is given for example in Rockafellar's Convex Analysis, chapters 11/12. I will sketch a proof here.
We need the following non-trivial theorem about hyperplane separation.

Theorem Let $C,D \subset \mathbb R^n$ be closed convex subsets such that $\mathrm{dist}(C,D)>0.$ Then there is $\varepsilon > 0$ and an affine function $g(x) = a^Tx+b$ such that $g(x)>\varepsilon$ for all $x \in C$ and $g(x)<-\varepsilon$ for all $x \in D.$

There's no easy proof of this result that I can type up quickly here, so I'll refer you to the reference above (theorems 11.1-4). From this we can deduce the following, which is the key idea.

Corollary A closed convex subset $C \subset \mathbb R^n$ can be written as the intersection of closed half-spaces containing it.

Now this is easy to show given the above; if we suppose otherwise, there is some
$$ x \in \bigcap\{ H : H \text{ a closed half space, } C \subset H \} \setminus C.$$
Then $\{x\}, C$ are closed and satisfies the conditions of the above theorem, so there is some affine function $g$ such that $g(x) < 0 < g(y)$ for all $y \in C.$ But $\{ y \mid g(y) \geq 0\}$ is a half space containing $C$ but not $x$ which gives a contradiction.
Now the result follows by considering epigraphs. There's a slight technicality since affine functions cannot be vertical lines, but I'll leave those details for you to fill in.

On the note about 'almost everywhere,' note that if $f: \mathbb R^n \rightarrow \mathbb R \cup \{\infty\}$ is convex, then we can define its lower semicontinous hull,
$$ \mathrm{cl}\ f(x) = \liminf_{y \rightarrow x} f(y).$$
One can show that a convex function is almost everywhere continuous (and in fact differentiable), so $f$ and $\mathrm{cl}\ f$ differ on a set of measure zero.
Edit: As Ashkan pointed out in the comments, we can say more about continuity. We have every convex function $\mathbb R^n \rightarrow \mathbb R \cup \{\infty\}$ is continous in the interior of $\mathrm{dom} f,$ so we just need to modify values on the boundary to ensure lower semicontinuity. The fact that the boundary of a convex set has Lebesgue measure zero is a non-trivial result, but you can see a proof here.
