grandes-ecoles 2022 Q12
View
Let $k \in \mathbb{N}^*, (p_1, \ldots, p_k) \in (\mathbb{R}^d)^k$ and $(b_1, \ldots, b_k) \in \mathbb{R}^k$ such that $$A := \left\{x \in \mathbb{R}^d : p_i \cdot x \leqslant b_i, i = 1, \ldots, k\right\}$$ is non-empty. Show that $A$ is convex and closed. Let $x \in A$, let $I(x) := \left\{i \in \{1, \ldots, k\} : p_i \cdot x = b_i\right\}$, show that $$x \in \operatorname{Ext}(A) \Longleftrightarrow \operatorname{rank}\left(\{p_i, i \in I(x)\}\right) = d$$ deduce that $\operatorname{Ext}(A)$ is a finite set (possibly empty) whose cardinality is at most $2^k$.