prove that set is polyhedral

Question

If I understand correctly, a subset $S$ of a Hilbert space $H$ is called polyhedral if it can written as an intersection of a finite number of halfspaces, i.e. $$ S = \bigcap_{i=1}^{k}S_{i}, $$ where $$ S_{i}: \{h\in H \mid (h, u_i) \leq \eta_i \}, $$ where $u_i \in H \setminus \{0\}$ and $\eta_i \in \mathbb{R}$.

How to prove that the set $$ C: \{h\in \mathbb{R}^n \mid \sum_{i=1}^{n-1} |h_i - h_{i+1}|_{+} \leq \eta\} $$ where $|x|_{+} = xI\{x>0\}$ (i.e. equals to $x$ if $x > 0$ and $0$ otherwise), is polyhedral?

In the case of $\ell^2$ space (square-summable sequences) the set $$ C: \{h\in \ell^2 \mid \sum_{i=1}^\infty |h_{i} - h_{i+1}|_{+} \leq \eta\} $$ is closed and convex but not polyhedral, correct?

Answer 1

For $u \in \mathbb R^n$ and $\eta \in \mathbb R$ let $H(u,\eta) = \{ h \in \mathbb R^n \mid (h,u) \le \eta \}$.

Let us first consider $\eta < 0$. Then $C = \emptyset$ which is a polyhedron (in fact, the intersection of $H(e_1,-1)$ and $H(-e_1,1)$ for $e_1 = (1,0,0,\ldots)$.

For $\eta \ge 0$ it is rather technical.

For $h = (h_1,\ldots,h_n)$ let $w(h) = (w_1(h),\ldots,w_{n-1}(h))$ where $w_i(h) = 1$ if $h_i \ge h_{i+1}$ and $w_i(h) = 0$ else. Then $$\phi(h) = \sum_{i=1}^{n-1} \lvert h_i - h_{i+1} \rvert_+ = \sum_{i=1}^{n-1} (h_i - h_{i+1})w_i(h) .$$ The set $$W = \{w(h) \mid h \in \mathbb R^{n-1} \} = \{(w_1,\ldots,w_{n-1}) \mid w_i \in \{0,1\} \} $$ has $2^{n-1}$ elements. For each $w = (w_1,\ldots,w_{n-1}) \in W$ define $u(w) = (u_1(w),\ldots,u_n(w))$ by $$u_1(w) = w_1 ,\\ u_i(w) = w_i - w_{i-1} \text{ for } 1 < i < n ,\\ u_n(w) = -w_{n-1} .$$ Let $$S = \bigcap_{w \in W} H(u(w),\eta) .$$ We claim that $S = C$.

1. $\left( h, u(w) \right) = \sum_{i=1}^{n-1} (h_i - h_{i+1})w_i$: In fact, $$\left( h, u(w) \right) = \sum_{i=1}^n h_iu_i(w) = h_1w_1 + \sum_{i=2}^{n-1} h_i(w_i - w_{i-1}) - h_nw_{n-1} \\= \sum_{i=1}^{n-1} h_iw_i - \sum_{i=1}^{n-1}h_{i+1}w_i = \sum_{i=1}^{n-1} (h_i - h_{i+1})w_i .$$

2. $\phi(h) = \left( h, u(w(h)) \right)$: In fact, $$\left( h, u(w(h)) \right) = \sum_{i=1}^{n-1} (h_i - h_{i+1})w_i(h) = \phi(h) .$$

3. $S \subset C$: If $h \in S$, then $h \in H(u(w(h)),\eta)$, thus $\phi(h) \le \eta$, i.e. $h \in C$.

4. $\phi(h) \ge \left( h, u(w) \right)$ for all $w \in W$: This is equivalent to $\sum_{i=1}^{n-1} (h_i - h_{i+1})w_i(h) \ge \sum_{i=1}^{n-1} (h_i - h_{i+1})w_i$, i.e. to $\sum = \sum_{i=1}^{n-1} (h_i - h_{i+1})(w_i(h) - w_i) \ge 0$. But if $w_i(h) = 1$, then $h_i - h_{i+1} \ge 0$ and $w_i(h) - w_i \ge 0$, and if $w_i(h) = 0$, then $h_i - h_{i+1} < 0$ and $w_i(h) - w_i \le 0$, hence all summands in $\sum$ are nonnegative.

5. $C \subset S$: If $h \in C$, then for all $w \in W$ we get $(h,u(w)) \le \phi(h) \le \eta$, i.e. $h \in H(u(w),\eta)$.

For $\ell^2$ this argument is no longer valid because (1) there are uncountably many sequences $w = (w_1,w_2,\ldots)$ with $w_i \in \{0,1\}$ and (2) $u(w)$ is in general no element of $\ell^2$. However, this is no strict proof that $C$ is not polyhedral in that case.