# How can I start looking for extreme points in convex polytopes?

Consider $$S \subset \mathbb{R^2}$$ a set such that $$\forall (x_1,x_2) \in S$$ :

$$2x_1+3x_2 \leq 6$$

$$-2x_1+ x_2 \leq 2$$

$$x_1 \geq 0 , x_2 \geq 0$$

How can I find extreme points of $$S$$? What is a good strategy to start tackling this kind of problem?

Because $$x_1,x_2\geqslant0$$ we can write the inequalities as equalities with the use of slack variables: \begin{align} 2x_1+3x_2+s_1&=6\\ -2x_1+x_2+s_2&=2\\ x_1,x_2,s_1,s_2&\geqslant 0. \end{align} Extreme points are equivalent to basic feasible solutions. Because $$S\subset\mathbb R^2$$, a basic solution has two basic variables; hence there are six candidates: $$(x_1,x_2), (x_1,s_1), (x_1,s_2), (x_2,s_1), (x_2,s_2), (s_1,s_2).$$ Solve the system of equations by setting each nonbasic variable equal to zero; if the resulting solution is positive, then it is feasible, and hence a basic feasible solution. I'll leave the computations to you, but the extreme points we find in this process are $$(0,0), (3,0), (0,2)$$ (in terms of $$(x_1,x_2)$$).
• This works fine for $\mathbb R^2$ but what about higher-dimensional problems? :) – Math1000 Sep 4 '19 at 0:02
• Mathematica's RegionPlot3D functionality. – David G. Stork Sep 4 '19 at 4:40