Lema de Farkas: intuición puramente algebraica

Question

He aquí una declaración de Lemma de Farkas de la Wikipedia. En $A$ ser un $m \times n$ matriz y $b$ un $m$ -vector dimensional. Entonces, exactamente una de las dos afirmaciones siguientes es cierta:

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

Este resultado tiene una interpretación geométrica sencilla: o bien $b$ se encuentra en el cono formado por las columnas de $A$ o es posible encontrar un vector $y$ tal que $y$ forma un ángulo agudo con todas las columnas de $A$ y un ángulo obtuso con $b$ .

Me preguntaba si hay alguna forma de hacer que el resultado sea intuitivo puramente a nivel algebraico de resolución de ecuaciones lineales e inecuaciones.

El lema es importante en finanzas y la intuición geométrica no es de mucha ayuda allí ya que los vectores son pagos y precios de activos financieros que no tienen un significado geométrico natural. Gale Teoría de los modelos económicos lineales tiene una prueba puramente algebraica, pero es un argumento de inducción opaco.

EDIT: Un poco más sobre mi solicitud. Tenemos $m$ activos y $n$ posibles estados futuros de la naturaleza. $A_{ij}$ es la retribución por activo $i$ en el estado $j$ . $b_i$ es el precio del activo $i$ . $x_j$ es el valor de un dólar en el estado $j$ . $y_i$ es el importe del activo $i$ en una cartera.

Así que el lema de Farkas nos dice que o bien (1) hay una manera de asignar un precio no negativo a un dólar en cada estado de tal manera que el precio de cada activo es sólo la suma total del valor de sus pagos, o bien (2) hay una cartera cuyo precio es negativo, por lo que te pagan por tenerla, pero cuyos pagos son no negativos, lo que significa que no tienes que devolver nada. Quiero entender, en términos que tengan sentido económico, por qué (1) y (2) deben ser mutuamente excluyentes. Los ángulos agudos y obtusos no ayudan.

Answer 1

Si quiere una intuición que explique por qué El Lemma de Farka debería ser cierto, tendrás que usar la interpretación geométrica; no hay forma de evitarlo.

Si quieres una intuición que muestre qué logra el Lemma de Farka (pero no por qué debería ser cierto), existe de hecho una explicación algebraica.

En concreto, el Lemma de Farka responde a la siguiente pregunta: ¿cuál es la condición suficiente y necesaria para que el sistema de ecuaciones

$$\begin{array}{rcl}a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &=& b_2 \\ &\vdots& \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &=& b_m \end{array}$$

tener una solución positiva $x_i\ge 0$ ?

Evidentemente, si una de las ecuaciones tiene la forma

$$ c_1x_1 + c_2x_2 + \dots + c_nx_n = b $$

donde todos los $c_i$ son positivos $c_i > 0$ pero el lado derecho $b$ es negativo $b<0$ entonces es claramente imposible elegir todos los $x_i$ positivos y que satisfagan la ecuación, porque el lado izquierdo siempre sería positivo.

Esto era sólo para una única ecuación, pero es igualmente obvio que si cualquier combinación lineal de las ecuaciones de su sistema

$$ \left(\sum y_i a_{i1}\right)x_1 + \left(\sum y_i a_{i2}\right)x_2 + \dots + \left(\sum y_i a_{in}\right) x_n = \sum y_i b_i $$

tiene esta forma con coeficientes positivos a la izquierda y un número negativo a la derecha, entonces no se puede resolver para $x_i \ge 0$ .

Ahora, lo que el Lemma de Farka dice es que este es de hecho el lo único malo que puede ocurrir. Si el sistema

$$Ax = b$$

no tiene solución $x\ge0$ entonces esto debe ser porque existe una combinación lineal desagradable de algunas ecuaciones

$$(y^TA)x = y^Tb$$

que obstaculiza la solvencia porque satisface $y^TA \ge 0$ pero $y^Tb \le 0$ .

En cierto sentido, el Lemma de Farka muestra que la no resolubilidad del sistema puede ser "certificada"; el vector $y$ es un "certificado" de que el sistema no puede resolverse. Tales certificados, comúnmente llamados obstrucciones son comunes en otras ramas de las matemáticas, como la geometría algebraica ( Nullstellensatz de Hilbert ) o topología algebraica (homología, cohomología).

Answer 2

En primer lugar, supongamos que se cumplen ambas condiciones. De la primera de ellas sabemos $x\geq 0$ a partir del segundo --- $y^TA\geq 0$ . Por lo tanto $y^Tb=y^TAx\geq 0$ . Contradicción.

Supongamos ahora que ambas condiciones son falsas. Sea $\{e_k\}_{k=1}^n$ sea la base estándar en $\mathbb{R}^n$ . Obsérvese que el conjunto $\{Ax\mid x\geq 0\} = \{\sum_kx_k Ae_k\mid x_k\geq 0\}$ está cerrado y toma el punto más cercano a $b$ en él. De la minimalidad de $\|b-Ax\|^2$ para cualquier $k$ tenemos $x_k>0$ y $\partial_{x_k}\|b-Ax\|^2=0$ o bien $x_k=0$ y $\partial_{x_k}\|b-Ax\|^2\geq 0$ . Así $$\left[\begin{aligned}x_k&>0,&(b-Ax,Ae_k)&=0,\\x_k&=0,& (b-Ax,Ae_k)&<0\end{aligned}\right.\tag{1}$$

Toma $y=Ax-b$ . A partir de (1) tenemos $(y,Ae_k)\geq 0$ y por lo tanto $A^Ty\geq 0$ . Finalmente $$b^Ty=(y,b)=(Ax-b,b)=(Ax-b,b-Ax)+(Ax-b,Ax)=$$ $$-\|b-Ax\|^2-\sum_kx_k (b-Ax,Ae_k)=-\|b-Ax\|^2<0.$$ Así que la segunda condición debe ser cierta. Contradicción.