Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
For $C^2$ functions $f$ I think you can make the family equal to the set of all affine functions tangent to $f$ somewhere, but $C^1$ sounds harder. Maybe that recent question with the result monotone functions have countable discontinuities is serendipitously relevant too... –  anon Aug 11 '11 at 3:22
add comment

1 Answer

up vote 3 down vote accepted

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}$.

share|improve this answer
1  
Thank you, Theo!! –  Tootsie Aug 11 '11 at 12:56
    
You're welcome. –  t.b. Aug 11 '11 at 13:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.