# 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!

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