The maximum of several affine functions is a polyhedral function

Question

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?

Answer 1

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.