Why is the conjugate of a function always convex? The conjugate of a function $f$ is given (for some $y \in \operatorname{dom}(f)$) as:
$$f^*(y) = \sup_{x \in \operatorname{dom}(f)}\left(y^Tx - f(x)\right)$$
It is known that $f^*$ is convex even if $f$ is not. I would like to know how to prove this.

For any given $x \in \operatorname{dom} f$, the function:
$$y \mapsto y^\top x - f(x)$$
is an affine function, which is convex and lower semicontinuous (and, indeed, continuous). The epigraph of these functions is therefore closed and convex.
Then, $f^*$ is the pointwise supremum of the above functions, and its epigraph is the intersection of the above affine functions' epigraphs. Each are closed and convex, proving the epigraph of $f^*$ is closed and convex, thus $f^*$ is convex and lower semicontinuous.
