1
$\begingroup$

For a set of under-determined linear equations, I was wondering if there is any closed form for all non-negative solutions? Is there a way to analytically characterize the feasibility set of such equations?

More formally, for given $M\in \mathbb{R}^{n\times m}_{+}$ and $y\in \mathbb{R}^{m\times 1}$, find all solution $x\geq 0$ of $Mx=y$. Note that $M$ and $y$ are non-negative as well.

$\endgroup$
2
  • $\begingroup$ Farkas' Lemma (see the Wikipedia article) gives a little information; no solution exists iff there exists a row $z$ such that $zA \geq 0$ but $zy < 0$. It's not clear (to me) how this can be used to characterize the $x$. $\endgroup$ Jul 12, 2016 at 22:58
  • $\begingroup$ Thanks for the quick reply. If I understood it right, using Farkas' Lemma one trades the original problem for its dual as now there is the problem of searching for $z$, and it doesn't seem searching/solving for $z$ is any easier than the original problem. I am missing something here? $\endgroup$
    – Yashar Z
    Jul 13, 2016 at 0:17

1 Answer 1

1
$\begingroup$

All such vectors $x\geq 0$ form a polyhedron in $\mathbb{R}^n$, which may be empty. The latter can be certified using Farkas Lemma, as David points out in the comment. On the other hand, a nonempty polyhedron is a Minkowski sum of a subspace, a polyhedral cone, and a polytope. (see Wikipedia for terms I used).

Your extra conditions on $M$ and $y$ imply that you only get a polytope $P$. Then you can say that any $x$ is a convex combination of the vertices of $P$ (for practical purposes, this is often a useless kind of description, but you cannot hope for anything better in general).

$\endgroup$
5
  • $\begingroup$ Thanks for the reply Dima. As I wrote in a comment under David's reply, is checking for Farks Lemma any easier than solving the original problem? At the moment, I use linear programing to find a solution $x$ for the original problem. Checking for Farkdas Lemma involves linear inequalities as well. It can be formulated as a linear program too. So I am not sure what is the real benefit of checking for Farkas Lemma from the practical point of view. $\endgroup$
    – Yashar Z
    Jul 13, 2016 at 1:13
  • $\begingroup$ About the second part of your comment, is it possible to characterize $P$ in terms of $M$ and $y$. Can we say anything about the vertices of $P$? $\endgroup$
    – Yashar Z
    Jul 13, 2016 at 1:16
  • $\begingroup$ With $z$ found, you have a proof that $P=\emptyset$. (Good LP solvers typically would have an option to produce such a certificate if it exists). Regarding the vertices of $P$, all you can hope for, in general, are some bounds on their coordinates in terms of entries of $M$ and $y$. $\endgroup$ Jul 13, 2016 at 1:26
  • $\begingroup$ Thanks again, but if LP is to be used, why not directly formulate the original problem as LP? One can still get a certificate regarding existence of the solution. Right? $\endgroup$
    – Yashar Z
    Jul 13, 2016 at 1:37
  • $\begingroup$ The LP solver will produce $z$ for you. Mathematically this is the same. $\endgroup$ Jul 13, 2016 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.