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!
 A: 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} $$
A: examples : (1) Consider $F(x)=\sin\ x$ which has an infinite local extremums.
If $F(x)=f_1\circ \cdots \circ f_k\ (x)$, then $F'=f_1'\cdots f_k'$.
That is, there is $f_i$ s.t. it has infinite local extremum. It is a contradiction.
(2) If $f_{2k+1}(x)=x^2,\ k\geq 0,\ f_{2}(x)=x-1,\ f_4(x)=x-1/2,\
f_6(x)=x-1/8,\cdots $, then $f_{2k+1}\circ f_{2k}\circ \cdots f_1 \
(x)$ has at least $ 2^k$ local extremums.
