Determining existence of a solution for a system of linear inequalities

Question

I have a set of vectors $\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_m\in\mathbb{R}^n$ and I want to know if there exists a nonzero vector $\mathbf{x}$ such that $\mathbf{x}\cdot\mathbf{v}_i\le0$ for any $i$. This is the same as saying the equation $\mathbf{x}^TV\leqq\mathbf{0}$ has a nonzero solution, where $V$ is an $n\times m$ matrix whose columns are $\mathbf{v}_i$.

Geometrically, a solution exists if a plane can be drawn through the origin such that all of the vectors are on one side (on contained within the plane).

One can show using Stiemke's Theorem that a solution exists if and only if $V\mathbf{y}=\mathbf{0}\ ,\ \mathbf{y}>\mathbf{0}$ does not have a solution.

I have found a few sources on feasibility problems in linear programming, but none that have allowed me to find a solution to this problem. Any help would be appreciated.

Answer 1

Sounds really similar to Farkas's lemma. In order to prove that your problem has a solution, you must show that the problem

$$ (P)\quad A\underline{x}=\underline{b}, \quad \underline{x}\geq \underline{0} $$ has no solution (in your case $\underline{b}=\underline{0}$ and $A=V$). To this end, you can use the simplex method to verify that there is no admissible solution to problem $(P)$.

Edit: this is how you use Linear Programming (LP) to determine if there is a feasible solution. Consider the LP problem

$$ \min f(\underline{y})=\sum y_i\\ \\ s.t. A\underline{x} + \underline{y} = \underline{b}\\ x_i\geq 0,y_i\geq 0,b_i\geq 0 $$

Then, if (one of) the optimal solution(s) verifies $f(\underline{y})=0$, then that means that $y_i=0$ for all $i$, that is, your original system is feasible. This is the first phase of the so called two-phases simplex method, where you try to determine an initial solution for a LP problem. Notice that this problem (the first phase) always has the trivial initial solution $\underline{y}=\underline{b}$.

Answer 2

You can setup and solve a sequence of $2n$ LP's. For each variable $x_{i}$, first maximize $x_{i}$ subject to the constraints $x^{T}V \leq 0$, then minimize it.

If there was a nonzero vector $\hat{x}$ that satisfied the constraints, then there would be some $k$ such that either $\hat{x}_{k}<0$ or $\hat{x}_{k}>0$. When we minimized or maximized $x_{k}$ we would get a nonzero optimal value. Alternatively, if $x=0$ is the only solution that satisfies the constraints then all optimal values will be 0.

In terms of implementation, you can use any LP solver that you like. Depending on the size and structure of the problem it might be better to use a simplex code or it might be better to use an interior point solver.

Answer 3

An alternative approach based on Stiemke's theorem would involve the solution of a single somewhat larger LP.

Solve the LP

$\max z$

Subject to

$Vy=0$

$y_{i} \geq z, i=1, 2, \ldots, n$

If the optimal solution has $z=0$, then $Vy=0$, $y > 0$ has no solution.

Answer 4

If a set of vectors belongs to a hyperplane, then the normal vector of the hyperplane perpendicular to each of the vectors of the set. And vice versa: if a vector is perpendicular to each of a set of vectors, these vectors belong to the same hyperplane.

The nesessary and sufficient condition of hyper-coplanarity is the rank of the matrix $r$ is less than $n$.