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.



Intersection of a vector subspace with a cone
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).


