Which functions are the composition of convex functions?

The composition of convex functions is not necessarily convex or concave: For example, composing $f_1(x) = x^2-1$ and $f_2(y) = y^2$ gives $f_2(f_1(x)) = (x^2-1)^2$. Or consider $f_1(x) = x^2$ and $f_2(y) = e^{-y}$, which yield $f_2(f_1(x)) = e^{-x^2}$. (Of course, the composition is convex if the outer function is additionally assumed to be monotonically increasing.)

The question, then, is: What are all the functions which can be expressed as the composition of convex functions?

Two slightly different ways to state this a little more formally:

• Which functions can be expressed as $f_n \circ \cdots \circ f_1$, where $f_1, ..., f_n : \mathbb{R} \to \mathbb{R}$ are convex functions?
• The same question, but with $f_k : I_{k-1} \to I_k$, where $I_0, I_1, ..., I_n$ are (possibly infinite) intervals of the real line (i.e. convex subsets of $\mathbb{R}$).

(We could even generalize further to allow $f_1$ to be defined on, say, $\mathbb{R}^n$.)

I thought about this question, and it didn't even seem obvious to me whether, say, $x \mapsto x^3$ is a composition of convex functions. Your help is appreciated!

Solution 1:

Not a complete answer, but I can at least dispose of $h: x \mapsto x^3$. Suppose this is $f \circ g$ with $f$, $g$ convex. Since $h$ is one-to-one on $\mathbb R$ we'd need $g$ to be one-to-one on $\mathbb R$ and $f$ to be one-to-one on $g(\mathbb R)$. Now the left and right one-sided derivatives of a convex one-to-one function are either strictly positive (if the function is increasing) or strictly negative (if the function is decreasing). This would make it impossible to get $h'(0) = 0$.

On the other hand, e.g. $x + x^3$ is a composition of convex functions. Take $$ f (x) = g(x) = \cases{-x & if $x \ge 0$\cr -x - x^3 & if $x < 0$\cr} $$