38
$\begingroup$

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

$\endgroup$
33
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ 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$. $\endgroup$ – Jonas Meyer Feb 12 '12 at 4:53
  • $\begingroup$ @JonasMeyer: Those are nice ones and maybe easier to immediately see than my example. :) $\endgroup$ – cardinal Feb 12 '12 at 4:55
  • $\begingroup$ @Patrick: Thanks for catching my typo. :) $\endgroup$ – cardinal Feb 12 '12 at 16:55
37
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If $f$ can be the argument of $g$, then the only value $m$ can take is 1. When you say that the domain of $g$ is $\mathbb{R}^m$, it's OK if you just write $\mathbb{R}$ ? $\endgroup$ – evaristegd Aug 27 '18 at 13:59
  • $\begingroup$ In the proof, $g$ is the argument of $f$, not the opposite. $\endgroup$ – Elias Aug 28 '18 at 14:15
  • $\begingroup$ you're right, thanks $\endgroup$ – evaristegd Aug 28 '18 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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