A convex function $f$ can be represented as the supremum of all the affine functions that are dominated by $f$. Is there a simple characterization of those convex functions $g$ that can be represented as the supremum of all the linear functions that are dominated by $g$?
[Math] Which convex functions are characterized as the supremum of linear functions
convex-analysisfunctional-analysis
Related Solutions
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}$.
Best Answer
Assuming we're talking about functions from $\Bbb R$ to $\Bbb R$, the function $g$ has this property if and only if there exist $a,b$ with $a\ge b$ and $g=g_{a,b}$, where $$g_{a,b}(t)=\begin{cases}at&(t\ge0), \\bt&(t<0).\end{cases}$$
It's clear that every such $g_{a,b}$ is the sup of a family of linear functions. Conversely, say $g$ is convex and $g$ is the sup of a family $F$ of linear functions. Let $L_a(t)=at$. There exists $S\subset\Bbb R$ such that $$F=\{L_a:a\in S\}.$$Hence $$g(t)=\sup_{f\in F}f(t)=g_{\alpha,\beta}(t),$$where $\alpha=\sup S$ and $\beta=\inf S$.
(Note we never used the assumption that $g$ is convex. This makes sense: It's clear that the sup of any family of linear functions is convex...)
Edit: In fact $g:\Bbb R^n\to\Bbb R$ is the supremum of a family of linear functions if and only if $g$ is convex and $$g(tx)=tg(x)\quad(t\ge 0).$$
Again it's clear that the sup of a family of linear functions has this form. Suppose conversely that $g$ is convex and has that homogeneity property. We know that $g$ is the sup of a family of affine functions. So the following shows that $g$ is the sup of a family of linear functions:
Proof: Suppose first that $\alpha\le 0$ and $L\le g$. Since $A\le L$ it is clear that $A\le g$.
Conversely, suppose $A\le g$. Then $\alpha=A(0)\le g(0)=0$, and for $t>0$ we have $$\alpha+tL(x)\le g(tx)=tg(x).$$So $\alpha/t+L\le g$; let $t\to\infty$ and it follows that $L\le g$
Edit 2: This is in reply to a comment, wouldn't fit nicely in the comment box. It's been said that a convex function on $\Bbb R^n$ need not be continuous. Seems to me that yes it is continuous:
Note I'm taking convex function to be real-valued, as I thought was standard. If we allow convex functions to take values in $(-\infty,\infty]$ then yes, there are certainly discontinuous convex functions on $\Bbb R^n$.
Heh, proof that it is standard to take "real-valued" as part of the definition: A standard result says that any convex function on $\Bbb R$ is continuous..
Proof: Given $K$ compact there exist $x_1,\dots,x_{n+1}$ such that $K$ is contained in the convex hull of the $x_j$: hence $f\le\max(f(x_j))$ on $K$.
Now suppose that $f$ is convex on $\Bbb R^n$. Choose $c$ so that $f(x)\le c$ for $|x|\le 10$.
Suppose $t=|y|< 1$. There exists $z$ with $|z|=1$ such that $y=tz=(1-t)0+tz$.Hence $$f(y)\le tf(z)+(1-t)f(0)\le ct+(1-t)f(0).$$Now $t\to0$ as $y\to0$, so $$f(0)\ge\limsup_{y\to0}f(y).$$For the other direction, say $\alpha=\limsup_{y\to0}f(y)$. Say $y_j\to0$, $f(y_j)\to\alpha$. Let $z_j=-y_j/|y_j|$. Then $0$ is a convex combination of $y_j$ and $z_j$: $$0=t_jz_j+(1-t_j)y_j.$$In particular, $t_j=|(1-t_j)y_j|\to0$. So $$f(0)\le ct_j+(1-t_j)f(y_j)\to\alpha.$$So $$\limsup_{y\to0}f(y)\le f(0)\le\liminf_{y\to0}f(y),$$hence $\lim_{y\to0}f(y)=f(0).$