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.

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.
