Convex functions and families of affine functions

Question

I know that the supremum of a family of affine functions is convex. Just wondering if it is true (and if so how one proves) that the converse -- any $C^1$ convex function is the supremum of some family of affine functions. Thanks.

Answer 1

There is the following very general but somewhat tricky theorem—let me phrase it in terms of concave functions because that's the way I'm used to doing it. What follows is a slightly expanded version of an argument given on p. 13f at the beginning of Chapter 3 of Robert R. Phelps's Lectures on Choquet's Theorem, Springer Lecture Notes in mathematics 1757 (2001):

Recall that a function is upper semi-continuous if $\{f \lt c\}$ is open for all $c$.

Let $K$ be a closed convex set in a locally convex space $X$ (you may take $X = \mathbb{R}^n$ if you like, of course). Then a bounded function $f:K \to \mathbb{R}$ is upper semi-continuous and concave if and only if $$f(x) = \inf{\{a(x)\,:\,a:K \to X \text{ is continuous, affine and } f \leq a\}}$$ for all $x \in K$.

The idea is to use the separating hyperplane theorem. If a function is convex and upper semicontinuous then its subgraph is convex (by concavity) and closed (by upper semicontinuity) and thus the infimum $\hat{f}\,(x)$ over all values $a(x)$ of affine functions dominating $f$ can't lie strictly above the subgraph, for else we could find a separating hyperplane (= the graph of an affine function) lying strictly between the point $(x,\hat{f}(x))$ and the subgraph.

Since a $C^1$ function is continuous, hence upper semi-continuous, the question you ask follows from this immediately. Note also that continuity of affine functions is not an issue if $X = \mathbb{R}^n$.

---

Here are some more details:

For any bounded function $f$ put $\hat{f}(x) = \inf{\{a(x)\,:\,a:K \to X \text{ is continuous, affine and } f \leq a\}}$. The function $\hat{f}$ is called the concave envelope of $f$. As an infimum of continuous functions, $\hat{f}$ is certainly upper semi-continuous, and as an infimum of concave functions $\hat{f}$ is concave, so the conditions on $f$ are certainly necessary.

Now suppose $f$ is bounded, upper semi-continuous and concave. Consider the space $X \times \mathbb{R}$. Since $f$ is upper semi-continuous and concave, the subgraph $G_f = \{(x,t) \in K \times \mathbb{R}\,:\,f(x) \geq t\} \subset X \times \mathbb{R}$ is closed and convex.

Suppose towards a contradiction that there is a $k \in K$ such that $f(k) \lt \hat{f}(k)$. Then the Hahn-Banach separation theorem (or the separating hyperplane theorem if $X = \mathbb{R}^n$, see also this related thread) gives us a linear functional $\phi: X \times \mathbb{R} \to \mathbb{R}$ and $t_0 \in \mathbb{R}$ such that $$\sup\limits_{(x,t) \in G_f}{\phi(x,t)} \lt t_0 \lt \phi(k, \hat{f}(k)).$$ But $\phi(k,f(k)) \lt \phi(k,\hat{f}(k))$ gives us by linearity of $\phi$ that $\phi(0,\hat{f}(k)-f(k)) \gt 0$ and hence $\phi(0,1) \gt 0$. But this means that for each $x \in X$ there is a unique $a(x) \in \mathbb{R}$ such that $\phi(x,a(x)) = t_0$. It is not hard to show that $a$ is continuous and affine. Since for $x \in K$ we have $\phi(x,f(x)) \lt t_0$ and since $\phi(0,1) \gt 0$ we conclude from the definition of $a$ that for $x \in K$ we have $f(x) \lt a(x)$. On the other hand $t_0 \lt \phi(k, \hat{f}(k))$ but this gives us $f(k) \lt a(k) \lt \hat{f}(k)$, a contradiction to the definition of the concave envelope $\hat{f}$.