Eliminación de Fourier-Motzkin

Algoritmo matemático para eliminar variables de un sistema de inecuaciones lineales

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 lleva el nombre de Joseph Fourier ^[1], quien propuso el método en 1826, y Theodore Motzkin, quien lo redescubrió en 1936.

Eliminación

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 tienen 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. En ese caso, resulta trivial decidir si el sistema resultante es verdadero o falso. Es verdadero si y solo 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.

Considérese un sistema de inecuaciones con variables a , con la variable a eliminar. Las inecuaciones lineales del sistema se pueden agrupar en tres clases según el signo (positivo, negativo o nulo) del coeficiente para . ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{r}}$ ${\displaystyle x_{r}}$ ${\displaystyle x_{r}}$

• aquellas desigualdades que son de la forma ; denote estas por , para que van desde 1 hasta donde es el número de tales desigualdades; ${\displaystyle x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$ ${\displaystyle x_{r}\geq A_{i}(x_{1},\dots ,x_{r-1})}$ ${\displaystyle i}$ ${\displaystyle n_{A}}$ ${\displaystyle n_{A}}$
• aquellas desigualdades que son de la forma ; denote estas por , para que van desde 1 hasta donde es el número de tales desigualdades; ${\displaystyle x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$ ${\displaystyle x_{r}\leq B_{i}(x_{1},\dots ,x_{r-1})}$ ${\displaystyle i}$ ${\displaystyle n_{B}}$ ${\displaystyle n_{B}}$
• aquellas desigualdades en las que no juega ningún papel, agrupadas en una sola conjunción . ${\displaystyle x_{r}}$ ${\displaystyle \phi }$

El sistema original es por tanto equivalente a

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

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

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

La desigualdad

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

es equivalente a las desigualdades , para y . ${\displaystyle n_{A}n_{B}}$ ${\displaystyle A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$ ${\displaystyle 1\leq i\leq n_{A}}$ ${\displaystyle 1\leq j\leq n_{B}}$

Por lo tanto, hemos transformado el sistema original en otro sistema donde se elimina . Observe que el sistema de salida tiene desigualdades. En particular, si , entonces el número de desigualdades de salida es . ${\displaystyle x_{r}}$ ${\displaystyle (n-n_{A}-n_{B})+n_{A}n_{B}}$ ${\displaystyle n_{A}=n_{B}=n/2}$ ${\displaystyle n^{2}/4}$

Ejemplo

Consideremos el siguiente sistema de desigualdades: ^{[2] : 100–102}

${\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. Si eliminamos x obtendremos 2*2 = 4 inecuaciones en las variables restantes, y lo mismo ocurriría si eliminamos y. Si eliminamos z obtendremos solo 3*1 = 3 inecuaciones, por lo que utilizaremos esa 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 {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 2 variables en lugar de 3. Examinando los signos de los coeficientes para cada variable se obtiene que y es todo positivo, 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 tanto, existen x y z correspondientes para los sistemas más grandes también, y hay infinitas soluciones de este tipo. Por ejemplo, fijar y = -1000000, x = 0, z = -2222222 satisface tanto el sistema original como los reducidos.

Complejidad

La ejecución de un paso de eliminación sobre desigualdades puede dar como resultado, como máximo, desigualdades en el resultado, por lo que la ejecución ingenua de pasos sucesivos puede dar como máximo una complejidad exponencial doble. Esto se debe a que el algoritmo produce muchas restricciones redundantes implícitas en otras restricciones. ${\displaystyle n}$ ${\displaystyle n^{2}/4}$ ${\displaystyle d}$ ${\displaystyle 4(n/4)^{2^{d}}}$

Teorema de límite superior de McMullen que establece que el número de restricciones no redundantes crece como un exponente único. ^{[3] En [4]} se proporciona una implementación exponencial única de la eliminación de Fourier-Motzkin y estimaciones de complejidad.

Es bien conocido que la programación lineal brinda soluciones a sistemas de desigualdades en tiempo polinomial, favoreciéndola sobre la eliminación de Fourier-Motzkin.

Teoremas de aceleración de Imbert

Dos teoremas de "aceleración" debidos a Imbert ^[5] permiten la eliminación de desigualdades redundantes basadas únicamente en propiedades sintácticas del árbol de derivación de fórmulas, reduciendo así la necesidad de resolver programas lineales o calcular rangos de matrices.

Defina la historia de una desigualdad como el conjunto de índices de desigualdades del sistema inicial que se utilizaron para producir . Por lo tanto, para las desigualdades del sistema inicial. Al agregar una nueva desigualdad (eliminando ), la nueva historia se construye como . ${\displaystyle H_{i}}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle H_{i}=\{i\}}$ ${\displaystyle i\in S}$ ${\displaystyle k:A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$ ${\displaystyle x_{r}}$ ${\displaystyle H_{k}}$ ${\displaystyle H_{k}=H_{i}\cup H_{j}}$

Supongamos que las variables han sido eliminadas oficialmente . Cada desigualdad divide el conjunto en : ${\displaystyle O_{k}=\{x_{r},\ldots ,x_{r-k+1}\}}$ ${\displaystyle i}$ ${\displaystyle O_{k}}$ ${\displaystyle E_{i}\cup I_{i}\cup R_{i}}$

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

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

Teorema (primer teorema de aceleración de Imbert). Si la historia de una desigualdad es mínima, entonces . ${\displaystyle H_{i}}$ ${\displaystyle i}$ ${\displaystyle 1+|E_{i}|\ \leq \ |H_{i}|\ \leq 1+\left|E_{i}\cup (I_{i}\cap O_{k})\right|}$

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 (segundo teorema de aceleración de Imbert). Si la desigualdad es tal que , entonces es mínima. ${\displaystyle i}$ ${\displaystyle 1+|E_{i}|=|H_{i}|}$ ${\displaystyle H_{i}}$

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. ^[6]

Aplicaciones en la teoría de la informació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 apunta a 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 contiene 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 ^[7] realiza la eliminación, al tiempo que identifica y elimina las desigualdades redundantes. En consecuencia, el software genera un sistema simplificado (sin redundancias) que involucra únicamente las velocidades de comunicación.

La restricción redundante se puede identificar resolviendo un programa lineal como sigue. Dado un sistema de restricciones lineales, si la -ésima desigualdad se satisface para cualquier solución de todas las demás desigualdades, entonces es redundante. De manera similar, las STI se refieren a desigualdades que están implícitas por la no negatividad de las medidas de teoría de la información y las identidades básicas que satisfacen. Por ejemplo, la STI es una consecuencia de la identidad y la no negatividad de la entropía condicional, es decir, . Las desigualdades de tipo Shannon definen un cono en , donde es el número de variables aleatorias que aparecen en las medidas de información involucradas. En consecuencia, cualquier STI se puede demostrar mediante programación lineal verificando si está implícita por las identidades básicas y las restricciones de no negatividad. El algoritmo descrito primero realiza la eliminación de Fourier-Motzkin para eliminar las tasas auxiliares. Luego, impone las restricciones de no negatividad de la teoría de la información en el sistema de salida reducido y elimina las desigualdades redundantes. ${\displaystyle i}$ ${\displaystyle I(X_{1};X_{2})\leq H(X_{1})}$ ${\displaystyle I(X_{1};X_{2})=H(X_{1})-H(X_{1}|X_{2})}$ ${\displaystyle H(X_{1}|X_{2})\geq 0}$ ${\displaystyle \mathbb {R} ^{2^{n}-1}}$ ${\displaystyle n}$

Véase también

• Lema de Farkas : se puede demostrar mediante eliminación de FM.
• Campo cerrado real : el algoritmo de descomposición algebraica cilíndrica realiza la eliminación de cuantificadores sobre desigualdades polinomiales , no solo lineales.

Referencias

1. Fourier, José (1827). "Histoire de l'Académie, partie mathématique (1824)". Mémoires de l'Académie des sciences del'Institut de France . vol. 7. Gauthier-Villars.
2. Gartner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8.Páginas 81–104.
3. David Monniaux, Eliminación de cuantificadores mediante enumeración de modelos perezosos, Verificación asistida por computadora (CAV) 2010.
4. RJ. Jing, M. Moreno-Maza y D. Talaashrafi [1] Estimaciones de complejidad para la eliminación de Fourier-Motzkin . En: Boulier, F., England, M., Sadykov, TM, Vorozhtsov, EV (eds) Álgebra informática en computación científica. CASC 2020. Apuntes de clase en informática, vol. 12291. Springer,]
5. Jean-Louis Imbert, Acerca de las desigualdades redundantes generadas por el algoritmo de Fourier , Inteligencia Artificial IV: Metodología, Sistemas, Aplicaciones, 1990.
6. Jean-Louis Imbert, Eliminación de Fourier: ¿cuál elegir?.
7. Gattegno, Ido B.; Goldfeld, Ziv; Permuter, Haim H. (25 de septiembre de 2015). "Software de eliminación de Fourier-Motzkin para desigualdades teóricas de la información". arXiv : 1610.03990 [cs.IT].

Lectura adicional

• Schrijver, Alejandro (1998). Teoría de la Programación Lineal y Entera . John Wiley e hijos. págs. 155-156. ISBN 978-0-471-98232-6.
• Keßler, Christoph W. (1996). "Eliminación paralela de Fourier-Motzkin". Universidad de Trier : 66–71. CiteSeerX  10.1.1.54.657 .
• Williams, HP (1986). "El método de Fourier de programación lineal y su dualidad" (PDF) . American Mathematical Monthly . 93 (9): 681–695. doi :10.2307/2322281. JSTOR  2322281.

Enlaces externos

• 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 abierto en MATLAB por Ido B. Gattegno, Ziv Goldfeld y Haim H. Permuter.
• Eliminación simbólica de Fourier-Motzkin, código abierto en Python que implementa los dos teoremas de aceleración de Imbert.