Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is a set of convex functions closed under composition? I don't necessarily need a proof, but a reference would be greatly appreciated.

share|improve this question

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
4  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.