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

-

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.

-
Another example: $x^{2/3}=(-x^{1/3})^2$ is not convex on $(0,\infty)$ although $-x^{1/3}$ is convex on $(0,\infty)$ and $x^2$ is convex on $\mathbb R$. Or $(-\log(x))^2$. –  Jonas Meyer Feb 12 '12 at 4:53
@JonasMeyer: Those are nice ones and maybe easier to immediately see than my example. :) –  cardinal Feb 12 '12 at 4:55
@Patrick: Thanks for catching my typo. :) –  cardinal Feb 12 '12 at 16:55

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.

-