Intersection of a vector subspace with a cone

Question

Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating subspace $\langle S \rangle$?
I am aware of results like the Farkas Lemma (or variants as Gordan's Theorem, etc...). Or some papers like: Ben-Israel, Adi. "Notes on linear inequalities, I: The intersection of the nonnegative orthant with complementary orthogonal subspaces." Journal of Mathematical Analysis and Applications 9.2 (1964): 303-314.
But I am looking for an algorithm to decide yes or no.

Answer 1

Let $$M = \begin{pmatrix} | & | & \cdots & | \\ v_1 & v_2 & \cdots & v_d \\ | & | & \cdots & | \end{pmatrix}$$ and let $e_1, \ldots, e_N$ be the standard unit vectors. Then consider the linear programs indexed by $i = 1, \ldots, N$:

$$\begin{aligned} &\text{maximize }\langle e_i,Mx\rangle \\ &\text{subject to }\langle e_j, Mx\rangle \ge 0,\quad j=1,\ldots,N \end{aligned}$$

Clearly if any of these programs is unsatisfiable, then all of them are, and moreover $\langle S\rangle$ is disjoint from the positive orthant. So assume all programs are satisfiable.

If the $i$th program is bounded, let $x^{(i)}$ be its optimal solution and $y^{(i)}$ be its optimal value. If it is unbounded, add the constraint $\langle e_i, Mx\rangle \le 1$, and let $x^{(i)}$ be the optimal solution to this modified program, and the optimal value becomes $y^{(i)} = 1$.

If any of the $y^{(i)}$ are zero, then clearly $\langle S\rangle$ is disjoint from the positive orthant.

In the remaining case, where the programs are satisfiable and all optimal values are positive, let $x^{(i)}$ be the optimal solution for the $i$th program and let $y^{(i)}$ be the optimal value for the $i$th program. Since $\langle e_i, Mx^{(i)}\rangle = y^{(i)} > 0$ and $\langle e_j, Mx^{(i)}\rangle \ge 0$, all by construction, we can take any linear combination $\sum a_i Mx^{(i)}$, with all $a_i > 0$, to obtain a point in the intersection of $\langle S\rangle$ with the positive orthant.

In summary, if all the programs are satisfiable and have positive optimal values, then yes; otherwise, no. Note that adding constraints to make all programs bounded is for convenience of proving correctness, but unimportant for implementing the algorithm (one needs only check that all optimal values are either positive or infinite).