Is the composition of $n$ convex functions itself a convex function? Is a set of convex functions closed under composition? I don't necessarily need a proof, but a reference would be greatly appreciated.
 A: There is no need for the first function in the composition to be nondecreasing. And here is a proof for the nondifferentiable case as well. The only assumptions are that the composition is well defined at the points involved in the proof for every $\alpha \in [0, 1]$ and that $f_n, f_{n - 1}, \dots, f_1$ are convex nondecreasing functions of one variable and that $f_0 : \mathbb R^n \to \mathbb R$ is a convex function.
First let $g : \mathbb R^m \to \mathbb R$ a convex function and $f : \mathbb R \to \mathbb R$ a convex nondecreasing function, then, by convexity of $g$:
$$
g( \alpha x + ( 1 - \alpha ) y ) \leq \alpha g( x ) + ( 1 - \alpha )g( y ).
$$
So, using the fact that f is nondecreasing:
$$
f( g( \alpha x + ( 1 - \alpha ) y ) ) \leq f( \alpha g( x )+ ( 1 - \alpha )g( y ) ).
$$
Therefore, again by convexity:
$$
f( g( \alpha x + ( 1 - \alpha ) y ) ) \leq \alpha f( g( x ) ) + ( 1 - \alpha )f( g( y ) ).
$$
This reasoning can be used inductively in order to prove the result that
$$
f_n \circ f_{n - 1}\circ\cdots\circ f_0
$$
is convex under the stated hypothesis. And the composition will be nondecreasing if $f_0$ is nondecreasing.
A: In general, the answer is negative.
Counterexample: Let $f(x) = e^{-x}$ on $[0,\infty)$. Then $f$ is convex, but $f \circ f$ is concave. (Check derivatives.)
However, if we add an additional assumption, then we can get the desired result.
Lemma: Let $f_1,\ldots,f_n$ be convex nondecreasing functions. Then $f_1 \circ \cdots \circ f_n$ is convex (and nondecreasing).
Proof: Here is a proof for the case where each of the $f_i$ are twice-differentiable. We can show it by induction. Let $g_n = f_1 \circ \dots \circ f_n$. Suppose that $g_n$ is convex and nondecreasing. Then, $g_{n+1} = g_n \circ f_{n+1}$. But, two applications of the chain rule yield
$$
{g'\!\!}_{n+1} = ({g'\!\!}_n \circ f_{n+1}){f'\!\!}_{n+1} \geq 0\>,
$$
and,
$$
{g''\!\!}_{n+1} = ({g''\!\!}_n \circ f_{n+1})({f'\!\!}_{n+1})^2 + ({g'\!\!}_n \circ f_{n+1}){f''\!\!}_{n} \geq 0 \>,
$$
and so the stated result follows.
