Let $f_1$,$f_2$ be two convex functions on $R^n$. Show $\max[f_1(x),f_2(x)]$ is a convex function as well

Question

I'm getting confused on how to prove this. I was thinking 2 points $x$ and $y$ that satisfy the definition of convex function $f((1-\lambda)x+\lambda y \le (1-\lambda)f(x)+\lambda f(y)$ where $\lambda \subset [0,1]$ and $x$ and $y$ are real numbers, but can't really plug them in cause the values you get back are outputs from a function the function output depends on which function outputs a larger value.

Answer 1

The definition of convexity of $f$ is that $$f((1-t)x+ty)\le (1-t)f(x)+tf(y)\tag{1}$$ for all vectors $x$, $y$ in $\Bbb R^n$ and all $t\in[0,1]$.

In our case, take $f=\max(f_1,f_2)$ where $f_1$, $f_2$ are convex. Two prove an inequality $$\max(a,b)\le c$$ it suffices to prove both $$a\le c\quad \text{and}\quad b\le c.$$ So to prove $(1)$ we only need to prove both $$f_1((1-t)x+ty)\le (1-t)f(x)+tf(y)\tag{2}$$ and $$f_2((1-t)x+ty)\le (1-t)f(x)+tf(y).\tag{3}$$

The proofs of $(2)$ and $(3)$ are clearly going to be similar, so I'll only consider $(2)$. By the convexity of $f_1$ I know that $$f_1((1-t)x+ty)\le (1-t)f_1(x)+tf_1(y)\tag{4}.$$ But as $1-t\ge0$ and $t\ge0$, and $f_1(x)\le f(x)$ and $f_1(y)\le f(y)$, we have $(1-t)f_1(x)\le (1-t)f(x)$ and $tf_1(y)\le tf(y)$. Thus $$(1-t)f_1(x)+tf_1(y)\le (1-t)f(x)+tf(y).\tag{5}$$ Putting $(4)$ and $(5)$ together gives $(2)$.

Answer 2

Note that $\operatorname{epi} \max(f_1,f_2) = \operatorname{epi} f_1 \cap \operatorname{epi} f_2$. The intersection of convex sets is convex.