How to identify endpoints in convex polytopes with more variables than constraints?

38 Views Asked by At

For example, consider the set

$$S_1 = \left\{ (x_1, x_2, x_3) \in \mathbb{R}_{\geq 0}^3 : x_1 + x_2 + x_3 \leq 2 \right\}$$

Adding slack variables, we obtain

$$x_1 +x_2 +x_3 +x_s = 2$$

If we had $3$ equations, we would solve the system and find an extreme point, but in this case we have infinitely many solutions. Which of those are extreme points?

Consider that all variables involved are nonnegative.


Additional: This question arose because

$$S_2 = \left\{ (x_1,x_2) \in \mathbb{R}_{\geq 0}^2 : x_1+x_2 \leq 2 \right\}$$

has no extreme points. However, for this case we can directly show that it really has no extreme points, and I know that $S_1$ has extreme points.