finding an element of a vector subspace contained in the first orthant

Question

Given a matrix $M$, I want to find a nontrivial vector in the kernel of $M$ that also lies in the first orthant, if such a vector exists. That is, I want to simultaneously solve

$$Mx = 0$$ $$x \geq 0$$ $$x \neq 0$$

I'm having trouble phrasing this problem in a way that can be efficiently solved numerically. One approach I've tried is to solve

$$\min_x \|Mx\|^2\quad s.t. \quad x\geq 0, x_i = 1$$

using nonnegative least squares for every $i$, and looking for solutions whose minimum is 0. If the minimum is positive for every $i$, the original problem had no solution. Unfortunately, in addition to being inefficient (I have to do $\dim x$ solves), standard least squares packages are having great difficulty converging for this approach.

Is there a better way to solve this problem?

Answer 1

@Ben's answer is within $\epsilon$ of correct. The problem with it is that (depending on how you interpret the constrains $x_i \geq 1$) there might be no solution with either a specific $x_{i_0} > 0,$ or all $x_i>0,$ and as in the original question, cycling through all the indices is inefficientInstead you use Gordan's theorem (see http://en.wikipedia.org/wiki/Farkas_lemma, "further implications"), which says that the OP is equivalent to the existence of a solution to $M^t y < 0,$ which is equivalent to $M^t y \leq -\mathbf{1}.$

Answer 2

Yes, it's called linear programming. As Anthony notes above, you'll have rephrase your question a bit to get it in this framework. If really just want any element of that orthant, you can minimize $\sum x_i$ with respect to the constraints $x_i\geq 1$ and $Mx=0$.