¿Cómo se soluciona de una relación no lineal combinatoric problema?

Question

Soy un estudiante de CS estudiante y estoy luchando con un problema.

$Qx = b$ donde $Q$ es una constante $m \times n$ matriz (con $m>n$), $x$ es una $n \times 1$ vector y $b$ $m\times 1$ vector.

Quiero maximizar el número de ceros en el vector $b$.

sujeto a: $x(i)>0$ $i=1,2, \ldots,n$

¿Cómo se debe abordar un problema como este ?

Answer 1

Tenga en cuenta que no hay ninguna garantía de que usted será capaz de crear cualquier ceros en todos, por ejemplo si todas las entradas de $Q$ son estrictamente positivos. Así, una primera cosa que me gustaría hacer es olvidarnos de esas coordenadas $b_j$ que nunca puede ser igual a cero, es decir, aquellos para los cuales la fila $j$ $Q$ no tiene un aspecto positivo y un negativo de la entrada (esto incluye las filas que están totalmente de cero, que son poco interesante por una razón diferente). A continuación, para cada uno de los restantes de la fila tienes una ecuación lineal en la $x$ que le da la condición para que se coordinan para convertirse en cero, y que es tal que el hyperplane de sus soluciones cumple estrictamente positivo de cono dado por $x_i>0$ todos los $i$. Ahora, la tarea es encontrar la mayor colección de filas de modo que la intersección de su solución hyperplanes todavía cumple con ese cono. Usted puede buscar para los conjuntos de $n$ filas cuyas ecuaciones son linealmente dependientes, ya que es una condición necesaria para tener una colección de al menos $n$ coordenadas que pueden ser igual a cero simultáneamente. Es que no hay conjuntos de $n$ linealmente dependiente de las filas, entonces usted sólo tiene que encontrar la colección más grande de en la mayoría de las $n-1$ filas cuya intersección de hyperplanes cumple con el positivo de cono. Si los conjuntos de $n$ linealmente dependiente de las filas existen, usted puede comprobar sus intersección de hyperplanes, y ver si cumple con el positivo de cono; si lo hace, usted puede obtener los $n$ coordenadas a ser cero, si no es así, que el conjunto de $n$ linealmente dependiente de filas no es productivo, después de todo. Usted probablemente está a la izquierda con un par productivo $n$-tuplas en el mejor, que se puede comparar a ver si incluso más de $n$ simultánea ceros se puede lograr.

Answer 2

Aquí está una manera lenta de hacerlo.

• Encontrar una parametrización para $\operatorname{Nul} Q$, y ver si contiene un positivo vector (que es una cuestión de examinar algunas de las desigualdades que caen fuera de la parametrización). Si es así, esta es una $x$.
• En su defecto, uno a la vez, comprobar si cada estándar de base de vectores $e_i$$\operatorname{Col} Q$. Si es así, Encontrar una parametrización de $Q^{-1}e_i$ (la preimagen de $e_i$ - no implica que el $Q$ es invertible aquí), y de nuevo ver si contiene un vector positivo. Si es así, esta es una $x$.
• En su defecto, de una en una, encontrar una parametrización de $Q^{-1}\operatorname{Span}(e_i,e_j)$, y de nuevo ver si contiene un vector positivo. Si es así, esta es una $x$.
• Continuar con $Q^{-1}\operatorname{Span}(e_i,e_j,e_k)$, etc.

Answer 3

Para cualquier subconjunto $S$ $\{1\ldots m\}$ $b_j = 0$ todos los $j \in S$ corresponde a la solución de $Q_S x = 0, x > 0$ donde $Q_S$ es la submatriz de a $Q$ correspondiente a las filas de $S$. Por homogeneidad, si hay una solución no va a ser uno con todos los $x_j \ge 1$. Software de programación lineal puede ser útil.

Por supuesto, puede haber una gran cantidad de subconjuntos de a tener en cuenta. Afortunadamente, usted no pregunte para una solución eficaz.