Farkas Lema prueba

Question

Estoy tratando de probar la Farkas Lema utilizando la transformada de Fourier-Motzkin eliminación algoritmo. De La Wikipedia:

Dejar que Un ser $m \times n$ matriz y $b$ $m$- dimensiones del vector. Entonces, exactamente una de las dos siguientes afirmaciones es verdadera:

1. Existe una $x \in \Bbb R^n$ tal que $Ax = b$$x \ge 0$.
2. Existe una $y \in \Bbb R^m$ tal que $A^Ty \ge 0$$b^Ty < 0$.

---

La primera dirección es bastante fácil. Supongo que es un vector $y$ y he encontrado una contradicción. Para la otra dirección, he usado la de fourier-motzkin eliminación para reducir el número de variables. Supongo que $Ax \le b$ y tengo que hacer un paso del algoritmo. Puedo crear un nuevo sistema de $A'x' \le b'$. Sé que existe una no-negativo de la matriz $M$ que es una combinación lineal del nuevo sistema a la original. He seguido la dirección de repetir el algoritmo de $n$ veces para eliminar todas las variables y crear el sistema: $0 \le b''$.

Ahora en el fin de este sistema a no ser factible, debe ser que: $b''<0$. Así que puedo suponer que existen vectores $y''$ tal que $y''A''=0$ también $y''b''<0$ porque $b'<0$$y\ge 0$. Ahora puedo demostrar que también existe un vector $y$ para el sistema original. Pero la repetición de $n$ pasos me parece un poco arbitrario. Si acabo de hacer un paso y crear el sistema de $A'x'\le b'$ cómo puedo usar no es factible?

Answer 1

Como nota, $1\rightarrow \bar 2$ es muy sencillo:

$$ \begin{align} Ax &= b \\ x'A' &= b' \\ x'A'y &= b'y \\ \end{align} $$

Desde $x\geq0$, es imposible tener simultáneamente $A'y\geq 0$$b'y < 0$.

Para $\bar 1\rightarrow 2$, la primera nota que $Ax = b, x\geq 0$ (el sistema que es inviable debido a $\bar 1$) es equivalente a $Dx \leq d$, donde se definen

$$ D = \left( \begin{array}{c} A \\ -A \\ -I \end{array} \right), d = \left( \begin{array}{c} b \\ -b \\ 0 \end{array} \right). $$

Ahora podemos aplicar la transformada de Fourier-Motzkin Eliminación (FME) en el sistema de $Dx\leq d$, la eliminación de todas las variables de $1, 2, \ldots, n$ en orden. Definir $U^i$ a ser la matriz se utiliza para eliminar la variable $i$ a partir del sistema de ecuaciones; yo la uso $U^i\geq 0$ para indicar que cada entrada en $U^i$ es no negativo. De FME tenemos $U^nU^{n-1}\ldots U^1D = 0$. La definición de $U = U^nU^{n-1}\ldots U^1$ tenemos $UD = 0$; tenga en cuenta que de $U^1\geq 0, U^2\geq 0, \ldots, U^n\geq 0$ también contamos $U\geq 0$.

Debido a $Dx\leq d$ es factible, debe haber alguna fila $u'\geq 0$ $U$ tal que $u'D = 0'$$u'd < 0$. Dejando $p\geq 0$ ser el primero $m$ elementos de $u$, $q\geq 0$ ser la próxima $m$ elementos de $u$, e $r\geq 0$ ser el último, $n$ elementos de $u$, tenemos:

$$ \begin{align} u'D &= 0' \\ \left( \begin{array}{ccc} p' & q' & r' \end{array} \right) \left( \begin{array}{c} A \\ -A \\ -I \end{array} \right) &= 0' \\ (p-q)'A &= r' \\ (p-q)'A &\geq 0' \\ A'(p-q) &\geq 0 \end{align} $$

y

$$ \begin{align} u'd &< 0 \\ \left( \begin{array}{ccc} p' & q' & r' \end{array} \right) \left( \begin{array}{c} b \\ -b \\ 0 \end{array} \right) &< 0 \\ (p-q)'b &< 0 \\ b'(p-q) &< 0 \end{align} $$

Mediante el establecimiento $y = p-q$, hemos utilizado la OMF para construir un vector $y\in\mathbb{R}^m$ tal que $A'y \geq 0$$b'y < 0$.