Lemme de Farkas

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 $K$ par une application linéaire $A$ (les notations sont précisées ci-dessous) :

$\overline{A(K)} = \{y\in \mathbb{F} : A^*y\in K^+\}^+.$

Lorsque $A (K)$ 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 $K .$ Sous la forme ci-dessus, le lemme de Farkas généralise la relation bien connue d'algèbre linéaire reliant l'image $\mathcal{R}(A)$ d'une application linéaire $A$ entre deux espaces euclidiens et le noyau $\mathcal{N}(A^*)$ de son adjointe $A *$ , à savoir

$\mathcal{R}(A) = \mathcal{N}(A^*)^\perp.$

Certaines versions du lemme sont connues sous le nom de « théorèmes de l'alternative » et s'obtiennent en prenant pour cône $K$ l'orthant positif de $\mathbb{R}^n$ . 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.

Sommaire

1 Historique
2 La version du lemme en géométrie vectorielle
3 La version matricielle du lemme
4 Le lemme de Farkas comme critère d'inconsistance
5 Déduction d'inéquations en géométrie affine
6 Généralisation
7 Notes et références

Historique

Ce lemme a été historiquement 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

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

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

si et seulement si

g est une combinaison linéaire à coefficients positifs ou nuls de f₁, ... , 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 — Soient s₁, ... , s_k des éléments d'un espace vectoriel réel E de dimension finie. L'ensemble des combinaisons linéaires à coefficients positifs ou nuls de s₁, ... , s_k est fermé dans E.

La version matricielle du lemme

B étant une matrice de réels, on note ici B ≥ 0 lorsque tous les coefficients de B sont positifs ou nuls^[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.

Vérification

Pour chaque colonne C_j de A (1 ≤ j ≤ k), notons f_j la forme linéaire définie sur Rⁿ par $y\mapsto (^{\operatorname t}\!C_j)y$ ; notons par ailleurs g la forme linéaire $y\mapsto (^{\operatorname t}\!b)y$ .

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)\geqslant 0,\cdots,f_k(y)\geqslant 0\}$ mais qui ne soit pas dans $\{y\in E\,\mid\, g(y)\geqslant 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)\geqslant 0,\ldots,f_k(y)\geqslant 0\}\subset \{y\in E\,\mid\, g(y)\geqslant 0\}$ c'est la même chose que de dire que l'ensemble $\{y\in E\,\mid\,g(y)<0, f_1(y)\geqslant 0,\ldots,f_k(y)\geqslant 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 — Soient f₁, ... , f_k et h des formes linéaires sur un espace vectoriel réel E de dimension finie. Alors :

$\{y\in E\,\mid\,h(y)> 0,f_1(y)\geqslant 0,f_2(y)\geqslant 0,\ldots,f_k(y)\geqslant 0\}=\varnothing$

si et seulement si

( -h ) est une combinaison linéaire à coefficients positifs ou nuls de f₁, ... , 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 — Soient f₁, ... , f_k des formes affines sur un espace affine réel E de dimension finie. Alors :

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

si et seulement si

(-1) est une combinaison linéaire à coefficients positifs ou nuls de f₁, ... , 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 ≥ 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)\geqslant 0,\ldots,f_k(y)\geqslant 0\}$ vide.

Introduisons un espace vectoriel Ê 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 Ê. Notons $\hat f_j$ le prolongement linéaire de $f j$ (1 ≤ j ≤ k) et $\hat g$ le prolongement de la constante -1, de sorte que E a pour équation $\hat g(y)=-1$ dans Ê. L'hypothèse revient à dire que si un point y de Ê vérifie les conditions $\hat f_1(y)\geqslant 0,\cdots,\hat f_k(y)\geqslant 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)\geqslant 0,\cdots,\hat f_k(y)\geqslant 0\}$ est inclus dans l'ensemble $\{y\in\hat E\,\mid\, \hat g(y)\geqslant 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² où 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 f₁, ... , 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)\geqslant 0,\ldots,f_k(y)\geqslant 0\}$ non vide. Alors :

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

si et seulement si

g est somme d'une combinaison linéaire à coefficients positifs ou nuls de f₁, ... , 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)\geqslant 0,\ldots,f_k(y)\geqslant 0\}\subset \{y\in E\,\mid\, g(y)\geqslant 0\}$ . On note de nouveau Ê 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 forme affine valant constamment 1 sur E et $\hat h$ son extension linéaire à Ê. On vérifie ensuite que :

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

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

si $\hat 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 $\hat h(y)> 0$ , on se ramène au cas précédent par homothétie de rapport strictement positif ;
si $\hat 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 $\hat g$ est lui aussi à valeurs positives ou nulles sur le segment. On conclut alors que $\hat g(y)\geqslant 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.

Généralisation

On trouvera ci-dessous 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é (e.g., 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.

Commençons par rappeler certaines notions qui sont utilisées dans son énoncé. Si $A:\mathbb{E}\to \mathbb{F}$ est une application linéaire entre deux espaces euclidiens $\mathbb{E}$ et $\mathbb{F}$ dont les produits scalaires sont tous les deux notés $\langle\cdot,\cdot\rangle$ , son adjointe est l'application linéaire $A^*:\mathbb{F}\to \mathbb{E}$ définie par la propriété

$\forall\,(x,y)\in\mathbb{E}\times\mathbb{F}:\qquad\langle Ax,y\rangle=\langle x,A^* y\rangle.$

Par ailleurs, une partie $K$ d'un espace vectoriel $\mathbb{E}$ est un cône si $\mathbb{R}_{++}K\subset K$ , ce qui signifie que $t x$ doit appartenir à $K$ chaque fois que $t$ est un réel strictement positif et $x\in K$ . Ensuite, le cône dual (positif) d'une partie non vide $P$ d'un espace euclidien $\mathbb{E}$ est le cône convexe fermé non vide défini par

$P^+:=\{x\in\mathbb{E}:\langle x,y\rangle\geqslant 0$ pour tout $y\in P\}.$

Enfin, on note $\operatorname{adh} P$ ou $\overline{P}$ l'adhérence d'une partie $P$ d'un espace topologique.

Lemme de Farkas généralisé — Soient $\mathbb{E}$ et $\mathbb{F}$ deux espaces euclidiens, $A:\mathbb{E}\to \mathbb{F}$ une application linéaire, $K$ un cône convexe non vide de $\mathbb{E}$ et $L$ un cône convexe fermé non vide de $\mathbb{F}$ . Alors

$\{y\in L : A^*y\in K^+\}^+ = \overline{A(K)+L^+}.$

On ne peut pas se passer de l'adhérence dans le membre de droite de l'identité car le cône convexe $A (K) + L +$ n'est pas nécessairement fermé (même si $K$ est un cône convexe fermé) alors que, en tant que cône dual, le cône du membre de droite est toujours fermé. Signalons toutefois que si $K$ et $L$ sont des orthant positif d'un certain $\mathbb{R}^p$ ), alors $A (K) + L +$ est aussi un cône polyédrique, donc un fermé ; dans ce cas, on peut ôter l'adhérence dans le membre de droite.

Lemme de Farkas généralisé

On retrouve le résultat énoncé au début de cet article lorsque $L=\mathbb{F}$ , puisqu'alors $L + = {0}$ . Dans ce cas, le résultat peut s'interpréter géométriquement comme suit. Le vecteur $b\notin\operatorname{adh}(A(K))$ si et seulement si $b\notin\{y\in \mathbb{F} : A^*y\in K^+\}^+$ , ce qui revient à dire qu'il existe un vecteur $y_0\in\mathbb{F}$ tel que $\langle y_0,b\rangle<0$ et $A^*y_0\in K^+$ (forme compacte de l'expression $\langle y_0,Ax\rangle\geqslant 0$ pour tout $x\in K)$ . Cette propriété exprime donc le fait que l'hyperplan $\{y\in\mathbb{F}:\langle y_0,y\rangle=0\}$ sépare strictement le singleton ${b}$ de l'adhérence du cône convexe $A (K)$ . La démonstration de ce lemme généralisé peut d'ailleurs se faire par séparation stricte de ces deux derniers convexes (Hahn-Banach).

Si $L=\mathbb{F}$ et $A (K)$ est fermé, le lemme de Farkas peut être vu comme donnant des conditions nécessaires et suffisantes pour qu'un système linéaire ait une solution dans le cône convexe $K$ , ce qui s'écrit :

$\exists\,x\in K:\quad Ax=b.$

Il assure en effet que ce système a une solution si et seulement si $b$ est dans le dual du cône convexe fermé $\{y\in \mathbb{F} : A^*y\in K^+\}$ , c'est-à-dire si et seulement si $\langle b,y\rangle\geqslant 0$ pour tout $y\in \mathbb{F}$ tel que $A^*y\in K^+.$ Lorsque $A (K)$ n'est pas fermé, ces dernières conditions sont équivalentes au fait que l'on peut trouver une solution du même système avec une précision aussi bonne que l'on veut, dans le sens suivant

$\forall\,\varepsilon>0,\quad\exists\,x_\varepsilon\in K:\quad \|Ax_\varepsilon-b\|\leqslant\varepsilon.$

Par ailleurs, observons que $\{y\in L : A^*y\in K^+\}=L\cap((A^*)^{-1}(K^+))$ est l'intersection du cône convexe fermé $L$ et de l'image réciproque par l'application linéaire (continue) $A *$ du cône convexe fermé $K +$ ; il s'agit donc d'un cône convexe fermé, si bien qu'il est égal à son bidual. On rappelle également que le cône dual d'un ensemble et de son adhérence sont identiques. Dès lors, dans les conditions énoncées dans le lemme de Farkas généralisé, on a

$(A(K)+L^+)^+ = \{y\in L : A^*y\in K^+\},$

sans que l'on ait besoin ici de prendre d'adhérence. Cette dernière identité se démontre directement, sans théorème de séparation ; mais pour en déduire le lemme de Farkas généralisé il faut utiliser le fait que le bidual d'un cône convexe est égal à son adhérence.

Notes et références

↑ (de) Julius Farkas, Theorie der einfachen Ungleichungen, Journal für die reine und angewandte Mathematik 124 (1902) p. 1-27
↑ Dans un autre contexte, cette même notation désigne la notion, différente, de matrice positive.

L'article, à l'exception de l'introduction, de la section historique et de la section Généralisation, 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.

v · Ensemble convexe Outils et résultats fondamentaux : Enveloppe convexe • Adhérence, intérieur et frontière d'un convexe • Projection sur un convexe fermé • Séparation des convexes • Points remarquables à la frontière d'un convexe • Polytope • Théorème de Krein-Milman • Lemme de Farkas Géométrie combinatoire : Théorème de Carathéodory • Théorème de Radon • Théorème de Helly Géométrie métrique : Courbe de largeur constante • Théorème des quatre sommets Algorithmes de géométrie convexe : Approche polyédrique • Marche de Jarvis • Parcours de Graham • Théorème optimisation/séparation Optimisation linéaire : Optimisation linéaire • Algorithme du simplexe • Génération de colonnes
Interactions géométrie-analyse	Théorème de Hahn-Banach • Jauge
Analyse convexe	Articles principaux : Ensemble convexe • Fonction convexe Outils et résultats fondamentaux : Conditions de Kuhn-Tucker • Inégalité de Jensen Algorithmique : Méthodes de points intérieurs
Utilisations de la convexité	Inégalités de convexité : Inégalité arithmético-géométrique • Inégalité de Hölder Analyse fonctionnelle : Espace localement convexe • Théorème du point fixe de Schauder Localisation de zéros de polynômes : Théorème de Gauss-Lucas Théorie des nombres : Théorème de Minkowski

Portail des mathématiques

Catégories :

Analyse convexe
Optimisation
Lemme de mathématiques

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Lemme de Farkas de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

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… … Wikipédia en Français
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… … Wikipédia en Français
Farkas — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Farkas (ˈfɑrkɑʃ) est un prénom hongrois masculin correspondant au prénom … Wikipédia en Français
Théorèmes de l'alternative — Les théorèmes de l alternative, dont le plus fameux est le lemme de Farkas, concernent tous un système d inéquations linéaires dans un espace vectoriel réel de dimension finie. Il s agit de donner un critère permettant de trancher si le système… … Wikipédia en Français
Theoremes de l'alternative — Théorèmes de l alternative Les théorèmes de l alternative, dont le plus fameux est le lemme de Farkas, concernent tous un système d inéquations linéaires dans un espace vectoriel réel de dimension finie. Il s agit de donner un critère permettant… … Wikipédia en Français
Conditions d'optimalité (dimension finie) — En optimisation mathématique, les conditions d optimalité sont un ensemble d équations, d inéquations (i.e., des inégalités) et d expressions diverses (e.g., la semi définie positivité de matrices sur des cônes) vérifiées par une solution d un… … Wikipédia en Français
Théorème de Helly — dans le plan : si trois quelconques des convexes de la famille se rencontrent alors l intersection de tous ces convexes est non vide. Le théorème de Helly est un résultat combinatoire sur les convexes. Ce résultat a été prouvé en 1913 par… … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Théorème de helly — Le théorème de Helly est un résultat combinatoire sur les convexes. Ce résultat a été prouvé en 1913 par Eduard Helly, et il a été publié par Johann Radon en 1921[1],[2]. Énoncé Théorème … Wikipédia en Français
Liste de lemmes (mathématiques) — Liste de lemmes mathématiques par ordre alphabétique. En mathématiques, un lemme est un énoncé prouvé, mais jugé moins important que ce qu on appelle un théorème, qu il sert généralement à établir au cours d une démonstration. Néanmoins cette… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Lemme de Farkas

Sommaire

Historique

La version du lemme en géométrie vectorielle

La version matricielle du lemme

Le lemme de Farkas comme critère d'inconsistance

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

Généralisation

Notes et références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Lemme de Farkas

Sommaire

Historique

La version du lemme en géométrie vectorielle

La version matricielle du lemme

Le lemme de Farkas comme critère d'inconsistance

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

Généralisation

Notes et références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link