Lemme De Farkas

Lemme de Farkas

Le lemme de Farkas est un résultat de géométrie convexe essentiel en programmation linéaire où il fonde la théorie de la dualité pour les programmes linéaires, ainsi qu'en théorie des jeux. Il intervient dans la preuve du théorème de Karush-Kuhn-Tucker en programmation non linéaire.

Il affirme, avec quelques précautions techniques nécessaires, qu'étant donnée une famille d'inéquations linéaires (ou affines) dans un espace vectoriel réel de dimension finie, il n'y a pas d'autres conséquences à en déduire que celles qui se déduisent de façon évidente.

On peut donner plusieurs versions du lemme de Farkas, toutes essentiellement équivalentes les unes aux autres.

Ce lemme est un des « théorèmes de l'alternative », qui fournissent pour un système d'inéquations linéaires une condition nécessaire et suffisante d'existence de solution, qui peut s'exprimer comme inexistence de solutions pour un autre problème de forme voisine.

Historique

Ce lemme a été historiquement démontré pour la première fois par Gyula Farkas en 1902 (Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik 124, p1-27) avec une formulation différente. La formulation matricielle est due à Albert William Tucker dans les années 1950.

La version du lemme en géométrie vectorielle

Avant de donner l'énoncé du lemme de Farkas, commençons par rappeler un résultat sur les équations linéaires, suffisamment simple pour ne pas bénéficier d'une dénomination particulière, et dont le lemme de Farkas est la généralisation aux inégalités.

Proposition — Soit $f_1,\ldots,f_k$ et g des formes linéaires sur un espace vectoriel de dimension finie E. Alors :

$\{y\in E\,\mid\,f_1(y)=\cdots=f_k(y)=0\}\subset \{y\in E\,\mid\, g(y)=0\}$

si et seulement si

g appartient à l'espace vectoriel formé des combinaisons linéaires de $(f_1,\ldots,f_k)$.

Dit autrement : étant donné un sous-espace vectoriel de E décrit par une liste d'équations cartésiennes, toute autre équation valable sur ce sous-espace s'obtient en combinant de façon immédiate les équations initialement fournies.

Le lemme de Farkas est le résultat analogue pour des systèmes d'inéquations :

Lemme de Farkas, version vectorielle — Soit $f_1,\ldots,f_k$ et g des formes linéaires sur un espace vectoriel réel de dimension finie E. Alors :

$\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}\subset \{y\in E\,\mid\, g(y)\geq 0\}$

si et seulement si

g appartient à l'ensemble des combinaisons linéaires à coefficients positifs ou nuls de $(f_1,\ldots,f_k)$.

Une des preuves passe par l'étape suivante cruciale, qui est aussi parfois appelée lemme de Farkas :

Lemme de Farkas, version topologique — Soit $s_1,\ldots,s_k$ des éléments d'un espace vectoriel réel de dimension finie E. L'ensemble des combinaisons linéaires à coefficients positifs ou nuls de $(s_1,\ldots,s_k)$ est fermé dans E.

La version matricielle du lemme

On rappelle que B étant une matrice de réels, on note $B\geq 0$ lorsque tous les coefficients de B sont positifs ou nuls. La notation B^T désigne la transposée de B.

La version matricielle du lemme est la suivante :

Lemme de Farkas, version matricielle — Soit A une matrice de réels de taille (n,k) et b un vecteur-colonne avec n entrées, alors un et un seul des systèmes linéaires suivants a une solution :

• le système $Ax = b\,$ pour x vecteur-colonne à k entrées vérifiant par ailleurs $x \geq 0$ ;

• ou le système $A^Ty \geq 0$ pour $y\,$ vecteur-colonne à n entrées vérifiant par ailleurs $b^Ty < 0\,$.

La vérification est sans difficulté aucune, une fois qu'on a passé l'obstacle de raccrocher les matrices de cet énoncé aux objets géométriques de l'énoncé précédent.

Vérification

Pour chaque colonne C_j de A ($1\leq j \leq k$), notons f_j la forme linéaire définie sur $\R^n$ par $y\mapsto C_j^T y$ ; notons par ailleurs g la forme linéaire $y\mapsto b^Ty$.

L'existence d'une solution pour la première branche de l'alternative, c'est l'existence d'un k-uplet $(x_1,\ldots,x_k)$ de nombres positifs ou nuls tels que $x_1C_1+\cdots+x_kC_k=b$, autrement dit c'est la possibilité d'écrire g comme combinaison linéaire à coefficients positifs des f_j.

L'existence d'une solution pour la deuxième branche de l'alternative, c'est l'existence d'un y qui soit dans $\{y\in E\,\mid\,f_1(y)\geq 0,\cdots,f_k(y)\geq 0\}$ mais qui ne soit pas dans $\{y\in E\,\mid\, g(y)\geq 0\}$.

L'équivalence annoncée par le théorème de Farkas garantit donc précisément qu'un et un seul des deux systèmes a une solution.

 

Le lemme de Farkas comme critère d'inconsistance

On dira qu'un système d'inéquations est inconsistant lorsqu'il n'a aucune solution. Si on revient à la version du théorème pour les équations linéaires, dire que $\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}\subset \{y\in E\,\mid\, g(y)\geq 0\}$ c'est la même chose que de dire que l'ensemble $\{y\in E\,\mid\,g(y)<0, f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}$ est vide : c'est un énoncé d'inconsistance. En notant h=-g, on a donc la variante suivante :

Lemme de Farkas, critère vectoriel d'inconsistance — Soit $f_1,\ldots,f_k$ et h des formes linéaires sur un espace vectoriel réel de dimension finie E. Alors :

$\{y\in E\,\mid\,h(y)> 0,f_1(y)\geq 0,f_2(y)\geq0,\ldots,f_k(y)\geq 0\}=\emptyset$

si et seulement si

− h appartient à l'ensemble des combinaisons linéaires à coefficients positifs ou nuls de $(f_1,\ldots,f_k)$.

Par ce critère vectoriel d'inconsistance, on obtient facilement un critère d'inconsistance pour les systèmes affines directement apparenté, et d'aspect un peu plus simple :

Lemme de Farkas, critère affine d'inconsistance — Soit $f_1,\ldots,f_k$ des formes affines sur un espace affine réel de dimension finie E.

Alors :

$\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}=\emptyset$

si et seulement si

− 1 appartient à l'ensemble des combinaisons linéaires à coefficients positifs ou nuls de $(f_1,\ldots,f_k)$.

On voit de nouveau là très nettement l'idée sous-jacente à tous ces énoncés, appliquée dans le cas de l'inconsistance : un système inconsistant implique (au sens du calcu propositionnel) l'inéquation absurde $-1\geq 0$ ; le lemme de Farkas assure dès lors qu'elle peut en être déduite non seulement par des raisonnements plus ou moins compliqués mais aussi tout simplement par combinaisons des équations du système.

Démonstration

L'implication montante est évidente, montrons l'autre. On suppose donc $\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}$ vide.

Introduisons un espace vectoriel $\hat E$ dans lequel E est un sous-espace affine de codimension 1 ne passant pas par l'origine. Toute forme affine sur E se prolonge d'une façon unique en une forme linéaire sur $\hat E$. Notons $\hat f_j$ le prolongement linéaire de f_j ($1\leq j \leq k$) et $\hat g$ le prolongement de la constante − 1, de sorte que E a pour équation $\hat g(y)=-1$ dans $\hat E$.

L'hypothèse revient à dire que si un point y de $\hat E$ vérifie les conditions $\hat f_1(y)\geq 0,\cdots,\hat f_k(y)\geq 0$, il ne vérifie pas la condition $\hat g(y)=-1$. En jouant avec les homothéties de rapport strictement positif, il est immédiat qu'il ne peut pas non plus vérifier $\hat g(y)=-c$ pour un autre niveau strictement négatif. En d'autres termes l'ensemble $\{y\in\hat E\,\mid\,\hat f_1(y)\geq 0,\cdots,\hat f_k(y)\geq 0\}$ est inclus dans l'ensemble $\{y\in\hat E\,\mid\, \hat g(y)\geq 0\}$. On applique alors Farkas et on en déduit que $\hat g$ est une combinaison linéaire à coefficients positifs des $\hat f_j$. Il n'y a plus qu'à restreindre à E la relation obtenue.

 

Déduction d'inéquations en géométrie affine

La simple reproduction du résultat écrit plus haut en géométrie vectorielle serait inexacte en géométrie affine. L'énoncé est en effet faux pour les systèmes d'inéquations inconsistants. Donnons tout de suite un exemple : dans $\R^2$ où on note (u,v) le point courant, soit le système formé des deux inéquations : $u -1 \geq 0$ et $-u\geq 0$. Ce système est inconsistant, faux en tout point, et implique donc (au sens précis de "implique" en calcul propositionnel) n'importe quelle inéquation, par exemple l'inéquation $v-3\geq 0$. Pourtant il n'est bien sûr pas question de produire celle-ci par des manipulations algébriques simples à partir du système initial.

Un énoncé général nécessite ainsi une hypothèse supplémentaire de consistance du système.

« Lemme de Farkas généralisé » — Soit $f_1,\ldots,f_k$ et g des formes affines sur un espace vectoriel affine de dimension finie E. On suppose l'ensemble $\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}$ non vide. Alors :

$\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}\subset \{y\in E\,\mid\, g(y)\geq 0\}$

si et seulement si

g est somme d'une combinaison linéaire à coefficients positifs ou nuls de $(f_1,\ldots,f_k)$ et d'une constante positive ou nulle.

Démonstration

Comme dans la démonstration précédente l'implication montante est évidente. On montre l'autre, en supposant tout d'abord que $\{y\in E\,\mid\,f_1(y)\geq 0,\ldots,f_k(y)\geq 0\}\subset \{y\in E\,\mid\, g(y)\geq 0\}$. On note de nouveau $\hat E$ un espace vectoriel dont E est un sous-espace affine de codimension 1 ne passant pas par l'origine, $\hat f_j$ l'extension linéaire de f_j à cet espace, et naturellement $\hat g$ l'extension linéaire de g à cet espace. On note cette fois h la constante valant 1 sur E et $\hat h$ son extension à $\hat E$.

On vérifie ensuite que :

$\{y\in \hat E\,\mid\,\hat f_1(y)\geq 0,\ldots,\hat f_k(y)\geq 0, \hat h(y)\geq 0\}\subset \{y\in E\,\mid\, \hat g(y)\geq 0\}$ :

pour un point y de l'ensemble de gauche, on discute selon la valeur de h(y) qui est supposé positif ou nul :

• si h(y) = 1, c'est qu'on est dans E et l'appartenance à l'ensemble de droite est assurée par l'hypothèse ;
• plus généralement, si h(y) > 0, on se ramène au cas précédent par homothétie de rapport strictement positif  ;
• si h(y) = 0 on a besoin de l'hypothèse de consistance du système initial. On prend un point auxiliaire $z\in E$ vérifiant ce système, et on se dirige de z vers y le long du segment [z,y[ : tout au long du voyage, les $\hat f_j$ gardent toutes des valeurs positives ou nulles tandis que $\hat h$ reste à valeurs strictement positives ; le cas précédent assure donc que g est lui aussi à valeurs positives ou nulles sur le segment. On conclut alors que $g(y)\geq 0$ par passage à la limite.

Il ne reste plus qu'à appliquer le lemme de Farkas dans sa version vectorielle pour conclure que $\hat g$ est une combinaison linéaire à coefficients positifs des $\hat f_j$ et de $\hat h$ ; on termine en restreignant cette conclusion à E.

 

Références

L'article, à l'exception de la section historique, est une adaptation assez distanciée des pages 58-62 de Fundamentals of convex analysis, Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, coll. « Grundlehren Text Editions », Springer, 2001 (ISBN 3540422056), à la lumière de l'entrée du blog de Terence Tao du 30 novembre 2007, disponible en ligne.

Littérature

• Julius Farkas. "Über die Theorie der Einfachen Ungleichungen". Journal für die Reine und Angewandte Mathematik 124. p1-27

Ce document provient de « Lemme de Farkas ».