The maximum of several affine functions is a polyhedral function
1,994
Let's review:
- A function is polyhedral if its epigraph is a finite intersection of closed halfspaces.
- The epigraph of $\max(f_1,\dots,f_m)$ is the intersection of the epigraphs of $f_1,\dots,f_m$.
- The epigraph of $x\mapsto (a_{ij}^Tx+b_{ij})$ is a closed halfspace.
Combining the above yields the answer to your question.
Related videos on Youtube
Author by
sleeve chen
Updated on August 03, 2020Comments
-
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?
-
gerw over 8 yearsDo you know how to get the epigraph of a sum/max of functions in terms of their epigraphs?
-
sleeve chen over 8 yearsnot quite understand, I am weak in this part. I am weak in these complicated function
-
user251257 over 8 years
-