El lema de Farkas

Teorema de solubilidad para sistemas finitos de desigualdades lineales

En matemáticas , el lema de Farkas es un teorema de solubilidad para un sistema finito de desigualdades lineales . Fue demostrado originalmente por el matemático húngaro Gyula Farkas . ^[1] El lema de Farkas es el resultado clave que sustenta la dualidad de la programación lineal y ha desempeñado un papel central en el desarrollo de la optimización matemática (alternativamente, programación matemática ). Se utiliza, entre otras cosas, en la prueba del teorema de Karush-Kuhn-Tucker en programación no lineal . ^[2] Cabe destacar que, en el área de los fundamentos de la teoría cuántica, el lema también subyace al conjunto completo de desigualdades de Bell en forma de condiciones necesarias y suficientes para la existencia de una teoría local de variables ocultas , dados los datos de cualquier conjunto específico de mediciones. ^[3]

Las generalizaciones del lema de Farkas se refieren al teorema de resolubilidad para desigualdades convexas, ^[4] es decir, sistemas infinitos de desigualdades lineales. El lema de Farkas pertenece a una clase de enunciados denominados "teoremas de la alternativa": un teorema que establece que exactamente uno de dos sistemas tiene solución. ^[5]

Enunciado del lema

En la literatura existen varias formulaciones del lema ligeramente diferentes (pero equivalentes). La que se presenta aquí se debe a Gale, Kuhn y Tucker (1951). ^[6]

Lema de Farkas  —  Sea y Entonces exactamente una de las dos afirmaciones siguientes es verdadera: ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}}$ ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m}.}$

1. Existe tal que y ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {Ax} =\mathbf {b} }$ ${\displaystyle \mathbf {x} \geq 0.}$
2. Existe tal que y ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}$

Aquí, la notación significa que todos los componentes del vector son no negativos. ${\displaystyle \mathbf {x} \geq 0}$ ${\displaystyle \mathbf {x} }$

Ejemplo

Sea m , n = 2 y El lema dice que exactamente una de las dos afirmaciones siguientes debe ser verdadera (dependiendo de b ₁ y b ₂ ): ${\displaystyle \mathbf {A} ={\begin{bmatrix}6&4\\3&0\end{bmatrix}},}$ ${\displaystyle \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}.}$

1. Existen x ₁ ≥ 0 , x ₂ ≥ 0 tales que 6 x ₁ + 4 x ₂ = b ₁ y 3 x ₁ = b ₂ , o
2. Existen y ₁ , y ₂ tales que 6 y ₁ + 3 y ₂ ≥ 0 , 4 y ₁ ≥ 0 y b ₁ y ₁ + b ₂ y ₂ < 0 .

He aquí una prueba del lema en este caso especial:

• Si b ₂ ≥ 0 y b ₁ − 2 b ₂ ≥ 0 , entonces la opción 1 es verdadera, ya que la solución de las ecuaciones lineales es y la opción 2 es falsa, ya que entonces si el lado derecho es positivo, el lado izquierdo también debe ser positivo. ${\displaystyle x_{1}={\tfrac {b_{2}}{3}}}$ ${\displaystyle x_{2}={\tfrac {b_{1}-2b_{2}}{4}}.}$ $${\displaystyle b_{1}y_{1}+b_{2}y_{2}\geq b_{2}(2y_{1}+y_{2})=b_{2}{\frac {6y_{1}+3y_{2}}{3}},}$$
• En caso contrario, la opción 1 es falsa, ya que la solución única de las ecuaciones lineales no es débilmente positiva. Pero en este caso, la opción 2 es verdadera:
  • Si b ₂ < 0 , entonces podemos tomar por ejemplo y ₁ = 0 y y ₂ = 1 .
  • Si b ₁ − 2 b ₂ < 0 , entonces, para algún número B > 0 , b ₁ = 2 b ₂ − B , por lo tanto: Así podemos tomar, por ejemplo, y ₁ = 1 , y ₂ = −2 . $${\displaystyle b_{1}y_{1}+b_{2}y_{2}=2b_{2}y_{1}+b_{2}y_{2}-By_{1}=b_{2}{\frac {6y_{1}+3y_{2}}{3}}-By_{1}.}$$

Interpretación geométrica

Consideremos el cono convexo cerrado generado por las columnas de A ; es decir, ${\displaystyle C(\mathbf {A} )}$

${\displaystyle C(\mathbf {A} )=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geq 0\}.}$

Obsérvese que es el conjunto de los vectores b para los que se cumple la primera afirmación del enunciado del lema de Farkas. Por otra parte, el vector y en la segunda afirmación es ortogonal a un hiperplano que separa a b y El lema se sigue de la observación de que b pertenece a si y solo si no hay hiperplano que lo separe de ${\displaystyle C(\mathbf {A} )}$ ${\displaystyle C(\mathbf {A} ).}$ ${\displaystyle C(\mathbf {A} )}$ ${\displaystyle C(\mathbf {A} ).}$

Más precisamente, denotemos las columnas de A . En términos de estos vectores, el lema de Farkas establece que exactamente una de las dos afirmaciones siguientes es verdadera: ${\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}\in \mathbb {R} ^{m}}$

1. Existen coeficientes no negativos tales que ${\displaystyle x_{1},\dots ,x_{n}\in \mathbb {R} }$ ${\displaystyle \mathbf {b} =x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}.}$
2. Existe un vector tal que para y ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$ ${\displaystyle \mathbf {a} _{i}^{\top }\mathbf {y} \geq 0}$ ${\displaystyle i=1,\dots ,n,}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}$

Las sumas con coeficientes no negativos forman el cono abarcado por las columnas de A . Por lo tanto, la primera afirmación dice que b pertenece a ${\displaystyle x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}}$ ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle C(\mathbf {A} ).}$

La segunda afirmación dice que existe un vector y tal que el ángulo de y con los vectores a _i es como máximo de 90°, mientras que el ángulo de y con el vector b es mayor de 90°. El hiperplano normal a este vector tiene los vectores a _i en un lado y el vector b en el otro lado. Por lo tanto, este hiperplano separa el cono generado por del vector b . ${\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}}$

Por ejemplo, sea n , m = 2 , a ₁ = (1, 0) ^T , y a ₂ = (1, 1) ^T . El cono convexo generado por a ₁ y a ₂ puede verse como una porción en forma de cuña del primer cuadrante en el plano xy . Ahora, supongamos que b = (0, 1) . Ciertamente, b no está en el cono convexo a ₁ x ₁ + a ₂ x ₂ . Por lo tanto, debe haber un hiperplano separador. Sea y = (1, −1) ^T . Podemos ver que a ₁ · y = 1 , a ₂ · y = 0 , y b · y = −1 . Por lo tanto, el hiperplano con normal y de hecho separa el cono convexo a ₁ x ₁ + a ₂ x ₂ de b .

Interpretación lógica

Una versión particularmente sugerente y fácil de recordar es la siguiente: si un conjunto de inecuaciones lineales no tiene solución, entonces se puede producir una contradicción a partir de él mediante una combinación lineal con coeficientes no negativos. En fórmulas: si es irresoluble entonces tiene solución. ^[7] Nótese que es una combinación de los lados izquierdos, una combinación del lado derecho de las inecuaciones. Como la combinación positiva produce un vector cero a la izquierda y un −1 a la derecha, la contradicción es evidente. ${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$ ${\displaystyle \mathbf {y} ^{\top }\mathbf {A} =0,}$ ${\displaystyle \mathbf {y} ^{\top }\mathbf {b} =-1,}$ ${\displaystyle \mathbf {y} \geq 0}$ ${\displaystyle \mathbf {y} ^{\top }\mathbf {A} }$ ${\displaystyle \mathbf {y} ^{\top }\mathbf {b} }$

Así, el lema de Farkas puede verse como un teorema de completitud lógica : es un conjunto de "axiomas", las combinaciones lineales son las "reglas de derivación", y el lema dice que, si el conjunto de axiomas es inconsistente, entonces puede ser refutado usando las reglas de derivación. ^{[8] : 92–94} ${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$

Implicaciones en la teoría de la complejidad

El lema de Farkas implica que el problema de decisión "Dado un sistema de ecuaciones lineales, ¿tiene una solución no negativa?" está en la intersección de NP y co-NP . Esto se debe a que, según el lema, tanto una respuesta "sí" como una respuesta "no" tienen una prueba que se puede verificar en tiempo polinomial. Los problemas en la intersección también se denominan problemas bien caracterizados . Es una pregunta abierta desde hace mucho tiempo si es igual a P. En particular, no se sabía que la pregunta de si un sistema de ecuaciones lineales tiene una solución no negativa estuviera en P, hasta que se demostró utilizando el método del elipsoide . ^{[9] : 25} ${\displaystyle NP\cap coNP}$ ${\displaystyle NP\cap coNP}$

Variantes

El lema de Farkas tiene varias variantes con diferentes restricciones de signo (la primera es la versión original): ^{[8] : 92}

• O tiene solución o tiene solución con ${\displaystyle \mathbf {Ax} =\mathbf {b} }$ ${\displaystyle \mathbf {x} \geq 0,}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0}$ ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}$
• O tiene solución o tiene solución con ${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$ ${\displaystyle \mathbf {x} \geq 0,}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} \geq 0}$ ${\displaystyle \mathbf {y} \geq 0}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0}$
• O bien tiene solución o bien tiene solución con . ${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$ ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n},}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}$ ${\displaystyle \mathbf {y} \geq 0}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0}$
• O tiene solución o tiene solución con ${\displaystyle \mathbf {Ax} =\mathbf {b} }$ ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n},}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}$ ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} \neq 0.}$

Se menciona la última variante para completar el texto; en realidad no es un "lema de Farkas", ya que sólo contiene igualdades. Su demostración es un ejercicio de álgebra lineal .

También existen lemas tipo Farkas para programas enteros. ^{[9] : 12--14} Para sistemas de ecuaciones, el lema es simple:

• Supongamos que A y b tienen coeficientes racionales. Entonces, o bien tiene una solución integral o bien existe una que es integral y otra que no lo es. ${\displaystyle \mathbf {Ax} =\mathbf {b} }$ ${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n},}$ ${\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} }$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} }$

En el caso de los sistemas de inecuaciones, el lema es mucho más complicado. Se basa en las dos reglas de inferencia siguientes :

1. Dadas desigualdades y coeficientes , inferir la desigualdad . ${\displaystyle a_{1}^{T}x\leq b_{1},\ldots ,a_{m}^{T}x\leq b_{m}}$ ${\displaystyle w_{1},\ldots ,w_{m}}$ ${\displaystyle \left(\sum _{i=1}^{m}w_{i}a_{i}^{T}\right)x\leq \sum _{i=1}^{m}w_{i}b_{i}}$
2. Dada una desigualdad , inferir la desigualdad . ${\displaystyle a_{1}x_{1}+\cdots +a_{m}x_{m}\leq b}$ ${\displaystyle \lfloor a_{1}\rfloor x_{1}+\cdots +\lfloor a_{m}\rfloor x_{m}\leq \lfloor b\rfloor }$

El lema dice que:

• Supongamos que A y b tienen coeficientes racionales. En ese caso, cualquiera de ellos tiene una solución integral o es posible inferir, a partir de un número finito de aplicaciones de las reglas de inferencia 1,2, la desigualdad . ${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$ ${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n},x\geq 0}$ ${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$ ${\displaystyle 0^{T}x\leq -1}$

Las variantes se resumen en la siguiente tabla.

Generalizaciones

Lema de Farkas generalizado  :  Sea un cono convexo cerrado en y el cono dual de es Si el cono convexo es cerrado, entonces exactamente una de las dos afirmaciones siguientes es verdadera: ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n},}$ ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m},}$ ${\displaystyle \mathbf {S} }$ ${\displaystyle \mathbb {R} ^{n},}$ ${\displaystyle \mathbf {S} }$ ${\displaystyle \mathbf {S} ^{*}=\{\mathbf {z} \in \mathbb {R} ^{n}\mid \mathbf {z} ^{\top }\mathbf {x} \geq 0,\forall \mathbf {x} \in \mathbf {S} \}.}$ ${\displaystyle C(\mathbf {A} )=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \in \mathbf {S} \}}$

1. Existe tal que y ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {Ax} =\mathbf {b} }$ ${\displaystyle \mathbf {x} \in \mathbf {S} .}$
2. Existe tal que y ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} \in \mathbf {S} ^{*}}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} <0.}$

El lema de Farkas generalizado se puede interpretar geométricamente de la siguiente manera: o bien un vector está en un cono convexo cerrado dado , o bien existe un hiperplano que separa el vector del cono; no hay otras posibilidades. La condición de clausura es necesaria, véase Teorema de separación I en Teorema de separación de hiperplanos . Para el lema de Farkas original, es el ortante no negativo, por lo que la condición de clausura se cumple automáticamente. De hecho, para un cono convexo poliédrico, es decir, existe un tal que la condición de clausura se cumple automáticamente. En la optimización convexa , varios tipos de calificación de restricción, por ejemplo, la condición de Slater , son responsables de la clausura del cono convexo subyacente. ${\displaystyle \mathbf {S} }$ ${\displaystyle \mathbb {R} _{+}^{n},}$ ${\displaystyle \mathbf {B} \in \mathbb {R} ^{n\times k}}$ ${\displaystyle \mathbf {S} =\{\mathbf {B} \mathbf {x} \mid \mathbf {x} \in \mathbb {R} _{+}^{k}\},}$ ${\displaystyle C(\mathbf {A} ).}$

Planteando y generalizando el lema de Farkas, obtenemos el siguiente corolario sobre la solubilidad de un sistema finito de igualdades lineales: ${\displaystyle \mathbf {S} =\mathbb {R} ^{n}}$ ${\displaystyle \mathbf {S} ^{*}=\{0\}}$

Corolario  —  Sea y Entonces exactamente una de las dos afirmaciones siguientes es verdadera: ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}}$ ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m}.}$

1. Existe tal que ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {Ax} =\mathbf {b} .}$
2. Existe tal que y ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}$ ${\displaystyle \mathbf {b} ^{\top }\mathbf {y} \neq 0.}$

Otras implicaciones

El lema de Farkas se puede variar para dar lugar a muchos otros teoremas de alternativa mediante modificaciones simples, ^[5] como el teorema de Gordan : O tiene una solución x , o tiene una solución distinta de cero y con y ≥ 0 . ${\displaystyle \mathbf {Ax} <0}$ ${\displaystyle \mathbf {A} ^{\top }\mathbf {y} =0}$

Las aplicaciones comunes del lema de Farkas incluyen la demostración del teorema de dualidad fuerte asociado con la programación lineal y las condiciones de Karush-Kuhn-Tucker . Se puede utilizar una extensión del lema de Farkas para analizar las condiciones de dualidad fuerte y construir el dual de un programa semidefinido. Es suficiente demostrar la existencia de las condiciones de Karush-Kuhn-Tucker utilizando la alternativa de Fredholm, pero para que la condición sea necesaria, se debe aplicar el teorema minimax de von Neumann para demostrar que las ecuaciones derivadas por Cauchy no se violan.

Véase también

• Programa lineal dual
• Eliminación de Fourier-Motzkin : se puede utilizar para demostrar el lema de Farkas.

Notas

1. Farkas, Julius (Gyula) (1902), "Theorie der Einfachen Ungleichungen", Journal für die reine und angewandte Mathematik , 1902 (124): 1–27, doi :10.1515/crll.1902.124.1, S2CID  115770124
2. Takayama, Akira (1985). Economía matemática (2.ª ed.). Nueva York: Cambridge University Press. pág. 48. ISBN 0-521-31498-4.
3. Garg, Anupam ; Mermin, ND (1984), "El lema de Farkas y la naturaleza de la realidad: implicaciones estadísticas de las correlaciones cuánticas", Fundamentos de la física , 14 : 1–39, doi :10.1007/BF00741645, S2CID  123622613
4. Dinh, N.; Jeyakumar, V. (2014), "El lema de Farkas: tres décadas de generalizaciones para la optimización matemática", TOP , 22 (1): 1–22, doi :10.1007/s11750-014-0319-y, S2CID  119858980
5. Border, KC (2013). "Desigualdades lineales alternativas" (PDF) . Consultado el 29 de noviembre de 2021 .
6. Gale, David ; Kuhn, Harold ; Tucker, Albert W. (1951), "Programación lineal y teoría de juegos - Capítulo XII" (PDF) , en Koopmans (ed.), Análisis de la actividad de producción y asignación , Wiley. Véase el Lema 1 en la página 318.
7. Boyd, Stephen P.; Vandenberghe, Lieven (2004), "Sección 5.8.3" (pdf) , Optimización convexa , Cambridge University Press, ISBN 978-0-521-83378-3, consultado el 15 de octubre de 2011.
8. Gärtner, 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.
9. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, Sr.  1261419

Lectura adicional

• Goldman, AJ; Tucker, AW (1956). "Conos convexos poliédricos". En Kuhn, HW; Tucker, AW (eds.). Desigualdades lineales y sistemas relacionados . Princeton: Princeton University Press. págs. 19–40. ISBN 0691079994.
• Rockafellar, RT (1979). Análisis convexo . Princeton University Press. pág. 200.
• Kutateladze SS El lema de Farkas revisitado. Siberian Mathematical Journal , 2010, vol. 51, núm. 1, 78–87.