2
$\begingroup$

Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently?

Suppose we have an under-determined system:

$$Ax = b$$

where $A$ is a $m \times n$ matrix and $m < n$. How can we get a solution such that $x>0$?

I have tried to solve the system using linear programming: for the $Ax=b$ constraint, it is hard to find any solution. So I make it:

$$Ax \leq 1.01 b$$ $$Ax \geq 0.99 b$$

such that we have an approximated solution. But still had no success. To make a proper objective function is very tricky.

I wonder if there is some effective method to solve this problem?

btw: some papers might be relevant are listed:

Conditions for a unique non-negative solution to an underdetermined system. http://ieeexplore.ieee.org/document/5394815/

A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices https://arxiv.org/abs/1003.4778

The Farkas-Minkowski Theorem: www.math.udel.edu/~angell/Opt/farkas.pdf

Update 1:

By using linear least-squares to minimize $\|Ax-b\|_2$ and $x \geq 0$, it seems that we can get non-negative solution $x$, nevertheless, the zeros in $x$ and the error of $A x$ to $b$ are still not acceptable.

Update 2:

Problem solved! Now I can get a positive solution perfectly meets the equations (1 - 10), even N is big, e.g. N = 1000 unknowns.

Improve this question
$\endgroup$
8
  • $\begingroup$ I see you already solved the problem, but in case this is helpful: what I usually do is add an extra variable $z$ and inequalities of the form $m_i \ge z$ and set the objective to maximize $z$. $\endgroup$
    – Yoav Kallus
    Commented Aug 1, 2017 at 14:21
  • $\begingroup$ You did it with linear programming? In this case, you are setting low bound to z? I did it as well, but no success :(. Also, can you please give some explanation on how you put z in A, and constructed the objective function? thanks $\endgroup$
    – KOF
    Commented Aug 1, 2017 at 14:27
  • 1
    $\begingroup$ Yes, I use a LP solver. You can set a lower bound for z, but not necessary. If the optimal solution of the modified LP has $z\le0$, that means the original linear system has no positive solution. How you modify the problem to introduce the extra variable and extra inequalities depends on your LP solver. Good luck. $\endgroup$
    – Yoav Kallus
    Commented Aug 1, 2017 at 14:33
  • 1
    $\begingroup$ If you've solved the problem, KOF, let me encourage you to post the solution. $\endgroup$
    – Gerry Myerson
    Commented Aug 1, 2017 at 23:07
  • $\begingroup$ A relevant question: mathoverflow.net/q/262985/7076 $\endgroup$
    – Max Alekseyev
    Commented Aug 2, 2017 at 4:22

0

Reset to default

You must log in to answer this question.