# Algorithm for Finding the Extreme Rays of a Polyhedral Cone

I would like an algorithm for the following problem:

Given: a finite set of vectors $\{\mathbf v_1, ... , \mathbf v_n\} \subset \mathbb R^N$,

Find: the extreme rays of the cone \begin{equation} C = \left \{ \sum_{i=1}^n x_i \mathbf v_i : x_i \geq 0 \right \}. \end{equation}

Perhaps another way to say it is that I would like an algorithm for computing the minimal generating set of the cone generated by $\{\mathbf v_1, ... , \mathbf v_n\} \subset \mathbb R^N$.

• Did you find a solution to this? I am trying to solve the same problem. – El Gallo Negro Jul 27 '19 at 18:45
• Unfortunately, no. My attention was drawn elsewhere. – Garrett Aug 26 '19 at 0:28

1. Initialize $I := \{1, ... , n \}$.
2. For $j = 1$ to $n$,
a. Attempt to solve the following LP: \begin{equation} \begin{aligned} \min_{\mathbf x} & \ \ \ 0 \\ \text{s.t.} &\ \sum_{i \in I\backslash \{j\}} \mathbf v_i x_i=v_j \\ & \ \ \ \mathbf x \geq \mathbf 0 \end{aligned} \end{equation} b. If the the LP is feasible, set $I:= I\backslash \{j\}$.
3. Return $I$
I claim (without proof) that the resulting set $I$ gives the indices of the extreme rays of the cone $C$.