Variables mínimas relevantes en un sistema lineal

El problema de las variables mínimas relevantes en sistemas lineales ( Min-RVLS ) es un problema de optimización matemática . Dado un programa lineal , se requiere encontrar una solución factible en la que el número de variables distintas de cero sea el menor posible.

Se sabe que el problema es NP-difícil e incluso difícil de aproximar.

Definición

Un problema Min-RVLS se define por: ^[1]

• Una relación binaria R , que es una de {=, ≥, >, ≠};
• Una matriz A de m por n (donde m es el número de restricciones y n el número de variables);
• Un vector b de m por 1 .

El sistema lineal viene dado por: A x R b. Se supone que es factible (es decir, que se satisface por al menos un x ). Dependiendo de R, existen cuatro variantes diferentes de este sistema: A x = b, A x ≥ b, A x > b, A x ≠ b .

El objetivo es encontrar un vector x de n por 1 que satisfaga el sistema A x R b y, sujeto a ello, contenga la menor cantidad posible de elementos distintos de cero.

Caso especial

El problema Min-RVLS[=] fue presentado por Garey y Johnson ^[2] , quienes lo llamaron "solución de peso mínimo para ecuaciones lineales". Demostraron que era NP-hard, pero no consideraron aproximaciones.

Aplicaciones

El problema Min-RVLS es importante en el aprendizaje automático y el análisis discriminante lineal . Dado un conjunto de ejemplos positivos y negativos, se requiere minimizar la cantidad de características que se requieren para clasificarlos correctamente. ^[3] El problema se conoce como el problema del conjunto mínimo de características. Un algoritmo que se aproxima a Min-RVLS dentro de un factor de podría reducir sustancialmente la cantidad de muestras de entrenamiento necesarias para alcanzar un nivel de precisión determinado. ^[4] ${\displaystyle O(\log(m))}$

El problema de palabras de código más cortas en la teoría de codificación es el mismo problema que Min-RVLS[=] cuando los coeficientes están en GF(2).

Problemas relacionados

En las relaciones lineales mínimas insatisfechas ( Min-ULR ), se nos da una relación binaria R y un sistema lineal A x R b , que ahora se supone que es inviable . El objetivo es encontrar un vector x que viole la menor cantidad posible de relaciones, al tiempo que satisface todas las demás.

Min-ULR[≠] es trivialmente solucionable, ya que cualquier sistema con variables reales y un número finito de restricciones de desigualdad es factible. En cuanto a las otras tres variantes:

• Min-ULR[=,>,≥] son ​​NP-hard incluso con sistemas homogéneos y coeficientes bipolares (coeficientes en {1,-1}). ^[5]
• El conjunto de arcos de retroalimentación mínimos del problema NP-completo se reduce a Min-ULR[≥], con exactamente un 1 y un -1 en cada restricción, y todos los lados derechos iguales a 1. ^[6]
• Min-ULR[=,>,≥] son ​​polinomiales si el número de variables n es constante: se pueden resolver polinomialmente utilizando un algoritmo de Greer ^[7] en el tiempo . ${\displaystyle O(n\cdot m^{n}/2^{n-1})}$
• Min-ULR[=,>,≥] son ​​lineales si el número de restricciones m es constante, ya que todos los subsistemas pueden comprobarse en el tiempo O ( n ).
• Min-ULR[≥] es polinomial en algún caso especial. ^[6]
• Min-ULR[=,>,≥] se puede aproximar dentro de n  + 1 en tiempo polinomial. ^[1]
• Min-ULR[>,≥] son ​​conjuntos mínimos dominantes , incluso con sistemas homogéneos y coeficientes ternarios (en {−1,0,1}).
• Min-ULR[=] no se puede aproximar dentro de un factor de , para cualquier , a menos que NP esté contenido en DTIME ( ). ^[8] ${\displaystyle 2^{\log ^{1-\varepsilon }n}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n^{\operatorname {polylog} (n)}}$

En el problema complementario del subsistema lineal máximo factible ( Max-FLS ), el objetivo es encontrar un subconjunto máximo de restricciones que se puedan satisfacer simultáneamente. ^[5]

• Max-FLS[≠] se puede resolver en tiempo polinomial.
• Max-FLS[=] es NP-hard incluso con sistemas homogéneos y coeficientes bipolares.

• Con coeficientes enteros, es difícil aproximarse dentro de . Con coeficientes sobre GF[q], es q -aproximable. ${\displaystyle m^{\varepsilon }}$
• Max-FLS[>] y Max-FLS[≥] son ​​NP-hard incluso con sistemas homogéneos y coeficientes bipolares. Son 2-aproximables, pero no pueden aproximarse dentro de ningún factor constante más pequeño.

Dureza de aproximación

Las cuatro variantes de Min-RVLS son difíciles de aproximar. En particular, las cuatro variantes no se pueden aproximar dentro de un factor de , para cualquier , a menos que NP esté contenido en DTIME ( ). ^{[1] : 247–250} La dificultad se demuestra mediante reducciones: ${\displaystyle 2^{\log ^{1-\varepsilon }n}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n^{\operatorname {polylog} (n)}}$

• Hay una reducción de Min-ULR[=] a Min-RVLS[=]. También se aplica a Min-RVLS[≥] y Min-RVLS[>], ya que cada ecuación puede reemplazarse por dos desigualdades complementarias.
• Hay una reducción del conjunto mínimo dominante a Min-RVLS[≠].

Por otra parte, existe una reducción de Min-RVLS[=] a Min-ULR[=]. También se aplica a Min-ULR[≥] y Min-ULR[>], ya que cada ecuación puede ser reemplazada por dos desigualdades complementarias.

Por lo tanto, cuando R está en {=,>,≥}, Min-ULR y Min-RVLS son equivalentes en términos de dureza de aproximación.

Referencias

1. Amaldi, Edoardo; Kann, Viggo (diciembre de 1998). "Sobre la aproximabilidad de la minimización de variables no nulas o relaciones insatisfechas en sistemas lineales". Ciencias de la Computación Teórica . 209 (1–2): 237–260. doi : 10.1016/S0304-3975(97)00115-1 .
2. Garey, Michael R.; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la completitud NP . WH Freeman. ISBN 978-0-7167-1044-8.
3. Koehler, Gary J. (noviembre de 1991). "Funciones discriminantes lineales determinadas por búsqueda genética". ORSA Journal on Computing . 3 (4): 345–357. doi :10.1287/ijoc.3.4.345.
4. Van Horn, Kevin S.; Martinez, Tony R. (enero de 1994). "El problema del conjunto mínimo de características". Redes neuronales . 7 (3): 491–494. doi :10.1016/0893-6080(94)90082-5.
5. Amaldi, Edoardo; Kann, Viggo (agosto de 1995). "La complejidad y aproximabilidad de encontrar subsistemas máximos factibles de relaciones lineales". Ciencias de la Computación Teórica . 147 (1–2): 181–210. doi : 10.1016/0304-3975(94)00254-G .
6. Sankaran, Jayaram K (febrero de 1993). "Una nota sobre la resolución de la inviabilidad en programas lineales mediante la relajación de restricciones". Operations Research Letters . 13 (1): 19–20. doi :10.1016/0167-6377(93)90079-V.
7. Greer, R. (2011). Árboles y colinas: metodología para maximizar funciones de sistemas de relaciones lineales . Elsevier. ISBN 978-0-08-087207-0.^{[ página necesaria ]}
8. Arora, Sanjeev; Babai, László; Stern, Jacques; Sweedyk, Z (abril de 1997). "La dureza de los óptimos aproximados en redes, códigos y sistemas de ecuaciones lineales". Revista de Ciencias de la Computación y de Sistemas . 54 (2): 317–331. doi : 10.1006/jcss.1997.1472 .