How to find nonnegative solutions of a linear system?

Question

I have the following system of $M$ linear equations in $N$ unknowns.

$$ \begin{bmatrix} 3 & 0 & 1 & 0 & -1 & -3 & 2\\ 1 & 2 & 0 & 4 & 0 & 0 & -1\\ 1 & 1 & 0 & 0 & -1 & -1 & -2\\ 0 & 0 & 1 & 0 & -3 & -1 & 1 \\ \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ x_{3}\\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \\ \end{bmatrix} = \begin{bmatrix} 1\\ 0\\ 0\\ -1\\ \end{bmatrix}$$

Is there any algorithm for finding answers of this equations that ${x_{i} \ge 0}$?

Comment: I just want that $x_i \ge 0$.

It can change to

$$ \begin{bmatrix} 1 & 0 & 0 & 0 & 2/3 & -2/3 & 1/3 & 2/3\\ 0 & 1 & 0 & 0 & -5/3 & -1/3 & -7/3 & -2/3 \\ 0 & 0 & 1 & 0 & -3 & -1 & 1 & -1 \\ 0 & 0 & 0 & 1 & 2/3 & 1/3 & 5/6 & 1/6 \\ \end{bmatrix} $$

Answer 1

You can solve the linear programming problem given below by the simplex method:

$\max z=0$ subject to the constraints given by the equations.

Of course, you would have to add artificial variables for all the constraints which would make it a far too large problem to be solved by hand. Probably some software would be of assistance.

Wolfe's method in quadratic programming relies on the same idea for finding non negative solutions of the Kuhn Tucker conditions.

Answer 2

You can choose three unknown values as variables, for example $x_5$, $x_6$ and $x_7$, then the remaining unknown values become a linear function of these variables. In this case,

$$ \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} =\frac{1}{6}\left( \begin{bmatrix} 4 \\ -4 \\ -6 \\ 1 \end{bmatrix} + \begin{bmatrix} -4 & 4 & -2 \\ 10 & 2 & 14 \\ 18 & 6 & -6 \\ -4 & -2 & -5 \end{bmatrix} \begin{bmatrix} x_5 \\ x_6 \\ x_7 \end{bmatrix} \right) $$

If you for example want to find which values for $x_5$, $x_6$ and $x_7$ can be used such that $x_3$ and $x_4$ are equal to or greater than zero you will run into a problem. You namely want to $x_5$, $x_6$ and $x_7$ also to be equal to or greater than zero, thus the optimal variable which you would like to increase from zero would need to have the largest positive gain for $x_3$ and the smallest negative gain for $x_4$. This is true for $x_5$, however even this variable will not be able to keep both $x_3$ and $x_4$ positive, namely for $x_5=\frac{1}{4}$ then $x_4=0$ but $x_3=-\frac{1}{4}$and for $x_5=\frac{1}{3}$ then $x_3=0$ but $x_4=-\frac{1}{18}$. Thus is can be concluded that there exists no solution such that $x_i\geq0$.