Lema de Farkas

Teorema 1 (Lema de Farkas). Sean \(A\in\mathbb{R}^{m\times n}\) y \(b\in\mathbb{R}^m\). Entonces, exactamente uno de los siguientes conjuntos debe ser vacío:

  1. \(A:=\left\{x\in\mathbb{R}^n\,:\, Ax=b,\, x\geq 0\right\}\);

  2. \(B:= \left\{y\in\mathbb{R}^m\,:\,A^Ty\geq 0,\, b^Ty<0\right\}\).

Demostración. Sean \(A\in\mathbb{R}^{m\times n}\) y \(b\in\mathbb{R}^m\), cualesquiera.

  1. Primera etapa En una primera etapa vamos a probar que los conjuntos \(A\) y \(B\) no pueden ser no vacíos al mismo tiempo. Así, supongamos, por contradicción que no lo son y existen \(x\in\mathbb{R}^n\) tal que

    \[\tag{1}\label{1} Ax=b \quad x\geq 0.\]

    Y, también existe \(y\in\mathbb{R}^m\) tal que

    \[\tag{2}\label{2} A^T y \geq 0 \quad y^Tb <0.\]

    Así, notemos que usando la ecuación (1) como \(Ax=b\)

    \[y^T Ax = y^T (Ax) = y^T b <0\quad\Longrightarrow\quad y^T b <0\]

    Además, se tiene que

    \[y^T Ax = (y^T A)x = (A^T y)^T x \geq 0\quad\Longrightarrow\quad y^T b \geq 0.\]

    nuevamente por las definiciones de los conjuntos. Así, hemos concluido que

    \[y^T b\geq 0 \quad \land \quad y^b <0,\]

    lo cual no es posible y por lo tanto, los conjuntos \(A\) y \(B\) no pueden ser vacíos simultáneamente.

    (Observación: Vamos a probar que \(B\neq\varnothing\) si y solo si \( A\neq\varnothing\), equivalentemente se tiene la negación \(B=\varnothing\) si y solo si \(A\neq\varnothing\).)

  2. Segunda etapa

    1. Supongamos que \(A\) es vacío, vamos a probar que \(B\) es no vacío.

      Para esto, consideremos el siguiente conjunto

      \[C = \text{cono}(a_1,\ldots,a_n) = \left\{\sum_{i=1}^n \alpha_i a_i\,:\, \alpha_i \geq 0\right\},\]

      donde \(\{a_1,\ldots,a_n\}\) es el conjunto de vectores columna de de la matriz \(A\). Equivalentemente, el conjunto \(C\) se puede ver de la siguiente manera:

      \[C = \{ s\in\mathbb{R}^m\,: \, s = A \alpha \, , \, \alpha\in\mathbb{R}^n \}.\]

      (Observación: Este conjunto se denomina el cono convexo y difiere de la combinación convexa pues no se exige que la suma de las constantes de la combinación sea \(1\), i.e, \(\sum_{i=1}^n \alpha_i= 1\).)

      Ahora, notemos que este conjunto es convexo y cerrado.

      En efecto, sean \(a,b\in C\), y \(\lambda\in [0,1]\), notemos que

      \[\begin{aligned} \lambda a + (1-\lambda)b & = \lambda A \alpha_x + (1-\lambda) A \alpha_y\\ & = A \tilde{\alpha_x} + A \tilde{\alpha_y} \in C, \end{aligned}\]

      donde \(\tilde{\alpha_x}= \lambda \alpha_x\geq 0\) y \(\tilde{\alpha_y}= (1-\lambda) \alpha_y\geq 0\), pues \(\lambda \in[0,1]\).

      Vamos que probar que \(C\) es cerrado. Sea \(\left(c_n\right)_{n\in\mathbb{\mathbb{N}}}\subseteq C\), una sucesión convergente a un \(c^*\), vamos a probar que \(c^*\in C\). Para ello, se tiene que

      \[c_k = A\alpha_{c_k} \quad \alpha_{c_k}\in\mathbb{R}^n \,\, \alpha_{c_k}\geq 0.\]

      Luego, se tiene que la sucesión \(\left(c_n\right)_{n\in\mathbb{\mathbb{N}}}\), induce una sucesión \(\left(\alpha_{c_n}\right)_{n\in\mathbb{\mathbb{N}}}\) en \(W:= \left\{\alpha\in\mathbb{R}^n\,:\, \alpha\geq 0\right\}\). Así, como la sucesión es convergente si y solo sí cada una de sus sucesiones componentes converge en \([0,+\infty[\), entonces la sucesión \(\left(\alpha_{c_n}\right)_{n\in\mathbb{\mathbb{N}}}\) converge en \(W\) y más aún, \(\left(c_n\right)_{n\in\mathbb{\mathbb{N}}}\) converge en \(C\). Así como la sucesión fue arbitraria, se sigue que \(C\) es cerrado.

      Nuestro objetivo es encontrar un \(y\in\mathbb{R}^m\), tal que

      \[A^T y \geq 0 \quad y^T b<0.\]

      Para ello, tenemos que \(\{b\}\) es un conjunto compacto pues es cerrado y acotado en \(\mathbb{R}^{m\times 1}\), así por el teorema de Heine-Borel, se tiene que es compacto y más aún es convexo, lo cual se ve fácilmente.

      Además, se tiene que \(\{b\}\) y \(C\) son disjuntos pues por hipótesis \(A\) es vacío.

      De esta manera, por el teorema de Hanh-Banach, segunda forma geométrica, existe un hiperplano de separación \(H = [f=\gamma]\) cerrado que separa estrictamente a los conjuntos \(\{b\}\) y \(C\), es decir, existe \(\gamma\in\mathbb{R}\) tal que

      \[f(b) < \gamma < f(s) \quad \forall s\in C,\]

      equivalentemente se tiene que

      \[\tag{3}\label{3} f(b) < \gamma < f(s) \quad \forall \alpha \in\mathbb{R}^n \, , \, \alpha\geq 0.\]

      Ahora, como el hiperplano \(H\) es cerrado, entonces sabemos que \(f\in(\mathbb{R}^n)^*\), es decir, \(f\) es lineal y continuo de \(\mathbb{R}^n\) en \(\mathbb{R}\). Así, como \(0\in C\) (tomando \(\alpha=0\)), entonces

      \[\tag{4}\label{4} f(b) < 0.\]

      Luego, por el teorema de representación de Riez, existe un \(q\in\mathbb{R}^m\), tal que

      \[f(s) = q^T s \quad \forall s\in \mathbb{R}^m.\]

      De donde, usando lo anterior en (3), se sigue que

      \[q^T b < \gamma < q^T A\alpha \quad \forall \alpha\in\mathbb{R}^n.\]

      De esta manera, en (4) se tiene que

      \[\begin{aligned} q^T b <0. \end{aligned}\]

      Y, por otro lado, tenemos que

      \[\begin{aligned} q^T A\alpha > 0 & \quad\Longrightarrow\quad(A \alpha)^T q >0 \\ & \quad\Longrightarrow\quad \alpha^T A^T q >0 \\ & \quad\Longrightarrow\quad A^T q \geq 0 && \text{Pues }\,\alpha\geq 0. \end{aligned}\]

      Así, se tiene que \(q\in B\) y por lo tanto \(B\) es no vacío, como se quería.

    2. Supongamos que \(B\) es no vacío, vamos a probar que \(A\) es vacío.

      Por contradicción, supongamos que \(A\) no es vacío. Notemos que esto no es posible pues en una primera etapa probamos que los conjuntos \(A\) y \(B\) no pueden ser no vacíos simultáneamente. Así se tiene que \(A\) es vacío, lo que completa esta etapa.

    Notemos que así se ha probado que

    \[B\neq\varnothing\quad\Leftrightarrow\quad A= \varnothing,\]

    es decir, que solo uno de los conjuntos debe ser vacío.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.