The maximum of several affine functions is a polyhedral function A function $f: \mathbb{R}^n \mapsto (-\infty,\infty]$ is polyhedral if its **epigraph** is a polyhedral, i.e. $$\text{epi}f=\\{(x,t)\in \mathbb{R}^{n+1} | \ \ C\left( \begin{matrix} x\\\ t \end{matrix} \right)\leq d\\} $$ where $C\in \mathbb{R}^{m\times (n+1)}$ and $d\in \mathbb{R}^m$. Ex: $$f(x)=\sum_{j=1}^p \text{max}_{1\leq i\leq m}(a_{ij}^Tx+b_{ij})$$ > How to understand this is a polyhedral function? I know "$\text{max}_{1\leq i\leq m}(a_{ij}^Tx+b_{ij})$" is pointwise maximum (fixed $j$). But how to understand a polyhedral from the definition?

Let's review:

1. A function is polyhedral if its epigraph is a finite intersection of closed halfspaces.
2. The epigraph of $\max(f_1,\dots,f_m)$ is the intersection of the epigraphs of $f_1,\dots,f_m$.
3. The epigraph of $x\mapsto (a_{ij}^Tx+b_{ij})$ is a closed halfspace.



Combining the above yields the answer to your question.