¿Cuál es la utilidad/significado del lema de Farkas?

Question

Trabajé en un ejercicio para demostrar el lema de Farkas, que establece que para $A \in \mathbb{R}^{m,n}$ y $b \in \mathbb{R}^n$ exactamente una de las siguientes es verdadera:

• Existe $x \ge 0$ tal que $Ax=b$ .
• Existe $y$ tal que $A^T y \ge 0$ y $y^T b < 0$ .

Esto es simplemente un hecho trivial sobre la separación entre dos conjuntos convexos cerrados: $S_1 = \{ b \}$ y $S_2 = \{ Ax \mid x \ge 0 \}$ .

Dada su sencillez, debe haber algún significado o aplicación más amplia de este hecho. ¿Puede alguien aclararme cuál es?

Answer 1

El conjunto factible de la optimización suele escribirse como

$$\{x| x \ge 0, Ax=b\}$$

Podríamos construir el conjunto factible anterior preguntando a un cliente qué es lo que desea e incluimos ese criterio en el conjunto anterior. Una pregunta natural es si el conjunto no es vacío, es decir, si el problema de optimización no es factible.

Lo que el lema de Farkas le ha prometido es que si puede encontrar tal $y$ tal que $A^Ty \ge 0$ y $y^Tb <0$ entonces se ha demostrado que el conjunto es vacío. El lema de Farkas nos ha prometido la existencia de un certificado $y$ para demostrar que el conjunto está vacío.