Lemme de Farkas

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le lemme de Farkas est un résultat d'analyse convexe (une branche des mathématiques) qui s'exprime et s'interprète de multiples manières. Sous une forme assez générale, il donne une expression duale de l'adhérence de l'image d'un cône convexe par une application linéaire  :

est l'adjointe de et désigne le cône dual d'une partie . Lorsque est fermé, on obtient ainsi des conditions nécessaires et suffisantes pour qu'un système d'équations linéaires (ou affines) ait une solution dans . Sous la forme ci-dessus, le lemme de Farkas généralise la relation bien connue d'algèbre linéaire reliant l'image d'une application linéaire entre deux espaces euclidiens et le noyau de , à savoir

Certaines versions du lemme sont connues sous le nom de « théorèmes de l'alternative » et s'obtiennent en prenant pour cône l'orthant positif de . Ceux-ci expriment l'équivalence (ou l'incompatibilité) entre la satisfaction de différents systèmes d'inéquations linéaires (ou affines).

Du fait de sa généralité, le lemme de Farkas intervient dans de nombreux domaines, lorsque des questions de dualité sont en jeu. Citons l'optimisation non linéaire dans laquelle il permet d'obtenir une expression analytique de l'optimalité (les conditions de Karush, Kuhn et Tucker) à partir d'une expression géométrique de celle-ci, et la théorie des jeux.

Historique[modifier | modifier le code]

Ce lemme a été démontré pour la première fois par Gyula Farkas (en) en 1902 avec une formulation différente[1]. La formulation matricielle est due à Albert William Tucker dans les années 1950.

La version du lemme en géométrie vectorielle[modifier | modifier le code]

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 — Soient f1, ... , fk et g des formes linéaires sur un espace vectoriel E de dimension finie. Alors :

si et seulement si

g appartient à l'espace vectoriel formé des combinaisons linéaires de f1, ... , fk.

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 — Soient f1, ... , fk et g des formes linéaires sur un espace vectoriel réel E de dimension finie. Alors :

si et seulement si

g est une combinaison linéaire à coefficients positifs ou nuls de f1, ... , fk.

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

Lemme de Farkas, version topologique — Soient s1, ... , sk des éléments d'un espace vectoriel réel E de dimension finie. L'ensemble des combinaisons linéaires à coefficients positifs ou nuls de s1, ... , sk est fermé dans E.

La version matricielle du lemme[modifier | modifier le code]

B étant une matrice de réels et l'on note B ≥ 0 lorsque c'est une matrice à coefficients positifs[2]. La notation tB désigne la matrice transposée de B.

La version matricielle du lemme est la suivante :

Lemme de Farkas, version matricielle — Soient 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 ≥ 0 ;
  • le système tA y ≥ 0 pour y vecteur-colonne à n entrées vérifiant par ailleurs tb y < 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.

Le lemme de Farkas comme critère d'existence de solutions[modifier | modifier le code]

On dira qu'un système d'inéquations est contradictoire lorsqu'il n'a aucune solution[3]. Si l'on revient à la version du théorème pour les équations linéaires, dire que c'est la même chose que de dire que l'ensemble est vide : c'est un énoncé de contradiction. En notant h = –g, on a donc la variante suivante :

Lemme de Farkas, critère vectoriel de contradiction — Soient f1, ... , fk et h des formes linéaires sur un espace vectoriel réel E de dimension finie. Alors :

si et seulement si

( –h ) est une combinaison linéaire à coefficients positifs ou nuls de f1, ... , fk.

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

Lemme de Farkas, critère affine de contradiction — Soient f1, ... , fk des formes affines sur un espace affine réel E de dimension finie. Alors :

si et seulement si

(–1) est une combinaison linéaire à coefficients positifs ou nuls de f1, ... , fk.

On voit de nouveau là très nettement l'idée sous-jacente à tous ces énoncés : un système inconsistant (au sens du calcul propositionnel) implique l'inéquation absurde - 1 ≥ 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éduction d'inéquations en géométrie affine[modifier | modifier le code]

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 R2 où l'on note (u, v) le point courant, soit le système formé des deux inéquations : u – 1 ≥ 0 et –u ≥ 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 ≥ 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é » — Soient f1, ... , fk et g des formes affines sur un espace vectoriel affine de dimension finie . On suppose l'ensemble non vide. Alors :

si et seulement si

g est somme d'une combinaison linéaire à coefficients positifs ou nuls de f1, ... , fk et d'une constante positive ou nulle.

Généralisation[modifier | modifier le code]

On trouvera dans l'article détaillé une version généralisée du lemme de Farkas, qui est utilisée en optimisation non linéaire pour obtenir une expression analytique de l'optimalité (par exemple, les conditions de Karush, Kuhn et Tucker) à partir d'une expression géométrique de celle-ci. Les résultats précédents peuvent se voir comme des cas particuliers de ce résultat.

Notes et références[modifier | modifier le code]

  1. (de) Julius Farkas, « Theorie der einfachen Ungleichungen », Journal für die reine und angewandte Mathematik, vol. 124,‎ , p. 1-27 (lire en ligne).
  2. Dans un autre contexte, cette même notation désigne la notion, différente, de matrice autoadjointe positive.
  3. Avec le vocabulaire de la logique, on dirait inconsistant.

L'article, à l'exception de l'introduction, de la section historique et de la section Généralisation, est une adaptation assez distanciée de (en) Jean-Baptiste Hiriart-Urruty et Claude Lemaréchal, Fundamentals of Convex Analysis, Berlin, Springer, coll. « Grundlehren Text Editions », (ISBN 978-3-540-42205-1, lire en ligne), p. 58-62, à la lumière de l'entrée du blog de Terence Tao du 30 novembre 2007, disponible en ligne.