Eliminación de Fourier-Motzkin

La eliminación de Fourier-Motzkin, también conocida como método FME, es un algoritmo matemático para eliminar variables de un sistema de inecuaciones lineales. Puede generar soluciones reales.

El algoritmo recibe su nombre de Joseph Fourier, quien propuso el método en 1826, y de Theodore Motzkin, quien lo redescubrió en 1936.

La eliminación de un conjunto de variables, digamos V, de un sistema de relaciones (aquí desigualdades lineales) se refiere a la creación de otro sistema del mismo tipo, pero sin las variables en V, de modo que ambos sistemas tengan las mismas soluciones sobre las variables restantes.

Si se eliminan todas las variables de un sistema de inecuaciones lineales, se obtiene un sistema de inecuaciones constantes. Es trivial decidir si el sistema resultante es verdadero o falso. Es verdadero si y sólo si el sistema original tiene soluciones. En consecuencia, la eliminación de todas las variables puede utilizarse para detectar si un sistema de inecuaciones tiene soluciones o no.

Considerar un sistema ${\displaystyle S.$ de ${\displaystyle n}$ desigualdades ${\displaystyle r}$ variables ${\displaystyle x_{1}}$ a ${\displaystyle x_{r}}$Con ${\displaystyle x_{r}}$ la variable a eliminar. Las desigualdades lineales en el sistema se pueden agrupar en tres clases dependiendo del signo (positivo, negativo o nulo) del coeficiente para ${\displaystyle x_{r}}$.

• esas desigualdades que son de la forma ${\displaystyle x_{r}\geq b_{i}-\sum ¿Qué?$; denotarlas ${\displaystyle x_{r}\geq A_{i}(x_{1},\dotsx_{r-1}}$Para ${\displaystyle i}$ desde 1 hasta 1 ${\displaystyle No.$ Donde ${\displaystyle No.$ es el número de esas desigualdades;
• esas desigualdades que son de la forma ${\displaystyle x_{r}\leq b_{i}-\sum ¿Qué?$; denotarlas ${\displaystyle x_{r}\leq B_{i}(x_{1},\dotsx_{r-1}}$Para ${\displaystyle i}$ desde 1 hasta 1 ${\displaystyle No.$ Donde ${\displaystyle No.$ es el número de esas desigualdades;
• esas desigualdades ${\displaystyle x_{r}}$ no juega ningún papel, agrupado en una sola conjunción ${\displaystyle \phi }$.

El sistema original es por tanto equivalente a

${\displaystyle \max(A_{1}(x_{1},\dotsx_{r-1}),\dots A_{n_{A}(x_{1},\dotsx_{r-1})\leq x_{r}\leq \min(B_{1}(x_{1},\dotsx_{r-1}),\dots B_{n_{B}(x_{1},\dotsx_{r-1})\wedge \phi }$.

La eliminación consiste en producir un sistema equivalente a ${\displaystyle \exists x_{r}~S}$. Obviamente, esta fórmula equivale a

${\displaystyle \max(A_{1}(x_{1},\dotsx_{r-1}),\dots A_{n_{A}(x_{1},\dotsx_{r-1})\leq \min(B_{1}(x_{1},\dotsx_{r-1}),\dots B_{n_{B}(x_{1},\dotsx_{r-1})\wedge \phi }$.

La desigualdad

${\displaystyle \max(A_{1}(x_{1},\dotsx_{r-1}),\dots A_{n_{A}(x_{1},\dotsx_{r-1})\leq \min(B_{1}(x_{1},\dotsx_{r-1}),\dots B_{n_{B}(x_{1},\dotsx_{r-1})}$

equivale a ${\displaystyle No.$ desigualdades ${\displaystyle A_{i}(x_{1},\dotsx_{r-1})\leq B_{j}(x_{1},\dotsx_{r-1}}$Para ${\displaystyle 1\leq i\leq No.$ y ${\displaystyle 1\leq j\leq No.$.

Por lo tanto, hemos transformado el sistema original en otro sistema donde ${\displaystyle x_{r}}$ es eliminado. Tenga en cuenta que el sistema de salida tiene ${\displaystyle (n-n_{A}-n_{B})+n_{A}n_{B}$ desigualdades. En particular, si ${\displaystyle No.$, entonces el número de desigualdades de producción es ${\displaystyle No.$.

Consideremos el siguiente sistema de desigualdades:

${\displaystyle {\begin{cases}2x-5y+4z\leqslant 10\3x-6y+3z\leqslant 9\\\-x+5y-2z\leqslant -7\-3x+2y+6z\leqslant 12\\\\end{cases}}}}}$

Como todas las inecuaciones tienen la misma forma (todas menores que o todas mayores que), podemos examinar los signos de los coeficientes de cada variable. Eliminar x daría como resultado 2*2 = 4 inecuaciones en las variables restantes, y lo mismo sucedería si elimináramos y. Eliminar z daría como resultado solo 3*1 = 3 inecuaciones, por lo que la utilizaremos en su lugar.

${\displaystyle {\begin{cases}z\leqslant {\frac {10-2x+5y}{4}\\z\leqslant {\frac {9-3x+6y}{3}\{\frac} {7-x+5y} {2}\leqslant z\z\leqslant {\frac {12+3x-2y}{6}\\\end{cases}}}$

lo que da las 3 desigualdades:

${\displaystyle {\begin{cases}{\frac {7-x+5y}{2}\leqslant {\frac {10-2x+5y}{4}\\{\frac\f}}\\\\\\fnMic {7-x+5y}{2}\leqslant {\frac {9-3x+6y}{3}\{\frac} {7-x+5y} {2}\leqslant {\frac {12+3x-2y}{6}\\end{cases}}}$

Simplificando:

${\displaystyle {\begin{cases}5y\leqslant -4\x+y\leqslant -1\-6x+17y\leqslant -9\\end{cases}$

Este sistema utiliza sólo dos variables en lugar de tres. Al examinar los signos de los coeficientes de cada variable, se obtiene que y es totalmente positiva, por lo que podemos decir inmediatamente que el sistema no está acotado en y: dado que todos los coeficientes de y son positivos y todas las desigualdades son menores o iguales, fijar y en menos infinito (o cualquier número negativo suficientemente grande) satisfaría el sistema reducido, por lo que también existen x y z correspondientes para los sistemas más grandes, y hay infinitas soluciones de este tipo. Por ejemplo, fijar y = -1000000, x = 0, z = -2222222 satisface tanto el sistema original como los reducidos.

Corregir un paso de eliminación ${\displaystyle n}$ las desigualdades pueden resultar en la mayoría ${\displaystyle No.$ desigualdades en la producción, por lo tanto ingenuamente ${\displaystyle d}$ pasos sucesivos pueden resultar en la mayoría ${\displaystyle 4(n/4)}{2^{d}}$Una doble complejidad exponencial. Esto se debe al algoritmo que produce muchas limitaciones redundantes implicadas por otras limitaciones.

Teorema de límite superior de McMullen que establece que el número de restricciones no redundantes crece como un exponente único. En este artículo se proporciona una implementación exponencial única de la eliminación de Fourier-Motzkin y estimaciones de complejidad.

Es bien sabido que la programación lineal proporciona soluciones a sistemas de desigualdades en tiempo polinomial, lo que la favorece frente a la eliminación de Fourier-Motzkin.

Dos teoremas de "aceleración" creados por Imbert permiten la eliminación de desigualdades redundantes basadas únicamente en propiedades sintácticas del árbol de derivación de fórmulas, lo que reduce la necesidad de resolver programas lineales o calcular rangos de matrices.

Define el historia ${\displaystyle H_{i}$ de una desigualdad ${\displaystyle i}$ como conjunto de índices de desigualdades del sistema inicial ${\displaystyle S.$ usado para producir ${\displaystyle i}$. Así, ${\displaystyle H_{i}=\{i}$ para las desigualdades ${\displaystyle i\in S}$ del sistema inicial. Al agregar una nueva desigualdad ${\displaystyle k:A_{i}(x_{1},\dotsx_{r-1})\leq B_{j}(x_{1},\dotsx_{r-1})}$ (por eliminar ${\displaystyle x_{r}}$), la nueva historia ${\displaystyle H_{k}$ se construye como ${\displaystyle H_{k}=H_{i}\cup H_{j}$.

Supongamos que las variables ${\displaystyle O_{k}=\{x_{r},\ldotsx_{r-k+1}\}$ han sido Oficial eliminado. Cada desigualdad ${\displaystyle i}$ particiones el conjunto ${\displaystyle O...$ en ${\displaystyle E_{i}\cup I_{i}\cup R_{i}$:

• ${\displaystyle E_{i}$, el conjunto de efectivamente eliminada variables, i.e. a propósito. Una variable ${\displaystyle x_{j}$ está en el set tan pronto como al menos una desigualdad en la historia ${\displaystyle H_{i}$ de ${\displaystyle i}$ resultados de la eliminación de ${\displaystyle x_{j}$.
• ${\displaystyle I_{i}$, el conjunto de implícitamente eliminado variables, i.e. por accidente. Una variable se elimina implícitamente cuando aparece en al menos una desigualdad ${\displaystyle H_{i}$, pero no aparece en la desigualdad ${\displaystyle i}$ ni en ${\displaystyle E_{i}$
• ${\displaystyle R_{i}$, todas las variables restantes.

Una desigualdad no redundante tiene la propiedad de que su historia es mínima.

Teorema (Teorema de aceleración de Imbert). Si la historia ${\displaystyle H_{i}$ de una desigualdad ${\displaystyle i}$ es mínimo, entonces ${\displaystyle 1+ vidas_{i} eternas\\leq\ Silencio_{i} eterna\\leq 1+\left habitE_{i}\cup (I_{i}\cap O_{k})\justo$.

Una desigualdad que no satisface estos límites es necesariamente redundante y puede eliminarse del sistema sin cambiar su conjunto de soluciones.

El segundo teorema de aceleración detecta conjuntos históricos mínimos:

Teorema (Teorema de aceleración deImbert). Si la desigualdad ${\displaystyle i}$ es tal que ${\displaystyle 1+ vivenE_{i}$Entonces ${\displaystyle H_{i}$ es mínimo.

Este teorema proporciona un criterio de detección rápido y se utiliza en la práctica para evitar comprobaciones más costosas, como las basadas en rangos de matrices. Consulte la referencia para obtener detalles de implementación.

Las pruebas de viabilidad de la teoría de la información dan como resultado condiciones bajo las cuales se garantiza la existencia de un esquema de codificación de buen rendimiento. Estas condiciones se describen a menudo mediante un sistema lineal de desigualdades. Las variables del sistema incluyen tanto las tasas de transmisión (que son parte de la formulación del problema) como las tasas auxiliares adicionales utilizadas para el diseño del esquema. Comúnmente, uno intenta describir los límites fundamentales de la comunicación solo en términos de los parámetros del problema. Esto da lugar a la necesidad de eliminar las tasas auxiliares mencionadas anteriormente, lo que se ejecuta mediante la eliminación de Fourier-Motzkin. Sin embargo, el proceso de eliminación da como resultado un nuevo sistema que posiblemente contenga más desigualdades que el original. Sin embargo, a menudo algunas de las desigualdades en el sistema reducido son redundantes. La redundancia puede estar implícita en otras desigualdades o en desigualdades en la teoría de la información (también conocidas como desigualdades de tipo Shannon). Un software de código abierto desarrollado recientemente para MATLAB realiza la eliminación, al tiempo que identifica y elimina las desigualdades redundantes. En consecuencia, el software genera un sistema simplificado (sin redundancias) que solo involucra las tasas de comunicación.

La restricción redundante puede identificarse resolviendo un programa lineal como sigue. Dado un sistema de limitaciones lineales, si el ${\displaystyle i}$-la desigualdad está satisfecha para cualquier solución de todas las demás desigualdades, entonces es redundante. Análogamente, STIs refers to inequalities that are imply by the non-negativity of information theoretic measures and basic identities they satisfy. Por ejemplo, la CTI ${\displaystyle I(X_{1};X_{2})\leq H(X_{1}$ es una consecuencia de la identidad ${\displaystyle I(X_{1};X_{2})=H(X_{1})-H(X_{1}$ y la no negativa de la entropía condicional, es decir, ${\displaystyle H(X_{1} 0}$. Las desigualdades tipo Shannon definen un cono en ${\displaystyle \mathbb [R] ^{2^{n}-1}$, donde ${\displaystyle n}$ es el número de variables aleatorias que aparecen en las medidas de información involucradas. En consecuencia, cualquier CTI puede ser probada mediante programación lineal comprobando si está implicada por las identidades básicas y las limitaciones no negativas. El algoritmo descrito primero realiza la eliminación de Fourier-Motzkin para eliminar las tasas auxiliares. Luego impone las restricciones teóricas de la información no negativas al sistema de producción reducido y elimina las desigualdades redundantes.

• La lema de Farkas puede ser probada usando eliminación FM.
• Campo cerrado real – el algoritmo de descomposición algebraica cilíndrica realiza eliminación cuantitativa sobre polinomios desigualdades, no sólo lineales.

• Schrijver, Alexander (1998). Theory of Linear and Integer Programming. Los hijos de John Wiley. pp. 155–156. ISBN 978-0-471-98232-6.
• Keßler, Christoph W. (1996). "Parallel Fourier-Motzkin Elimination". Universität Trier: 66–71. CiteSeerX 10.1.1.54.657.
• Williams, H. P. (1986). "El método de programación lineal de Franceier y su dual" (PDF). American Mathematical Mensual. 93 (9): 681 –695. doi:10.2307/2322281. JSTOR 2322281.

• Capítulo 1 de Convexidad de Pregrado, libro de texto de Niels Lauritzen en la Universidad de Aarhus.
• Software FME para teoría de la información, código de código de código abierto en MATLAB por Ido B. Gattegno, Ziv Goldfeld y Haim H. Permuter.
• Eliminación simbólica Fourier-Motzkin, código de código abierto en Python implementando los dos teoremas de aceleración Imbert.