How to know whether a vector is a nonnegative linear combination of a set of vectors

Question

Let $v$ be a vector in $\mathbb{R}_n$, let $\{u_i\}_{i\in I}$ be a set of vectors in $\mathbb{R}_n$. Is there any good criteria or algorithm to decide whether $v$ is a linear combination of vectors in $\{u_i\}$ with nonnegative coefficients? Here $I$ is an index set that is either finite or countably infinite.

Answer 1

Partial answer: in the finite case, there is a way, though it's up to you to decide if that way is good enough for your purposes. The content of one of Weyl's theorems states that every finitely generated cone in $\mathbb{R}^n$ is polyhedral: meaning that a point $x \in \mathbb{R}^n$ is a nonnegative linear combination of a finite list of vectors if and only if it satisfies $Ax \leq 0$ for some matrix $A$ (where the less than or equal to sign is meant to indicate less than or equal to in each coordinate).

In other words, if you're given a finite list of vectors, $\{u_i\}$ and you want to check if some vector $x$ is a nonnegative linear combination of the $u_i$, you can compute this matrix, $A$ (dependent only on the $u_i$), then compute $Ax$. All of the coordinates of $Ax$ are nonpositive if and only if $x$ is a nonnegative linear combination of the $u_i$.

The construction of $A$ (and verification of all of the details), however, is fairly long and requires more space than an answer on StackExchange can give. Hence, I'll refer you to section 1 of this paper, which should have all of the details you need.

For a slightly different take, check out section 4.1 of this other paper. It could be a bit more confusing, however, because it focuses on doing this in a system of first-order arithmetic (it's also less well-written).