Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

Question

Compute the extreme points of a polyhedron $P$ and write $(1/2,1/2,1/2)$ as a linear combination of these.

I want to compute all the extreme points of the set $P$ (polyhedron) in $\mathbb R^3$ satisfying the inequalities:

$-x -y-z \le -1$

$-x + y + z \le 1$

$x -y +z \le 1$

$x + y -z \le 1$

$x + y+ z \le 2$

I've computed $\text{ext}(P) = \{e_1,e_2,e_3,(1/2,1/2,1),(1/2,1,1/2),(1,1/2,1/2)\}$ and $\text{rec}(P)={0}$, so $P = \text{ext}(P)$.

However, $(1/2,1/2,1/2) \in P$, cannot be written as a convex combination of the vectors in $\text{ext}(P)$.

What am I doing wrong ?

Answer 1

The point $(\frac 12,\frac 12,\frac 12)$ can be written as a convex combination of three of the points you gave. In particular,

$$\begin{align} \left(\frac 12,\frac 12,\frac 12\right) & = \frac 12 \left( \frac 12,\frac 12,1 \right) \\ & + \frac 14 (1,0,0)\\ & + \frac 14 (0,1,0)\\ \end{align} $$