# Is the composition of a set of convex functions convex?

Here we see the proof for $f(x)$ being convex where $$f(x) = h(g(x))$$given $h$ is convex and nondecreasing and $g$ is convex. But what if $$f(x) = h(g_1(x),g_2(x),g_3(x),...,g_k(x))$$ where each $g_i(x)$ is convex and $h$ is still convex and nondecreasing. Can we extend the proof to such a case?

• I would try extending the result to $k=2$. – hardmath Dec 9 '14 at 15:07
• For $n=1$, $h$ is nondecreasing. How should it be for $n\ge 2$? – ajotatxe Dec 9 '14 at 15:09
• @ajotatxe sorry, edited my post, h is always nondecreasing – user192348 Dec 9 '14 at 15:10
• @user2340818 How would you define nondecreasing for a function $h:\mathbb R^2 \to\mathbb R$? – AlexR Dec 9 '14 at 15:12
• Good question @AlexR! – Alex Silva Dec 9 '14 at 15:13

If we assume $h:\mathbb R^2 \to\mathbb R$ to be convex and component-wise nondecreasing, i.e. $$h(x,\cdot) \text{ and } h(\cdot, y) \text{ are nondecreasing for all }x,y\in\mathbb R\\ h(\lambda x + (1-\lambda)x', \lambda y + (1-\lambda) y') \le \lambda h(x,y) + (1-\lambda) h(x',y')$$ We can prove that $$h(g_1(x), g_2(y))$$ is convex for $g_1, g_2:\mathbb R\to\mathbb R$ convex. This allows us to generalise to $n$ dimensions: \begin{align*} h(g_1(\lambda x + (1-\lambda) x'), g_2(\lambda y + (1-\lambda) y')) & \le h(\lambda g_1(x) + (1-\lambda) g_1(x'), \lambda g_2(y) + (1-\lambda) g_2(y')) \\ & \le \lambda h(g_1(x), g_2(y)) + (1-\lambda) h(g_1(x'), g_2(y')) \end{align*}
Let $h:\mathbb R^n \to\mathbb R$ convex and nondecreasing in each component and $g:\mathbb R^n \to\mathbb R^n$ be such that $g_i : \mathbb R^n \to\mathbb R$ is convex then $$f:\mathbb R^n \to\mathbb R, f(x) = h(g(x))$$ is convex.
\begin{align*} f(\lambda x+(1-\lambda y)) & = h(g(\lambda x + (1-\lambda) y)) \\ & \le h(\lambda g(x) + (1-\lambda) g(y)) & (\ast) \\ & \le \lambda h(g(x)) + (1-\lambda) h(g(y)) \\ & = \lambda f(x) + (1-\lambda) f(y) \end{align*} In $(\ast)$ we know that $h$ is nondecreasing component-wise, i.e. $h(x + \delta e_j) \le h(x)$ for $\delta \ge 0$ and $g$ is component-wise convex so $g_j(\lambda x + (1-\lambda y)) \le \lambda g_j(x) + (1-\lambda) g_j(y)$.