Epigraph for convex sets

Question

I am trying to understand these situations:

When is the epigraph of a function a halfspace?

When is the epigraph of a function a convex cone?

When is the epigraph of a function a polyhedron?

For 1D I can see the if the function is horizontal line I get a halfspace, a slanted line I get a cone, a piecewise linear function gives me a polyhedron. How can I generalize to a general n dimension?

Answer 1

TL;DR: the epigraph is a halfspace / convex cone / polyhedral if and only the function is affine / sublinear / the pointwise maximum of a finite number affine functions.

I'll answer your queries for functions $f \colon E \to \overline{\mathbb R}$, where $E$ is a real normed space with algebraic dual space $E'$. The dual pairing on $E$ is $\langle \cdot, \cdot \rangle$ and on $E \times \mathbb R$ it is $\big((p_1, r_1), (p_2, r_2)\big) \mapsto \langle p_1, p_2 \rangle + r_1 r_2$.

1. A halfspace with normal $p \in E' \setminus \{ 0 \}$ and offset $\alpha \in \mathbb R$ is \begin{equation*} H_{p, \alpha}^{-} := \{ x \in E: \langle p, x \rangle \le \alpha \} \qquad \text{or} \qquad H_{p, \alpha}^{+} := \{ x \in E: \langle p, x \rangle \ge \alpha \}. \end{equation*} Suppose there exist $p = (p_0, p_1) \in \big((E \times \mathbb R)' \big) \setminus \{ (0, 0) \} \cong \big( E' \times \mathbb R \big) \setminus \{ (0, 0) \}$ and $\alpha \in \mathbb R$ such that $\text{epi(f)} = H_{p, \alpha}^{\pm}$. If $p_1 = 0$, then $H_{p, \alpha}^{\pm} = H_{p_0, \alpha}^{\pm} \times \mathbb R$. Due to $\pm$ being $+$ or $-$, we can assume without loss of generality that $p_1 > 0$. Hence \begin{align*} \{ (x, r) \in E \times \mathbb R: f(x) \le r \} & = \{ (x, r) \in E \times \mathbb R: \langle p_0, x \rangle + p_1 r \le \alpha \} \\ & = \{ (x, r) \in E \times \mathbb R: \langle p_0, x \rangle - \alpha \le p_1 r\} \\& = \left\{ (x, r) \in E \times \mathbb R: \left\langle \frac{1}{p_1} p_0, x \right\rangle - \frac{1}{p_1} \alpha \le r \right\} \end{align*} Hence $f$ must be the affine function $$\ell_{\frac{1}{p_1} p_0, \frac{1}{p_1} \alpha} \colon E \to \mathbb R, \qquad x \mapsto \left\langle \frac{1}{p_1} p_0, x \right\rangle - \frac{1}{p_1} \alpha.$$ Note that $\ell_{\frac{1}{p_1} p_0, \frac{1}{p_1} \alpha}$ is continuous if and only if $p_0 \in E^*$ (continuous dual space of $E$) is continuous.
2. We show that $f$ is sublinear if and only if $\text{epi}(f)$ is a convex cone (which means $K + K \subset K$ and $K$ convex).

"$\implies$": Let $f$ be sublinear and $(x_1, r_1), (x_2, r_2) \in \text{epi}(f)$ and $r \ge 0$. Then $f(x_k) \le r_k$ for $k \in \{ 1, 2 \}$. Since $f$ is sublinear, $f(r x_1) = r f(x_1) \le r r_1$ and $f(x_1 + x_2) \le f(x_1) + f(x_2) \le r_1 + r_2$, so $\text{epi}(f)$ is a convex cone.

"$\impliedby$": Let $\text{epi}(f)$ be a convex cone and $x, y \in E$ and $r \in \mathbb R$. We have $\big(x, f(x)\big), \big(y, f(y)\big) \in \text{epi}(f)$ and $\big(x + y, f(x) + f(y)\big) \in \text{epi}(f)$, that is, $f(x + y) \le f(x) + f(y)$. In particular, $f(0) \le 2 f(0)$, so $f(0) \ge 0$. Furthermore, $\big(r x, r f(x)\big) \in \text{epi}(f)$, so $f(r x) \le r f(x)$. In particular, $f(0) \le 0$, so $f(0) = 0$. By the same reasoning we also get $f(r x + y) \le r f(x) + f(y)$. Lastly, for $r > 0$ we have $f(x) = f\left( \frac{1}{r} (r x) + 0\right) \le \frac{1}{r} f(r x) + f(0) = \frac{1}{r} f(r x)$ and thus $r f(x) \le f(r x)$, proving $f(r x) = r f(x)$, as desired.

3. I assume that by polyhdral set you mean $$ \big\{ x \in E: \langle p_k, x \rangle \le \alpha_k \ \forall k \in \{ 1, \ldots, m \} \big\} = \bigcap_{k = 1}^{m} H_{p_k, \alpha_k}^-, $$ where $p_k \in E'$ and $\alpha_k \in \mathbb R$ for $k \in \{1, \ldots, m \}$ and $m \in \mathbb N$. Since $$\bigcap_{k = 1}^{m} \text{epi}(f_k) = \text{epi}\left(\max_{k = 1}^{m} f_k\right),$$ it follows from 1. that the $\text{epi}(f)$ is polyhedral if and only if $f$ is the pointwise maximum of affine functions.