Lemme de Farkas - Farkas' lemma

Le lemme de Farkas est un théorème de résolvabilité pour un système fini d' inéquations linéaires en mathématiques. Il a été prouvé à l'origine par le mathématicien hongrois Gyula Farkas . Le lemme de Farkas est le résultat clé qui sous-tend la dualité de la programmation linéaire et a joué un rôle central dans le développement de l'optimisation mathématique (ou programmation mathématique ). Il est utilisé entre autres dans la preuve du théorème de Karush-Kuhn-Tucker en programmation non linéaire . Remarquablement, dans le domaine des fondements de la théorie quantique, le lemme sous-tend également l'ensemble complet des inégalités de Bell sous la forme de conditions nécessaires et suffisantes pour l'existence d'une théorie des variables cachées locale , étant donné les données de tout ensemble spécifique de mesures.

Les généralisations du lemme de Farkas concernent le théorème de résolvabilité pour les inégalités convexes, c'est-à-dire le système infini d'inéquations linéaires. Le lemme de Farkas appartient à une classe d'énoncés appelés « théorèmes de l'alternative » : un théorème énonçant qu'exactement l'un des deux systèmes a une solution.

Énoncé du lemme

Il existe un certain nombre de formulations légèrement différentes (mais équivalentes) du lemme dans la littérature. Celui donné ici est dû à Gale, Kuhn et Tucker (1951).

Ici, la notation signifie que toutes les composantes du vecteur sont non négatives. ${\displaystyle \mathbf {x} \geq 0}$${\displaystyle \mathbf {x} }$

Exemple

Soit m , n = 2, , et . Le lemme dit qu'exactement une des deux affirmations suivantes doit être vraie (selon b ₁ et b ₂ ) : ${\displaystyle \mathbf {A} ={\begin{bmatrix}6&4\\3&0\end{bmatrix}}}$${\displaystyle \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}}$

1. Il existe x ₁ 0, x ₂ ≥ 0 tels que 6 x ₁ + 4 x ₂ = b ₁ et 3 x ₁ = b ₂ , ou
2. Il existe y ₁ , y ₂ tels que 6 y ₁ + 3 y ₂ 0, 4 y ₁ ≥ 0, et b ₁ y ₁ + b ₂ y ₂ < 0.

Voici une preuve du lemme dans ce cas particulier :

• Si b ₂ ≥ 0 et b ₁ − 2 b ₂ ≥ 0, alors l'option 1 est vraie, puisque la solution des équations linéaires est x ₁ = b ₂ /3 et x ₂ = ( b ₁ -2 b ₂ ) / 4 L'option 2 est fausse, puisque b ₁ y ₁ + b ₂ y ₂ ≥ b ₂ (2 y ₁ + y ₂ ) = b ₂ (6 y ₁ + 3 y ₂ ) / 3, donc si le membre de droite est positif, le côté gauche doit être positif aussi.
• Sinon, l'option 1 est fausse, puisque l'unique solution des équations linéaires n'est pas faiblement positive. Mais dans ce cas, l'option 2 est vraie :
  • Si b ₂ < 0, alors nous pouvons prendre par exemple y ₁ = 0 et y ₂ = 1.
  • Si b ₁ − 2 b ₂ < 0, alors, pour un certain nombre B > 0, b ₁ = 2 b ₂ − B, donc : b ₁ y ₁ + b ₂ y ₂ = 2 b ₂ y ₁ + b ₂ y ₂ - b y ₁ = b ₂ (6 y ₁ + 3 y ₂ ) / 3 - b y ₁ . Ainsi on peut prendre, par exemple, y ₁ = 1, y ₂ = -2.

Interprétation géométrique

Considérons le cône convexe fermé enjambé par les colonnes de ; C'est, ${\displaystyle C(\mathbf {A} )}$${\displaystyle \mathbf {A} }$

${\displaystyle C(\mathbf {A} )=\{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geq 0\}.}$

Observez que c'est l'ensemble des vecteurs pour lesquels la première assertion de l'énoncé du lemme de Farkas est vraie. D'autre part, le vecteur dans la deuxième assertion est orthogonal à un hyperplan qui sépare et . Le lemme découle de l'observation qui appartient à si et seulement s'il n'y a pas d'hyperplan qui le sépare de . ${\displaystyle C(\mathbf {A} )}$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {b} }$${\displaystyle C(\mathbf {A} )}$${\displaystyle \mathbf {b} }$${\displaystyle C(\mathbf {A} )}$${\displaystyle C(\mathbf {A} )}$

Plus précisément, notons les colonnes de . En ce qui concerne ces vecteurs, le lemme de Farkas énonce qu'exactement l'une des deux affirmations suivantes est vraie : ${\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}\in \mathbb {R} ^{m}}$${\displaystyle \mathbf {A} }$

1. Il existe des coefficients non négatifs tels que .${\displaystyle x_{1},\dots ,x_{n}\in \mathbb {R} }$${\displaystyle \mathbf {b} =x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}}$
2. Il existe un vecteur tel que pour , et .${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$${\displaystyle \mathbf {a} _{i}^{\mathsf {T}}\mathbf {y} \geq 0}$${\displaystyle i=1,\dots ,n}$${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} <0}$

Les sommes à coefficients non négatifs forment le cône recouvert par les colonnes de . Par conséquent, la première instruction indique qui appartient à . ${\displaystyle x_{1}\mathbf {a} _{1}+\dots +x_{n}\mathbf {a} _{n}}$${\displaystyle x_{1},\dots ,x_{n}}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {b} }$${\displaystyle C(\mathbf {A} )}$

La deuxième déclaration dit qu'il existe un vecteur tel que l'angle de avec les vecteurs est au plus de 90°, tandis que l'angle de avec le vecteur est supérieur à 90°. L'hyperplan normal à ce vecteur a les vecteurs d'un côté et le vecteur de l'autre. Par conséquent, cet hyperplan sépare le cône couvert par du vecteur . ${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {a} _{i}}$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {a} _{i}}$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {a} _{1},\dots ,\mathbf {a} _{n}}$${\displaystyle \mathbf {b} }$

Par exemple, soit n , m = 2, a ₁ = (1, 0) ^T , et a ₂ = (1, 1) ^T . Le cône convexe couvert par un ₁ et un ₂ peut être vu comme une tranche en forme de coin du premier quadrant dans le plan xy . Maintenant, supposons que b  = (0, 1). Certes, b n'est pas dans le cône convexe a ₁ x ₁ + a ₂ x ₂ . Il doit donc exister un hyperplan séparateur. Soit y  = (1, −1) ^T . Nous pouvons voir que a ₁ · y = 1, a ₂ · y = 0, et b · y = -1. Ainsi, l'hyperplan de normale y sépare bien le cône convexe a ₁ x ₁ + a ₂ x ₂ de b .

Interprétation logique

Une version particulièrement suggestive et facile à retenir est la suivante : si un ensemble d'inéquations n'a pas de solution, alors une contradiction peut en être produite par combinaison linéaire avec des coefficients non négatifs. Dans les formules: si ≤ est alors impossible à résoudre , , ≥ a une solution. Notez que c'est une combinaison des membres de gauche, une combinaison du membre de droite des inégalités. Puisque la combinaison positive produit un vecteur nul à gauche et un -1 à droite, la contradiction est apparente. ${\displaystyle Hache}$${\style d'affichage b}$${\displaystyle y^{\mathsf {T}}A=0}$${\displaystyle y^{\mathsf {T}}b=-1}$${\style d'affichage y}$${\style d'affichage 0}$${\displaystyle y^{\mathsf {T}}A}$${\displaystyle y^{\mathsf {T}}b}$

Ainsi, le lemme de Farkas peut être considérée comme un théorème de complétude logique : ≤ est un ensemble de « axiomes », les combinaisons linéaires sont les « règles de dérivation », et le lemme dit que, si l'ensemble des axiomes est incompatible, il peut être réfuté en utilisant les règles de dérivation. ${\displaystyle Hache}$${\style d'affichage b}$

Variantes

Le Farkas Lemma a plusieurs variantes avec des contraintes de signes différentes (la première est la version originale) :

• Soit le système a une solution avec , soit le système a une solution avec .${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {x} \geq 0}$${\displaystyle \mathbf {A} ^{\mathsf {T}}\mathbf {y} \geq 0}$${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} <0}$
• Soit le système a une solution avec , soit le système a une solution avec et .${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$${\displaystyle \mathbf {x} \geq 0}$${\displaystyle \mathbf {A} ^{\mathsf {T}}\mathbf {y} \geq 0}$${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} <0}$${\displaystyle \mathbf {y} \geq 0}$
• Soit le système a une solution avec , soit le système a une solution avec et .${\displaystyle \mathbf {Ax} \leq \mathbf {b} }$${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$${\displaystyle \mathbf {A} ^{\mathsf {T}}\mathbf {y} =0}$${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} <0}$${\displaystyle \mathbf {y} \geq 0}$
• Soit le système a une solution avec , soit le système a une solution avec .${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$${\displaystyle \mathbf {A} ^{\mathsf {T}}\mathbf {y} =0}$${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} \neq 0}$

Cette dernière variante est mentionnée par souci d'exhaustivité ; ce n'est pas réellement un « lemme de Farkas » puisqu'il ne contient que des égalités. Sa démonstration est un exercice d'algèbre linéaire .

Généralisations

Le lemme de Farkas généralisé peut être interprété géométriquement comme suit : soit un vecteur est dans un cône convexe fermé donné , soit il existe un hyperplan séparant le vecteur du cône ; il n'y a pas d'autres possibilités. La condition de fermeture est nécessaire, voir Théorème de séparation I dans Théorème de séparation hyperplan . Pour le lemme original de Farkas, est l'orthant non négatif , d'où la condition de fermeture se vérifie automatiquement. En effet, pour un cône convexe polyédrique, c'est-à-dire qu'il existe un tel que , la condition de fermeture est vérifiée automatiquement. Dans l'optimisation convexe , divers types de qualification de contraintes, par exemple la condition de Slater , sont responsables de la fermeture du cône convexe sous-jacent . ${\displaystyle \mathbf {S} }$${\displaystyle \mathbb {R} _{+}^{n}}$${\displaystyle \mathbf {B} \in \mathbb {R} ^{n\times k}}$${\displaystyle \mathbf {S} =\{\mathbf {B} \mathbf {x} \mid \mathbf {x} \in \mathbb {R} _{+}^{k}\}}$${\displaystyle C(\mathbf {A} )}$

En posant et dans le lemme de Farkas généralisé, on obtient le corollaire suivant sur la solvabilité pour un système fini d'égalités linéaires : ${\displaystyle \mathbf {S} =\mathbb {R} ^{n}}$${\displaystyle \mathbf {S} ^{*}=\{0\}}$

Autres implications

Le lemme de Farkas peut être modifié en de nombreux autres théorèmes d'alternative par de simples modifications, comme le théorème de Gordan : Soit a une solution x , soit a une solution non nulle y avec y ≥ 0. ${\displaystyle Ax<0}$${\displaystyle A^{\mathsf {T}}y=0}$

Les applications courantes du lemme de Farkas incluent la démonstration du théorème de dualité forte associé à la programmation linéaire , la théorie des jeux à un niveau de base et les contraintes de Kuhn-Tucker . Une extension du lemme de Farkas peut être utilisée pour analyser les conditions de dualité forte et construire le dual d'un programme semi-défini. Il suffit de prouver l'existence des contraintes de Kuhn-Tucker en utilisant l' alternative de Fredholm mais pour que la condition soit nécessaire, il faut appliquer le théorème du minimax de Von Neumann pour montrer que les équations dérivées par Cauchy ne sont pas violées.

Voir également

• Programme double linéaire
• Élimination de Fourier-Motzkin - peut être utilisé pour prouver le lemme de Farkas.

Remarques

Lectures complémentaires

• Goldman, AJ ; Tucker, AW (1956). "Cônes convexes polyédriques" . À Kuhn, HW; Tucker, AW (éd.). Inégalités linéaires et systèmes associés . Princeton : Princeton University Press. p. 19-40. ISBN 0691079994.
• Rockafellar, RT (1979). Analyse convexe . Presse de l'Université de Princeton. p. 200.
• Kutateladze SS Le lemme de Farkas revisité. Journal mathématique de Sibérie , 2010, Vol. 51, n° 1, 78-87.