Shae's Ramblings

Suppose a parametric function \(f_\theta \colon A \to \mathbb{R}\) is convex in both \(\theta\) and \(x\in A\). Then one can prove the function \(g(x) = \min_\theta f_\theta(x)\) is convex in \(x\) (where \(\theta\) is constrained to a compact set $\Theta$). Indeed, take any two \(x_1, x_2 \in A\) and \(t\in (0,1)\), we have

\begin{align} f_\theta(tx_1 + (1-t)x_2) &\leq tf_\theta(x_1) + (1-t)f_\theta(x_2) \\ & \leq t\min_\theta f_\theta(x_1) + (1-t)f_\theta(x_2) \\ & \leq t\min_\theta f_\theta(x_1) + (1-t)\min_\theta f_\theta(x_2) \\ \end{align}

simply because the inequality holds for any \(\theta, x_1, x_2\) and thus holds for the parameters which minimize the function. Finally as \(\min_\theta f_\theta(x) \leq f_\theta(x)\) for every \(x\), we get the final result. More formally, this argument can be extended to the infimum \(\inf_\theta f_\theta(x)\) using the fact the infimum is the greatest lower bound (and must thus be greater than the LHS).

A similar derivation gives that \(h(x) = \max_\theta f_\theta(x)\) (and the \(\inf\) equivalent) is convex as well.