# 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

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.

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)$$.

• Brilliant thanks so much! except for the $\le c$ everything else makes perfect sense – Dylan Y Sep 26 '19 at 5:26

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.

• what is epi? I actually like this proof except that I don't get how $epi max(f_1,f_2)$ is equal to their intersect – Dylan Y Sep 26 '19 at 6:25
• $\operatorname{epi} f = \{ (x,\alpha) | \alpha \ge f(x) \}$. A function is convex iff its epigraph is convex. It is the points 'above' the graph of $f$. – copper.hat Sep 26 '19 at 6:28
• That makes sense, but how does the epigraph of the max of 2 functions gives a intersection of the 2 functions? I'd imagine it'd just be the epigraph of whichever is larger no? – Dylan Y Sep 26 '19 at 6:48
• O wait I just imagined it in my head and now I see it – Dylan Y Sep 26 '19 at 6:49