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$.

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

Here's the best I've got so far...

  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$.

| cite | improve this answer | |

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.