Determinar la existencia de una solución para un sistema de inecuaciones lineales

Question

Tengo un conjunto de vectores $\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_m\in\mathbb{R}^n$ y quiero saber si existe un vector distinto de cero $\mathbf{x}$ tal que $\mathbf{x}\cdot\mathbf{v}_i\le0$ cualquier $i$. Esto es lo mismo que decir que la ecuación de $\mathbf{x}^TV\leqq\mathbf{0}$ tiene un valor distinto de cero de la solución, donde $V$ $n\times m$ matriz cuyas columnas son $\mathbf{v}_i$.

Geométricamente, una solución existe si un avión puede ser trazada a través de el origen de todos los vectores están en un lado (en la contenida en el plano).

Se puede demostrar que el uso de Stiemke del Teorema de que existe una solución si y sólo si $V\mathbf{y}=\mathbf{0}\ ,\ \mathbf{y}>\mathbf{0}$ no tiene solución.

He encontrado un par de fuentes sobre la viabilidad de los problemas de programación lineal, pero ninguno que me han permitido encontrar una solución a este problema. Cualquier ayuda se agradece.

Answer 1

Suena muy similar a Farkas del lexema. Con el fin de demostrar que su problema tiene una solución, se debe mostrar que el problema

$$ (P)\quad\underline{x}=\underline{b}, \quad \underline{x}\geq \underline{0} $$ no tiene solución (en el caso de $\underline{b}=\underline{0}$$A=V$). Para este fin, puede utilizar el método simplex para comprobar que no es admisible la solución del problema $(P)$.

Edit: esta es la forma de utilizar la Programación Lineal (LP), para determinar si existe una solución factible. Considerar el LP problema

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

Entonces, si (uno) de la solución óptima(s) verifica $f(\underline{y})=0$, entonces eso significa que $y_i=0$ todos los $i$, es decir, el sistema original es factible. Esta es la primera fase de la llamada de dos fases del método simplex, donde se intenta determinar una solución inicial para un LP problema. Observe que este problema (la primera fase) siempre tiene el trivial solución inicial $\underline{y}=\underline{b}$.

Answer 2

Usted puede configurar y resolver una secuencia de $2n$ LP. Para cada variable $x_{i}$, primera maximizar $x_{i}$ sujeto a las restricciones $x^{T}V \leq 0$, luego se minimice.

Si hubo un vector distinto de cero $\hat{x}$ que está satisfecho con las limitaciones, habrá algún tipo de $k$ tal que cualquiera de las $\hat{x}_{k}<0$ o $\hat{x}_{k}>0$. Cuando se minimiza o maximiza $x_{k}$ obtendríamos un valor distinto de cero el valor óptimo. Alternativamente, si $x=0$ es la única solución que satisfaga las restricciones, a continuación, todos los valores óptimos será 0.

En términos de implementación, se puede utilizar cualquier LP solver que te gusta. Dependiendo del tamaño y la estructura del problema podría ser mejor usar un simple código o podría ser mejor usar un punto interior de solver.

Answer 3

Un enfoque alternativo basado en el teorema de Stiemke implica la solución de un solo LP algo más grande.

Resolver el LP

$\max z$

Sujeto a

$Vy=0$

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

Si la solución óptima tiene $z=0$, entonces el $Vy=0$, $y > 0$ no tiene solución.

Answer 4

Si un conjunto de vectores pertenece a un hiperplano, entonces el vector normal del hiperplano perpendicular a cada uno de los vectores del conjunto. Y viceversa: Si un vector es perpendicular a cada uno de un conjunto de vectores, estos vectores pertenecen al mismo hiperplano.

Los necesarios y la suficiente condición de coplanariedad hiper es el rango de la matriz $r$ menos de $n$.