Extreme rays of a small polyhedral cone: How do I get them?

Question

In a nutshell

I have a small 2-dimensional polyhedral cone. $$C=\{(x_1,x_2): 2x_1-x_2 \leq 0, x_1+3x_2 \leq 0\}$$ I am looking for a simple, illustrative, procedure to get its extreme rays. Any suggestions?

---

My reasoning (if you have time)

I am looking for something along these lines, not sure if it works. We can express $C$ as $$C=\{(x_1,x_2)=\alpha_1r_1+\alpha_2r_2, \alpha_1,\alpha_2\geq 0\}$$ where $r_1$ and $r_2$ are the two rays I am looking for. To find $r_1$ and $r_2$ I can probably express $x_1$ and $x_2$ as a function of the rays in the linear inequalities above, and use the extra condition that at an extreme rays we have $2-1$ binding constraints. This should give me:

$$2r_1^1-r_1^2 = 0$$ $$r_2^1+3r_2^2 = 0$$

But I don't seem to get anywhere, since I have two equations and four unknowns. Is it perhaps correct to say that the extreme rays the following? $$r_1^1=1/2r_1^2 $$ $$r_2^1=-3r_2^2 $$ Thus $$r_1= (1/2r_1^2, r_1^2)$$ and $$r_2=(-3r_2^2,r_2^2)$$ This is any point along the hyperplanes that define the cone. Does that sound right?

Answer 1

For your simple (2 variable, 2 side) cone, you are on the right track. An extreme ray will be defined by $n-1$ binding constraints, which in this case means either $2x_1 - x_2= 0$ or $x_1 + 3x_2 = 0$. In the first case, $x_2 = 2x_1$, so the ray will be either $(1, 2)$ or $(-1, -2)$. The first one is not feasible, so the winner is $(-1, -2)$. In the second case, $x_1=-3x_2$, so the ray is either $(-3,1)$ or $(3,-1)$, of which the former is feasible and the latter is not.

This approach gets tedious rather quickly as the dimension grows. If $x\in\Re^n$ and you have $k\ge n$ constraints, you need to solve $\binom{k}{n-1}$ systems of linear equations, then find the correct orientation for each solution and verify that the cone in fact recedes in that direction (which will not automatically be the case, unless your cone is "pointed"). Also, the method relies on knowing a point in the cone. The approach above implicitly relied on knowing that the cone contains $0$. If it does not, the feasibility test involves adding arbitrary multiples of the candidate ray to a known point in the cone.