How get the extreme directions of an unbounded feasible region

Question

The following constraints form a feasible region.

$-x_1+x_2 \le 2$

$-x_1+2x_2 \le 6$

$x_1,x_2 \ge 0$

The feasible region have three extreme points: $e_1=\left[\begin{array}{cc} 0\\ 0 \end{array}\right]$ $e_2=\left[\begin{array}{cc} 0\\ 2 \end{array}\right]$ $e_3=\left[\begin{array}{cc} 2\\ 4 \end{array}\right]$

What is the procedure that I need to follow to extract the extreme direction from this data?

Extrene Direction: An extreme direction of a convex set is a direction of the set that cannot be represented as a positive combination of two distinct directions of the set.

Answer 1

Draw the LP using the graphical method (Just plot the conditions as line on the $x_1$ and $x_2$ axis) let $x_1$ be the horizontal axis and $x_2$ be the vertical axis. Find the line that remains in the feasible region as $x_1$ tends to infinity. and take the ratio of increase in $x_2$ and $x_1$. So if you have a line $-x_1 +2x_2 \geq 8$ that stays in the feasible region as $x_1$ tends to infinity, then the extreme direction is $(2,1)$ as when $x_1$ increases by $2$ then $x_2$ increases by $1$. Another example: you have a line $x_2 \geq 2$,that stays in the feasible region as $x_1$ tends to infinity, then the extreme direction is $(1,0)$.

Answer 2

In standard format, we get the system: \begin{equation*} \begin{alignedat}{2} -x_1 & {}+{} & x_2&{}+{}&x_3& &&= 2\\ -x_1&{}+{}&2x_2& &&{}+{}&x_4\ &=6 \end{alignedat} \end{equation*} with all variables positive. The matrix of the system is: $$A=\begin{pmatrix}-1&1&1&0\\ -1&2&0&1\end{pmatrix}.$$ Any extreme direction $d$ can be obtained as: $$d=\begin{pmatrix}-B^{-1}a_j\\e_j\end{pmatrix},$$ where $B$ is a $2\times 2$ invertible submatrix of $A$, $a_j$ is the $j$th column of $A$, not in $B$, such that $B^{-1}a_j\leq0$ and $e_j$ is the canonical vector with a one in the position of the column $a_j$.

For example, let $B=\begin{pmatrix}1&0\\0&1\end{pmatrix}$, invertible submatrix of $A$. We have that $B^{-1}a_1=\begin{pmatrix}-1\\-1\end{pmatrix}\leq0$. The canonical vector $e_1$ has a one in the position of $a_1$, i. e., $e_1=\begin{pmatrix}1\\0\end{pmatrix}$. Therefore, we get the direction $$d=\begin{pmatrix}1\\0\\1\\1\\\end{pmatrix},\ \text{writing }-B^{-1}a_1\text{ in the position of }B\text{ and }e_1\text{ in the left entries.}$$ In our original system, by erasing the variables $x_3$ and $x_4$, we get the extreme direction $\begin{pmatrix}1\\0\end{pmatrix}$.