4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want a nonzero vector $x$ with that property? $\endgroup$ – Sungjin Kim Aug 11 '16 at 3:49
  • $\begingroup$ Yes, I forgot to specify that. Thanks. $\endgroup$ – Kajelad Aug 11 '16 at 3:51
  • $\begingroup$ Let us consider an extreme case: $n=1$, $m=2$, $v_1=1$, $v_2=-1$. Then what happens? This would give you some sense of what must be satisfied to guarantee the existence. $\endgroup$ – Sungjin Kim Aug 11 '16 at 4:08
0
+50
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Thanks. I have been doing a bit of research on linear programming, but I still have more to figure out. If you know of any, would it be possible to point out some sources on how to implement the simplex method on a feasibility problem like this? $\endgroup$ – Kajelad Aug 15 '16 at 21:22
  • $\begingroup$ Well, there is already plenty of software that does LP out there. To stay in the open-source world, you could use the linear programming in Octave: gnu.org/software/octave/doc/v4.0.0/Linear-Programming.html. I'm adding a comment on how to use LP. $\endgroup$ – bartgol Aug 16 '16 at 15:37
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would it be possible to elaborate this answer? It is still not clear to me how to implement this approach, and why it will produce the desired result. $\endgroup$ – Kajelad Aug 11 '16 at 17:24
  • $\begingroup$ I've expanded the answer a bit. $\endgroup$ – Brian Borchers Aug 12 '16 at 3:21
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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