Determining corners of this convex set

188 Views Asked by At

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$?

Edit: This is apparently true, see the beginning of Section 2 here. Pointers to an explanation would be appreciated.

1

There are 1 best solutions below

3
On BEST ANSWER

Consider that $P = \{ a \in \mathbb{R}^N: \sum_n a_n = 2 \text{ and } 0 \leq a_i \leq 1 \ \forall i\}$. Hence $P$ is described with one equality(equivalent to two inequalities basically) and $2N$ inequalities. A vertex (i.e. an extreme point) of $P \subset \mathbb{R}^N$ is can be described as a feasible point (i.e. lying in $P$) such that $N$ of the aforementioned inequalities are satisfied with equality. Finding these should be fairly easy. Actually, the vertices should be the set of all points in $\{0,1\}^N$ with exactly two $1$'s. Therefore your initial statement is true.