Lemma di Farkas §

Il sistema:

$$Ax=b,x\ge 0$$

ammette soluzione se e solo se il sistema

$$y^{T}A\ge 0,y^{T}b<0$$

è inammissibile.

Dim §

Riscriviamo il sistema di partenza per applicare il Teorema di Gale.

$$\{\begin{array}{l}Ax=b\\ x\ge 0\end{array}⟺\{\begin{array}{l}Ax\le b\\ -Ax\le -b\\ -x\le 0\end{array}$$

Combiniamo tutto in una matrice ed usiamo Gale:

$$y^T\left(\begin{array}{c}A\\ -A\\ -I\end{array}\right)=0,y^T\left(\begin{array}{c}b\\ -b\\ 0\end{array}\right)<0,y\ge 0$$

scriviamo il vettore $y^T=(u^T,v^T,w^T)$, analizziamoli separatamente

$$u^{T}A-v^{T}A-w=0,u^{T}b-v^{T}b<0,u,v,w\ge 0$$

introduciamo il vettore $z:=u-v$, e notando che $w\ge 0$ otteniamo:

$$z^{T}A\ge 0,z^{T}b<0$$

le restrizioni sul segno sono sparite, ecco dimstrato il lemma di Farkas. $\square$

Corollario §

In maniera praticamente analoga si dimostra il seguente corollario, che serve per ottenere le Condizioni di ottimalità Duali KKT a partire dalle condizioni di ottimalità vincolata primali. Il Sistema

$$B\lambda +C\mu =g,\lambda \ge 0$$

ammette soluzioni se e solo se il sistema

$$\{\begin{array}{l}{B}^{T}d\le 0\\ C^{T}d=0\\ g^{T}d>0\end{array}$$

non ammette soluzioni.

Dim §

Riscriviamo il primo sistema ed applichiamo Gale:

$$\left(\begin{array}{c}BC\\ -B-C\\ -I0\end{array}\right)\left(\begin{array}{c}\lambda \\ \mu \end{array}\right)\le \left(\begin{array}{c}g\\ -g\\ 0\end{array}\right)$$

si ha il sistema opposto:

$$y^T\left(\begin{array}{c}BC\\ -B-C\\ -I0\end{array}\right)=0,y^T\left(\begin{array}{c}g\\ -g\\ 0\end{array}\right)<0$$

riscriviamo il vettore $y^T=(u^T,v^T,w^T)$

$$u^{T}B-v^{T}B-w^T=0,u^{T}C-v^{T}C=0,u^{T}g-v^{T}g<0$$

introducendo il vettore $d=u-v$, che non ha più restrizioni di segno ed eliminando il vettore positivo $w$ otteniamo:

$$\{\begin{array}{l}{d}^{T}B\ge 0\\ d^{T}C=0\\ d^{T}g<0\end{array}$$

moltiplicando per $-1$, e passando alle trasposte ottengo il secondo sistema della tesi. $\square$