3
$\begingroup$

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?

$\endgroup$
1
  • 4
    $\begingroup$ How about solving $Mx=0$, $x\ge 0$, $\sum x_i=1$. At least its an LP then. $\endgroup$ – Anthony Quas Jan 15 '11 at 19:03
3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

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.