Finding system constants to support positive solutions to a system of equations.

Question

I'm well aware of linear programming methods to determine if there exists an $x$ such that $Ax=b$ and $x$ is component-wise positive. What I'm interested in knowing is given matrix $A$, what $b$s satisfy the requirement that there exists $x$ such that $Ax=b$, and $x$ is component-wise positive.

Answer 1

This characterization might not be much use computationally, but it’s relatively clean theoretically.

By the Farkas lemma, there exists $x\geq0$ such that $Ax=b$ if and only if $b^Ty\geq0$ for all $y$ such that $A^Ty\geq0$.

Now, the set $C=\{y\;|\;A^Ty\geq0\}$ is a polyhedral cone. The dual cone $C^*$ of $C$ is defined to as $$ C^*:=\{b\;|\;b^Ty\geq0\text{ for all }y\in{C}\}. $$ Hence, given $A$, the set of $b$ vectors you desire is precisely the dual cone $C^*$ of the dual feasible region $C$.

Edit:

The OP asked in the comments: given a fixed rhs vector $\hat{b}$, find the “closest” vector $b^*$ that renders the system $Ax=b$, $x\geq0$ feasible. This can be formulated as the optimization problem, with decision variables $x$ and $b$: $$ \begin{array}{rl} \min & \|b-\hat{b}\| \\ \text{s.t.} & Ax=b \\ & x\geq0 \end{array} $$ The above problem is a convex optimization problem for any choice of norm $\|\cdot\|$. If you choose the norm as the 1-norm or the $\infty$-norm, the problem can be solved as a linear program. No matter which norm you choose, the problem can be solved very efficiently

Answer 2

The first idea that comes to my mind is to solve with linear programming the system $\min y$ s.t. $Ax - y = 0$. Then variables $y$ would output your vector $b$...