# Prove the maximum of convex functions is also convex using this def. [duplicate]

Could someone assist me in proving that the maximum of a convex function is also convex using the below definition? I cannot figure out how this proof would work and would appreciate some help!

$$f(\lambda x +(1-\lambda)y) \le \lambda f(x)+(1-\lambda)f(y)$$

$$\lambda \in[1,0]$$

Thank you!

Step 1: Take only two convex functions $f(x)$ and $g(x)$.

Step 2: Let $\lambda\in[0,1]$. Show that: \begin{align} \max\{ f(\lambda x +(1-\lambda) y),g(\lambda x + (1-\lambda )y)\} \leq \max\{ \lambda f(x) +(1-\lambda) f(y),\lambda g(x) + (1-\lambda)g(y)\} \end{align} Step 3: Show that $\max\{A+B,C+D\}\leq \max\{A,C\} + \max\{B,D\}$, for $A,B,C,D\in\mathbb{R}$

Step 4: Show that for $\alpha\geq 0$ we have: $\max\{\alpha A,\alpha B\}=\alpha\max\{A,B\}$, for $A,B\in\mathbb{R}$.

Step 5: Finish the proof. Repeat for more functions (induction).

• For the induction, the base case is k=2, the induction hypothesis is that we have the result for k and the induction step is k+1. I'm not sure what to do when this appears in the induction step: Suppose $x^*=\lambda x+(1-\lambda)y.$ Then $f(x)\le max\{\lambda f_1(x)+(1-\lambda)f(y),\dots ,f_{k+1}(x^*)\}$ because I think I can apply convexity on $f_{k+1}.$ What should I do? – user441848 Dec 31 '17 at 23:52
• @Anneliset. I don't understand what you mean exactly with the last words. However what will help you much is to note the following $$\max\{A, B, C\} =\max\{\max\{A, B\}, C\}$$This makes the induction easy. – Shashi Jan 1 '18 at 0:25
• There is a typo, I meant can't instead of can. – user441848 Jan 1 '18 at 2:02
• @Anneliset. Okay, did the hint I gave you help? You can use it like this $$\max\{f_1,...,f_{k+1}\} =\max\{\max\{f_1,...,f_{k}\},f_{k+1}\}$$ you know that the maximum of two convex function is convex and you are done. – Shashi Jan 1 '18 at 9:59
• Yes I think I got it, I'd have to associate the functions in pairs and then apply the base case which is that the maximum of 2 convex functions is convex. – user441848 Jan 1 '18 at 19:03

Let $f_{1}$ and $f_{2}$ be convex, and let $f=\max(f_{1},f_{2})$. $f(\lambda x+(1-\lambda)y)=\max({f_{1}(\lambda x+(1-\lambda)y),f_{2}(\lambda x+(1-\lambda)y)}) \leq \max(\lambda f_{1}(x)+(1-\lambda)f_{1}(y)); \lambda f_{2}(x)+(1-\lambda)f_{2}(y))=\lambda \max(f_{1}(x),f_{2}(x))+(1-\lambda) \max(f_{1}(y),f_{2}(y))=\lambda f(x)+(1-\lambda)f(y)$$I assume you have two convex functions$g$and$h$on some interval$I$, and you want to prove that$f$, defined as$f(x)=\max(g(x),h(x)), x\in I$is convex too. For$x,y \in I$, and$\lambda \in [0, 1] $, one of the functions$g$,$h$is going to be the 'bigger' one at$(1-\lambda)x+\lambda y$, without loss of generality let's assume that it is$g$. Thus,$f((1-\lambda)x+\lambda y)=g((1-\lambda)x+\lambda y) \ge (1-\lambda)g(x)+\lambda g(y) \ge (1-\lambda)f(x)+\lambda f(y)\$.