50
$\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$

2 Answers 2

45
$\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$
4
  • $\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, 2018 at 13:59
  • $\begingroup$ In the proof, $g$ is the argument of $f$, not the opposite. $\endgroup$
    – Elias
    Aug 28, 2018 at 14:15
  • $\begingroup$ you're right, thanks $\endgroup$
    – evaristegd
    Aug 28, 2018 at 19:25
  • $\begingroup$ Please, see math.stackexchange.com/questions/4113296/… $\endgroup$
    – dtn
    Apr 23, 2021 at 8:24
41
$\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$
4
  • 9
    $\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$ Feb 12, 2012 at 4:53
  • $\begingroup$ @JonasMeyer: Those are nice ones and maybe easier to immediately see than my example. :) $\endgroup$
    – cardinal
    Feb 12, 2012 at 4:55
  • $\begingroup$ @Patrick: Thanks for catching my typo. :) $\endgroup$
    – cardinal
    Feb 12, 2012 at 16:55
  • $\begingroup$ Please, see math.stackexchange.com/questions/4113296/… $\endgroup$
    – dtn
    Apr 23, 2021 at 8:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .