Inequality involving max is confusing me. I am trying to understand one line in a derivation here. Simply put, the statement is that:
$$
\max\{\theta f_1(x) + (1-\theta) f_1(y) , \theta f_2(x) + (1-\theta) f_2(y)\} \le \theta \max\{f_1(x), f_2(x) \} + (1-\theta) \max\{f_1(y), f_2(y) \}
$$
I do not understand how they 'opened up' the max here to get the right hand side of the equation. (Not sure this matters, but for this issue, both $f_1$ and $f_2$ are convex functions, and $\theta + (1-\theta) = 1$, with $\theta \in [0, 1]$).
 A: The property in use is $$\max\{a+b, c+d\}\le \max\{a,c\}+\max\{b,d\}$$

Proof: $a+b\le \max\{a,c\}+b\le \max\{a,c\}+\max\{b,d\}$.  Similarly $c+d\le \max\{a,c\}+\max\{b,d\}$. 
A: The function $\psi(z)= \max(z_1,z_2)$ is convex, and a convex function satisfies
$\psi(\theta w+ (1-\theta) z) \le \theta \psi(w)+ (1-\theta) \psi(z)$ for all $\theta \in [0,1]$.
Letting $w=f_1(x), z=f_2(x) $ gives the desired result.
Note: To see why the $\max$ is convex, suppose the functions $f_1,f_2$ are convex. Then we have (with $\lambda \in [0,1]$)
$f_1(\lambda w + (1-\lambda)z) \le \lambda f_1(w) + (1-\lambda) f_1(z)$, and 
$f_2(\lambda w + (1-\lambda)z) \le \lambda f_2(w) + (1-\lambda) f_2(z)$.
Note that both $\lambda $ and $1-\lambda$ are non-negative, so if we replace $f_1(w)$ (or $f_2(w)$) by $\max(f_1(w),f_2(w))$ and $f_1(z)$ (or $f_2(z)$) by $\max(f_1(z),f_2(z))$, the inequalities still hold.
Hence we have
$f_1(\lambda w + (1-\lambda)z) \le \lambda \max(f_1(w),f_2(w)) + (1-\lambda) \max(f_1(z),f_2(z))$, and similarly,
$f_2(\lambda w + (1-\lambda)z) \le \lambda \max(f_1(w),f_2(w)) + (1-\lambda) \max(f_1(z),f_2(z))$, from which it follows that
$\max(f_1(\lambda w + (1-\lambda)z), f_2(\lambda w + (1-\lambda)z)) \le \max(f_1(w),f_2(w)) + (1-\lambda) \max(f_1(z),f_2(z))$.
Now let $f_1(w) = w_1$, $f_2(w) = w_2$ to see why $\psi$ is convex.
Another note: A more geometric way of seeing this is to note that a function $f$ is convex iff $\operatorname{epi} f$ (the epigraph) is convex. Then if we have
$\psi(x) = \max(f_1(x),f_2(x))$, then $\operatorname{epi} \psi = \operatorname{epi} f_1 \cap \operatorname{epi} f_2$. If the $f_k$ are convex, then since the intersection of convex sets is convex, it follows that $\psi$ is also convex.
