Given that all functions $f_i(x):\mathbb{R}^n\to\mathbb{R}$ are piece-wise linear convex functions, prove that $F(x)=\sum_{i=1}^m f_i(x)$, for $m$ functions, is also a piece-wise linear convex function.
The definition to be used for piece-wise linear is $f_i = \max\{c_j^Tx + d_j\}$, where $c_j\in \mathbb{R}^n$ and $d_j\in\mathbb{R}$, and $\forall j\in J$, an index set associated with function $f_i$. And for each function $f_i$ there is a unique index set $J$ and its own sets $\{d_j\},\{c_j\}$.
I dont know how better to word that, sorry. I hope its well understood.
The definition for a convex function is as such: $\forall x,y$ in domain, $\forall \lambda\in[0,1]$, $f(\lambda x + (1-\lambda)y)\le \lambda f(x) + (1-\lambda) f(y)$.
Ive already proven that the sum of convex functions is convex, without regard for piece-wise linear. What I cant seem to show is that the sum of piece-wise linear functions (using the required definition) is also piece-wise linear.
Ive been working on this for three days. Any pointers or suggestions would be greatly appreciated. Ive also already proven using an inductive argument that it holds for $m>2$, but I cant seem to show the base case $m=2$. So Ive done quite a bit of this problem already. Just need help proving the base case of the piece-wise linear portion.
Note that that $\max_i a_i + \max_j b_j = \max_{i,j} (a_i+b_j)$.
Hence $\max_i (c_i^T x + d_i) + \max_j ({c'_j}^T x + d'_j) = \max_{i,j} ((c_i+c'_j)^T x + (d_i + d'_j) $.
Hence the sum of two convex piecewise linear functions is a convex piecewise linear function. Induction shows the rest.
Aside:
Let $A,B \subset \mathbb{R}$ be non empty.
Then $a+b \le \sup A + \sup B$ for all $a \in A, b \in B$ and so $\sup (A+B) \le \sup A + \sup B$.
For any $a\in A, b \in B$ we have $\sup(A+B) \ge a+b$. Now take the $\sup$ over $a \in A$ to get $\sup(A+B) \ge \sup A +b$ and repeat over $b \in B$ to get the desired result.