Equivalent definitions of piecewise affine convex function over a convex set of $\mathbb{R}^n$.

Question

Let $C\subset\mathbb{R}^n$ be a convex set and $f:C\to\mathbb{R}$ a convex function. I want to show that the following are equivalent:

1. $\mathrm{epi}(f)=\{(x,y)\in C\times\mathbb{R}\mid y\geq f(x)\}$ is a polyhedral convex set (i.e. a finite intersection of $C\times\mathbb{R}$ and half spaces of $\mathbb{R}^n\times\mathbb{R}$: $\langle (x,y),(b_i,c_i)\rangle\leq\beta_i$ for $i=1,\ldots,n$.) ;
2. $f(x)=\max_{a\in A}(c_a+\langle a,x\rangle)$ for a finite subset $A\subset\mathbb{R}^n$.

Answer 1

Suppose that $\mathrm{epi}(f)$ is the intersection of half-spaces determined by a finite family of hyperplanes, that is $$\mathrm{epi}(f)= \bigcap\limits_{(v,w,c) \in V \times W \times C} \{(x,y) \in C \times \mathbb{R} \mid -v \cdot x + w \cdot y \geq c \},$$

where $V$, $W$ and $C$ are finite.

• If $w <0$ find a contradiction as $y \to + \infty$.
• If $w=0$ show that $v=0$ and find a contradiction.
• Deduce that we may suppose $w=1$, hence

$$\mathrm{epi}(f)= \bigcap\limits_{(v,c) \in V \times C} \{ (x,y) \in C \times \mathbb{R} \mid y \geq c+ v \cdot x \}.$$

Therefore, $f(x) \geq \max\limits_{(v,c) \in V \times C} v \cdot x +c$.

Now if $y<f(x)$ ie. $(x,y) \notin \mathrm{epi}(f)$, there exists $(v,c) \in V \times C$ such that $y< v \cdot x+c$. As $y \to f(x)$, we deduce $$f(x) \leq v \cdot x+c \leq \max\limits_{(v,c) \in V \times C} v \cdot x+c,$$

hence $f(x)= \max\limits_{(v,c) \in V \times C} v \cdot x+c$.

Conversely, suppose that $f(x)= \max\limits_{a \in A} (a \cdot x+ c_a)$. For all $a \in A$, define the half-space $$H_a= \{(x,y) \in C \times \mathbb{R} \mid y \geq a \cdot x+c_a \}.$$

Then

$$\bigcap\limits_{a \in A} H_a= \{(x,y) \in C \times \mathbb{R} \mid y \geq \max\limits_{a \in A} (a \cdot x+c_a)=f(x) \}= \mathrm{epi}(f).$$

Remark: Notice that we did not use the fact that $f$ is convex. For more information about your equivalence and convexity, you may see here.