Which functions are the composition of convex functions?

2018-06-15 08:05:23

The composition of convex functions is not necessarily convex or concave: For example, composing $f_1(x) = x^2-1$ and $f_2(y) = y^2$ gives $f_2(f_1(x)) = (x^2-1)^2$. Or consider $f_1(x) = x^2$ and $f_2(y) = e^{-y}$, which yield $f_2(f_1(x)) = e^{-x^2}$. (Of course, the composition is convex if the outer function is additionally assumed to be monotonically increasing.)

The question, then, is: What are all the functions which can be expressed as the composition of convex functions?

Two slightly different ways to state this a little more formally:

Which functions can be expressed as $f_n \circ \cdots \circ f_1$, where $f_1, ..., f_n : \mathbb{R} \to \mathbb{R}$ are convex functions?

The same question, but with $f_k : I_{k-1} \to I_k$, where $I_0, I_1, ..., I_n$ are (possibly infinite) intervals of the real line (i.e. convex subsets of $\mathbb{R}$).

(We could even generalize further to allow $f_1$ to be defined on, say, $\mathbb{R}^n$.)

I thought about this questi

  • Not a complete answer, but I can at least dispose of $h: x \mapsto x^3$. Suppose this is $f \circ g$ with $f$, $g$ convex. Since $h$ is one-to-one on $\mathbb R$ we'd need $g$ to be one-to-one on $\mathbb R$ and $f$ to be one-to-one on $g(\mathbb R)$. Now the left and right one-sided derivatives of a convex one-to-one function are either strictly positive (if the function is increasing) or strictly negative (if the function is decreasing). This would make it impossible to get $h'(0) = 0$.

    On the other hand, e.g. $x + x^3$ is a composition of convex functions. Take

    $$ f (x) = g(x) = \cases{-x & if $x \ge 0$\cr -x - x^3 & if $x < 0$\cr} $$

    2018-06-15 09:27:57
  • examples : (1) Consider $F(x)=\sin\ x$ which has an infinite local extremums.

    If $F(x)=f_1\circ \cdots \circ f_k\ (x)$, then $F'=f_1'\cdots f_k'$.

    That is, there is $f_i$ s.t. it has infinite local extremum. It is a contradiction.

    (2) If $f_{2k+1}(x)=x^2,\ k\geq 0,\ f_{2}(x)=x-1,\ f_4(x)=x-1/2,\

    f_6(x)=x-1/8,\cdots $, then $f_{2k+1}\circ f_{2k}\circ \cdots f_1 \

    (x)$ has at least $ 2^k$ local extremums.

    2018-06-15 10:46:05