Why is the conjugate of a function always convex?
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.
As I wrote this question I recalled the following fact, and have attempted to prove this property of conjugate functions using it.
If $h(y,\,x)$ is convex in $y$ for each $x \in \mathcal{A}$, then $g(y) = \sup_{x \in \mathcal{A}}h(y,\,x)$ (the pointwise supremum) is convex.
Let us try to apply this fact to our problem, finding the "equivalent terms":
- $f^*(y)$ is $g(y)$
- $\mathcal{A}$ is $\operatorname{dom}(f)$
- $y^Tx - f(x)$ is $h(y,\,x)$
Do these "equivalent" terms meet the conditions they need to for us to be able to use this fact? I.e.,
$\forall x \in \operatorname{dom}(f),\,\text{is}\,h(y,\,x) := y^Tx - f(x)$ convex in $y$?
Let us try to prove this using Jensen's inequality.
For some $x,\,a,\,b \in \operatorname{dom}(f),\,\theta \in [0,\,1]$ consider: \begin{equation*} \begin{aligned} & h(\theta a + (1 - \theta) b,\,x)\\ & = (\theta a + (1 - \theta) b)^Tx - f(x)\\ & = \theta a^T x + (1 - \theta) b^T x - f(x)\\ & = \theta a^T x - \theta f(x) + (1 - \theta) b^T x - (1 - \theta) f(x)\\ & = \theta (a^T x - f(x)) + (1 - \theta) (b^T x - f(x))\\ & = \theta h(a,\,x) + (1 - \theta) h(b,\,x)\\ \end{aligned} \end{equation*}
Since equality always holds, $h(y,\,x)$ is convex in $y$.
Now that I have done this, I realize the following: $h(y,\,x)$ was just an affine function in $y$, meaning that the pointwise supremum, i.e. the conjugate of $f$, will also be convex.