The maximum of several affine functions is a polyhedral function

1,994

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.

Share:
1,994

Related videos on Youtube

sleeve chen
Author by

sleeve chen

Updated on August 03, 2020

Comments

  • sleeve chen
    sleeve chen over 3 years

    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?