Conjunto mínimo de las desigualdades

Question

Tengo un set de $m$ desigualdades lineales en $R^n$, de la forma $$ A x \leq b $$ Estos son generados automáticamente a partir de la especificación de mi problema. Muchos de ellos podrían ser removidos, ya que están implícitos en los demás.

Me gustaría encontrar el conjunto mínimo de las desigualdades, $$ A' x \leq b' $$ tal que la solución para el primer problema es también una solución a la segunda, y viceversa.

Una manera de hacerlo es aplicar la transformada de Fourier-Motzkin Eliminación: cojo una desigualdad, $a_1 x \leq b_1$, me negaría como $-a_1 x < -b'$, puedo agregar de nuevo al sistema, y aplicar la OMF: si el resultado es un espacio vacío, entonces la desigualdad original puede ser eliminado de forma segura. Por desgracia, FME es un algoritmo complejo, y en el peor de los casos se debe aplicar el $m$ veces.

Otra posibilidad es el uso de la programación lineal: una vez más, me quito una desigualdad $a_1 x \leq b$, y que yo llamo el conjunto restante de las desigualdades $A'' x \leq b''$. Entonces, me parece óptima para el problema $$ \max \;\; a_1 x \\ A'' x \leq b'' $$ using e.g. simplex, and finally I compare the result with $b$: if $a_1 x' < b$ then the inequality can be safely removed, otherwise it must be kept. Again, this has the same complexity of the simplex applied $m$ times (and $m$ es potencialmente muy grande).

Alguien sabe de un algoritmo mejor?

Answer 1

El uso de Farkas lema, un halfspace $\{x \mid a' x \leq b' \}$ contiene el poliedro $P= \{x |A x \leq b \}$ si y sólo si existe $\lambda \in \mathbb{R}^m$ $\lambda \geq 0$ (entendida componente inteligente) tal que: \begin{align*} a' &= \lambda^T A \\ b' &\geq \lambda^T b \end{align*} El conjunto \begin{align*} N= \{ (a',b') | \exists \lambda \geq 0, a' = \lambda^T A, b' \geq \lambda^T b \} \end{align*} se llama la polar de la poliedro $P$. Las facetas de $P$ están dadas por los rayos extremos de $N$.

Una desigualdad $a_i x \leq b_i$ no va a ser redundantes (he.e no está implícita la otra) si y sólo si es un extremo de rayos de $N$.

Así que todo lo que necesita hacer es calcular la cónica casco de la $m$$(a_1,b_1),...,(a_m,b_m)$, que es más o menos equivalente (algunos hueco para rellenar aquí) para calcular un convex hull. Convexa de los cascos puede ser calculado en $O(m^2)$ usando quickhull http://www.cse.unsw.edu.au/~lambert/java/3d/quickhull.html o cualquier otra convexa casco algoritmo.