Dada una matriz $A$ $\mathbb R^{m\times n}$, si me gustaría saber si hay o no un $x \in \mathbb R^{n}$ tal que $$ Ax > 0, $$ (es decir, todos los elementos en $Ax$ son positivos). ¿Hay alguna manera fácil para verificar si existe o no tal $x$?
Respuestas
¿Demasiados anuncios?
Misha
Puntos
1723
Esto se puede hacer por iteración en el método simplex. (O su método preferido para resolver problemas de programación lineal.)
Queremos saber si el polytope $P = \{\mathbf x : A\mathbf x \ge \mathbf 0\}$ tiene un punto interior. Para ello, vamos a tratar de encontrar $n+1$ affinely puntos independientes en $P$, entonces el promedio de ellos.
Deje $\mathbf x^0 = \mathbf 0$. Este será el primero de nuestros puntos. Luego repetimos: para encontrar $\mathbf x^i$ cuando hemos encontrado a $\mathbf x^0, \dots, \mathbf x^{i-1}$, escoger un vector $\mathbf c$ tal que $\mathbf c \cdot \mathbf x^0 = \dots = \mathbf c \cdot \mathbf x^{i-1} = 0$, y resolver el LP maximizar $\mathbf c \cdot \mathbf x$$P$. Si este se encuentra un punto de $\mathbf x$$\mathbf c \cdot \mathbf x \ne 0$, vamos que ser $\mathbf x^i$. De lo contrario, sabemos que $P$ no tiene punto interior, porque está recogido en la hyperplane $\{\mathbf x : \mathbf c \cdot \mathbf x = 0\}$.
Una vez que hemos conseguido $n+1$$\mathbf x^0, \dots, \mathbf x^n$, vamos a $\mathbf x = \frac1{n+1}(\mathbf x^0 + \dots + \mathbf x^n)$: este será el punto interior que estamos buscando. (Es un punto interior del casco convexo de $\mathbf x^0, \dots, \mathbf x^n$, por lo que también es un punto interior de a $P$.)
ChocolateAndCheese
Puntos
537
Va a depender de la matriz $A$. Por ejemplo, si $A$ es la matriz cero, entonces la respuesta es no. Si $A$ es de rango completo, entonces la respuesta es sí. En general la imagen de $A$ será un subespacio de $\mathbb{R}^m$, y no todos los subespacios de $\mathbb{R}^m$ cruzan el conjunto $\{(x_1,...,x_m) \in \mathbb{R}^m\; |\; x_i > 0 \;\forall i = 1,...,m\}$.
Más concretamente, la imagen de $A$ es el lapso de sus columnas. Por lo tanto, si $A$ contiene una columna donde cada entrada es positiva (o, equivalentemente, si cada entrada es negativo), entonces usted sabe como un vector $x$ existe. O, si usted puede encontrar algunos de combinación lineal de las columnas de tal manera que cada entrada es positiva, entonces usted saber de nuevo que ese $x$ existe.
edit: Añadido una más método concreto.
John Frederick Chionglo
Puntos
91
Una forma de encontrar x de Ax>0 sería la de resolver un problema artificial:
- min y donde (Ax + y)>0
Si ninguno de los y las variables están en la base de la solución óptima del problema artificial, entonces existe una solución para Ax>0, donde x>0.
Para obtener más información sobre la búsqueda de un inicio solución de (o básico de una solución factible) para el Método Simplex método por favor vea el Capítulo Cuatro: a Partir de la Solución y la Convergencia en las páginas 151 - 198 de "Programación Lineal y los Flujos de la Red" [Cuarta Edición] por Bazaraa, Jarvis y Sherali (2010).
