6
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Since you are in 2D (2 variables), you can easily draw $C$ and determine the rays graphically. $\endgroup$
    – Kuifje
    Sep 17 at 20:31
  • $\begingroup$ If you are looking for an algebraic method, do you consider solving linear programs "simple", and do you consider LP duality "simple"? $\endgroup$
    – prubin
    Sep 17 at 20:36
  • $\begingroup$ @Kuifje I can easily spot them graphically, but I was rather looking for an algebraic procedure. $\endgroup$
    – k88074
    Sep 18 at 6:38
  • $\begingroup$ @prubin I can consider solving an LP or its dual simple, though I would be even happier with something simpler, such as such as some transformation of the matrix or so. $\endgroup$
    – k88074
    Sep 18 at 6:38
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for your reply. It makes me more comfortable in my reasoning. Just a small note: Would your answer be more complete to say that any solution to each (system of) equation(s) is an extreme ray? In the example provided, also (2,4), (3,6) and so on, would be extreme rays, but not distinct from (1,2). $\endgroup$
    – k88074
    Sep 20 at 7:48
  • $\begingroup$ A ray is a combination of starting point (in this case, the origin) and direction. So the ray with start at (0,0) and direction (-1,-2) is the same as the ray starting at (0,0) with direction (-2,-4), etc. Note that origin (0,0), direction (1,2) is a different ray (and, in this case, not feasible). $\endgroup$
    – prubin
    Sep 20 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.