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.

Improve this question
$\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$
    – David Handelman
    Commented 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
    Commented Jul 13, 2016 at 0:17

1 Answer 1

Reset to default
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).

Improve this answer
$\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
    Commented 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
    Commented 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$
    – Dima Pasechnik
    Commented 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
    Commented Jul 13, 2016 at 1:37
  • $\begingroup$ The LP solver will produce $z$ for you. Mathematically this is the same. $\endgroup$
    – Dima Pasechnik
    Commented Jul 13, 2016 at 5:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .