El lema de Farkas es un teorema de resolubilidad para un sistema finito de desigualdades lineales en matemáticas. Originalmente fue probado 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 jugado un papel central en el desarrollo de la optimización matemática (alternativamente, programación matemática ). Se utiliza, entre otras cosas, en la demostración del teorema de Karush-Kuhn-Tucker en programación no lineal . [2]Sorprendentemente, 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 medidas. [3]
Las generalizaciones del lema de Farkas se refieren al teorema de solubilidad para desigualdades convexas, [4] es decir, un sistema infinito de desigualdades lineales. El lema de Farkas pertenece a una clase de enunciados llamados "teoremas de la alternativa": un teorema que establece que exactamente uno de dos sistemas tiene una solución.
Declaración del lema
Hay varias formulaciones ligeramente diferentes (pero equivalentes) del lema en la literatura. El que se da aquí se debe a Gale, Kuhn y Tucker (1951). [5]
Lema de Farkas - Let y . Entonces, exactamente una de las siguientes dos afirmaciones es verdadera:
- Existe un tal que y .
- Existe un tal que y .
Aquí, la notación significa que todos los componentes del vector son no negativos.
Ejemplo
Sea m , n = 2,, y . El lema dice que exactamente una de las siguientes dos afirmaciones debe ser verdadera (dependiendo de b 1 y b 2 ):
- Existen x 1 ≥ 0, x 2 ≥ 0 tal que 6 x 1 + 4 x 2 = b 1 y 3 x 1 = b 2 , o
- Existen y 1 , y 2 tales que 6 y 1 + 3 y 2 ≥ 0, 4 y 1 ≥ 0, y b 1 y 1 + b 2 y 2 <0.
Aquí hay una prueba del lema en este caso especial:
- Si b 2 ≥ 0 y b 1 - 2 b 2 ≥ 0, entonces la opción 1 es cierto, puesto que la solución de las ecuaciones lineales es x 1 = b 2 /3 y x 2 = b 1 -2 b 2 . La opción 2 es falsa, ya que b 1 y 1 + b 2 y 2 ≥ b 2 (2 y 1 + y 2 ) = b 2 (6 y 1 + 3 y 2 ) / 3, entonces si el lado derecho es positivo , el lado izquierdo también debe ser positivo.
- De lo 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 2 <0, entonces podemos tomar, por ejemplo, y 1 = 0 y y 2 = 1.
- Si b 1 - 2 b 2 <0, entonces, para algún número B > 0, b 1 = 2 b 2 - B, entonces: b 1 y 1 + b 2 y 2 = 2 b 2 y 1 + b 2 y 2 - B y 1 = b 2 (6 y 1 + 3 y 2 ) / 3 - B y 1 . Por tanto, podemos tomar, por ejemplo, y 1 = 1, y 2 = −2.
Interpretación geométrica
Considere el cono convexo cerrado atravesado por las columnas de ; es decir,
Observa eso es el conjunto de los vectores para lo cual es válida la primera afirmación del enunciado del lema de Farkas. Por otro lado, el vectoren la segunda afirmación es ortogonal a un hiperplano que separa y . El lema se deriva de la observación de que pertenece a si y solo si no hay hiperplano que lo separe de .
Más precisamente, dejemos denotar las columnas de . En términos de estos vectores, el lema de Farkas establece que exactamente una de las siguientes dos afirmaciones es verdadera:
- Existen coeficientes no negativos tal que .
- Existe un vector tal que por , y .
Las sumas con coeficientes no negativos forman el cono atravesado por las columnas de . Por lo tanto, la primera declaración dice que pertenece a .
La segunda declaración dice que existe un vector tal que el ángulo de con los vectores es como máximo 90 °, mientras que el ángulo de con el vector es más de 90 °. El hiperplano normal a este vector tiene los vectores en un lado y el vector Por otro lado. Por lo tanto, este hiperplano separa el cono atravesado por del vector .
Por ejemplo, dejar que n , m = 2, un 1 = (1, 0) T , y un 2 = (1, 1) T . El cono convexo atravesado por un 1 y un 2 puede verse como un corte en forma de cuña del primer cuadrante en el plano xy . Ahora, suponga que b = (0, 1). Ciertamente, b no está en el cono convexo a 1 x 1 + a 2 x 2 . Por lo tanto, debe haber un hiperplano separador. Deje que Y = (1, -1) T . Podemos ver que a 1 · y = 1, a 2 · y = 0 y b · y = −1. Por lo tanto, el hiperplano con y normal de hecho separa el cono convexo a 1 x 1 + a 2 x 2 de b .
Interpretación lógica
Una versión particularmente sugerente y fácil de recordar es la siguiente: si un conjunto de desigualdades 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 una solución. [6] Tenga en cuenta que es una combinación de los lados izquierdos, una combinación del lado derecho de las desigualdades. Dado que la combinación positiva produce un vector cero a la izquierda y un -1 a la derecha, la contradicción es evidente.
Por tanto, 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 se puede refutar usando las reglas de derivación. [7] : 92–94
Variantes
El Lema de Farkas tiene varias variantes con diferentes restricciones de signo (la primera es la versión original): [7] : 92
- O el sistema tiene una solución con , o el sistema tiene una solución con .
- O el sistema tiene una solución con , o el sistema tiene una solución con y .
- O el sistema tiene una solución con , o el sistema tiene una solución con y .
- O el sistema tiene una solución con , o el sistema tiene una solución con .
La última variante se menciona para completar; en realidad, no es un "lema de Farkas" ya que solo contiene igualdades. Su demostración es un simple ejercicio de álgebra lineal .
Generalizaciones
Lema generalizado de Farkas - Let, , es un cono convexo cerrado en , y el cono dual de es . Si cono convexo está cerrado, entonces exactamente una de las siguientes dos afirmaciones es verdadera:
- Existe un tal que y .
- Existe un tal que y .
El lema de Farkas generalizado se puede interpretar geométricamente de la siguiente manera: o un vector está en un cono convexo cerrado dado , o existe un hiperplano que separa el vector del cono; no hay otras posibilidades. La condición de cierre es necesaria, ver Teorema de separación I en Teorema de separación de hiperplano . Para el lema original de Farkas, es el orthant no negativo , por lo tanto, la condición de cierre se mantiene automáticamente. De hecho, para el cono convexo poliédrico, es decir, existe un tal que , la condición de cierre se mantiene automáticamente. En la optimización convexa , varios tipos de calificación de restricción, por ejemplo, la condición de Slater , son responsables del cierre del cono convexo subyacente..
Configurando y en el lema generalizado de Farkas, obtenemos el siguiente corolario sobre la solubilidad de un sistema finito de igualdades lineales:
Corolario - Let y . Entonces, exactamente una de las siguientes dos afirmaciones es verdadera:
- Existe un tal que .
- Existe un tal que y .
Implicaciones adicionales
El lema de Farkas se puede variar a muchos otros teoremas alternativos mediante modificaciones simples, como el teorema de Gordan :tiene una solución x , otiene una solución distinta de cero y con y ≥ 0.
Las aplicaciones comunes del lema de Farkas incluyen probar el fuerte teorema de la dualidad asociado con la programación lineal , la teoría de juegos en un nivel básico, [ aclaración necesaria ] y las restricciones de 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 semidefinito. Es suficiente probar la existencia de las restricciones de Kuhn-Tucker utilizando la alternativa de Fredholm, pero para que la condición sea necesaria, se debe aplicar el teorema del minimax de Von Neumann para mostrar que las ecuaciones derivadas de Cauchy no se violan.
Ver también
- Teorema de separación de hiperplano
- Programa lineal dual
- Eliminación de Fourier-Motzkin : se puede utilizar para probar el lema de Farkas.
Notas
- ↑ 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
- ^ Takayama, Akira (1985). Economía Matemática (2ª ed.). Nueva York: Cambridge University Press. pag. 48 . ISBN 0-521-31498-4.
- ^ 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
- ^ 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
- ^ Gale, David ; Kuhn, Harold ; Tucker, Albert W. (1951), "Programación lineal y la teoría de los juegos - Capítulo XII" (PDF) , en Koopmans (ed.), Análisis de actividad de producción y asignación , Wiley. Consulte el Lema 1 en la página 318.
- ^ 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.
- ^ a b 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.
Otras lecturas
- Goldman, AJ; Tucker, AW (1956). "Conos convexos poliédricos" . En Kuhn, HW; Tucker, AW (eds.). Desigualdades lineales y sistemas relacionados . Princeton: Prensa de la Universidad de Princeton. págs. 19–40. ISBN 0691079994.
- Rockafellar, RT (1979). Análisis convexo . Prensa de la Universidad de Princeton. pag. 200.
- Kutateladze SS El lema de Farkas revisitado. Revista de matemáticas de Siberia , 2010, vol. 51, núm. 1, 78–87.