Voici deux autres formes du lemme de Farkas :
Lemme de Farkas - version Ⓑ
Lemme de Farkas - version Ⓒ
Il n'est pas très difficile de montrer que ces deux formes sont équivalentes. On note tout d'abord que (B)-1 est incompatible avec (B)-2. En effet, on a la chaîne suivante :
\[ \underbrace{0=\left(\boldsymbol{y}^\top\boldsymbol{A}\right)}_{=\;0 \text{ par (B)-2} } \]De même, (C)-1 est incompatible avec (C)-2. En effet, on a la chaîne suivante :
\[ \underbrace{0\;\leq\left(\boldsymbol{y}^\top\boldsymbol{A}\right)}_{\geq\;0 \text{ par C-2} } \overset{\geq\; 0 \text{ par C-1}}{\boldsymbol{x}} = \underbrace{\overset{\geq\; 0 \text{ par C-2}}{\boldsymbol{y}^\top}\left(\boldsymbol{A} \boldsymbol{x}\right)\leq \boldsymbol{y}^\top \boldsymbol{b}}_{\text{par C-1}}\overset{\text{par C-2}}{<}0 \]On peut montrer que (B) implique (C). Par (C)-1, on a $\boldsymbol{A} \boldsymbol{x}\leq \boldsymbol{b}$ et $\boldsymbol{x}\geq \boldsymbol{0}.$ La seconde inégalité n'est pas modifiée si on la multiplie par $-1$ et par la matrice identité et que l'on change son signe (i.e. : on remplace $\boldsymbol{x}\geq \boldsymbol{0}$ par $-\boldsymbol{I}\boldsymbol{x}\leq \boldsymbol{0}$). On note qu'ainsi on a l'inégalité matricielle:
\[ \begin{bmatrix} \boldsymbol{A}\\-\boldsymbol{I} \end{bmatrix}\boldsymbol{x}\leq \begin{bmatrix} \boldsymbol{b}\\\boldsymbol{0} \end{bmatrix} \]soit, en notant
\[ \boldsymbol{A}^\prime = \begin{bmatrix} \boldsymbol{A}\\-\boldsymbol{I} \end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{b}^\prime = \begin{bmatrix} \boldsymbol{b}\\\boldsymbol{0} \end{bmatrix} \] \[ \boldsymbol{A}^\prime\boldsymbol{x}\leq \boldsymbol{b}^\prime \]Maintenant, par (C)-2, on a les trois inégalités suivantes $\boldsymbol{y}^\top\boldsymbol{A}\geq \boldsymbol{0}$, $\boldsymbol{y}\geq \boldsymbol{0}$ et $\boldsymbol{y}\boldsymbol{b}< 0$. Introduisons un vecteur de variables d'écart $\boldsymbol{e}\geq \boldsymbol{0}$ de manière à transformer l'inégalité $\boldsymbol{y}^\top\boldsymbol{A}\geq \boldsymbol{0}$ en égalité (i.e. : $\boldsymbol{y}^\top\boldsymbol{A}- \boldsymbol{e}^\top\boldsymbol{I}= \boldsymbol{0}$). On peut aussi réécrire la dernière inégalité ($\boldsymbol{y}^\top\boldsymbol{b}< 0$) sous la forme : $\boldsymbol{y}^\top\boldsymbol{b}- \boldsymbol{e}^\top\boldsymbol{0}< 0$. Le résultat de toutes ces opérations peut être mis sous la forme matricielle suivante :
\[ \begin{bmatrix} \boldsymbol{y}^\top & \boldsymbol{e}^\top \end{bmatrix}\begin{bmatrix} \boldsymbol{A}\\-\boldsymbol{I} \end{bmatrix}=\begin{bmatrix} \boldsymbol{0}^\top&\boldsymbol{0}^\top \end{bmatrix}, \hspace{.25cm} \begin{bmatrix} \boldsymbol{y}^\top & \boldsymbol{e}^\top \end{bmatrix}\geq \begin{bmatrix} \boldsymbol{0}^\top&-\boldsymbol{0}^\top \end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \begin{bmatrix} \boldsymbol{y}^\top & \boldsymbol{e}^\top \end{bmatrix}\begin{bmatrix} \boldsymbol{b}\\\boldsymbol{0} \end{bmatrix}< 0 \]ou, en notant :
\[ \boldsymbol{y}^{\prime\top} = \begin{bmatrix} \boldsymbol{y}^\top & \boldsymbol{e}^\top \end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{b}^\prime = \begin{bmatrix} \boldsymbol{b}\\\boldsymbol{0} \end{bmatrix} \]En résumé (C) peut être réécrit de telle sorte à ce que l'on puisse appliquer (B) en substituant les éléments initiaux par leur version en prime. Ceci montre donc que (B) implique (C). Montrons maintenant que (C) implique (B). Repartons de (B). Dans (B)-1, il n'y a pas de contrainte sur le signe de $\boldsymbol{x}$. On peut réintroduire une contrainte de ce type en notant que toute variable $x_i$ peut s'écrire comme l'écart de deux variables : $x_i = x_{n+1} - x_{n+2}$, $x_{n+1} \geq 0$ et $x_{n+2} \geq 0$. Pour simplifier les notations, on notera : $\boldsymbol{x} = \boldsymbol{r} - \boldsymbol{s}$ avec $\boldsymbol{r}\geq \boldsymbol{0}$ et $\boldsymbol{s}\geq \boldsymbol{0}$. On a donc
\[ \boldsymbol{A}\boldsymbol{x}\leq \boldsymbol{b}\hspace{.25cm}\Longleftrightarrow\hspace{.25cm} \boldsymbol{A}(\boldsymbol{r}-\boldsymbol{s})\leq \boldsymbol{b}, \boldsymbol{r}\geq \boldsymbol{0}, \boldsymbol{s}\geq \boldsymbol{0}\,\,\,\,\,\Longleftrightarrow\,\,\,\,\, \begin{bmatrix} \boldsymbol{A} & - \boldsymbol{A} \end{bmatrix} \begin{bmatrix} \boldsymbol{r}\\\boldsymbol{s} \end{bmatrix}\leq\boldsymbol{b}, \begin{bmatrix} \boldsymbol{r}\\\boldsymbol{s} \end{bmatrix}\geq\boldsymbol{0} \]Dans (B)-2, $\boldsymbol{y}^\top \boldsymbol{A}= 0$ signifie que, simultanément, $\boldsymbol{y}^\top \boldsymbol{A}\geq 0$ et $\boldsymbol{y}^\top \boldsymbol{A}\leq 0$. On a donc
\[ \boldsymbol{y}^\top \boldsymbol{A}= 0, \boldsymbol{y}\geq \boldsymbol{0}, \boldsymbol{y}^\top\boldsymbol{b}<0\hspace{.25cm}\Longleftrightarrow\hspace{.25cm} \boldsymbol{y}^\top \boldsymbol{A}\geq 0,-\boldsymbol{y}^\top \boldsymbol{A}\geq 0, \boldsymbol{y}\geq \boldsymbol{0}, \boldsymbol{y}^\top\boldsymbol{b}<0 \]soit
\[ \boldsymbol{y}^\top\begin{bmatrix} \boldsymbol{A} & - \boldsymbol{A} \end{bmatrix}\geq \boldsymbol{0}, \boldsymbol{y}\geq \boldsymbol{0}, \boldsymbol{y}^\top\boldsymbol{b}<0 \]En notant
\[ \boldsymbol{A}^\prime =\begin{bmatrix} \boldsymbol{A} & - \boldsymbol{A} \end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{x}^\prime=\begin{bmatrix} \boldsymbol{r}\\\boldsymbol{s} \end{bmatrix} \]ce qui permet de réécrire les deux conditions (C) sous la forme :
\[ \begin{array}{cc} \boldsymbol{A}^\prime \boldsymbol{x}^\prime\leq \boldsymbol{b}, \boldsymbol{x}^\prime\geq \boldsymbol{0}&(C)-1^\prime\\\\ \boldsymbol{y}^\top\boldsymbol{A}^\prime\geq \boldsymbol{0, \boldsymbol{y}\geq \boldsymbol{0}, \boldsymbol{y}^\top\boldsymbol{b}<0}&(C)-2^\prime \end{array} \]Appliquant (B), on obtient exactement les nouvelles conditions (C). Il y a donc équivalence entre les formulations. On laisse la(e) lectrice(lecteur) montrer par elle(lui)-même l'équivalence de (A) avec (B) ou (C).