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 est ou non consistant, c'est-à-dire s'il admet ou non une solution (ou, pour ceux dont 0 est une solution évidente, une solution non nulle).
Le principe en est à chaque fois le suivant : face à un système d'inéquations, on peut opérer des combinaisons linéaires de ces inéquations à coefficients positifs ou nuls, qui sont alors toutes des conséquences du système (l'usage judicieux de coefficients strictement positifs permettant au cas par cas de produire des conséquences qui soient des inégalités strictes). Il est bien évident que si l'une de ces conséquences est une absurdité – typiquement
– le système initial ne peut avoir de solution. Or, il se trouve que cette condition suffisante pour que le système soit inconsistant est à chaque fois nécessaire : chacun des théorèmes ci-dessous en exprime une variante.
Le nom de « théorèmes de l'alternative » vient du fait que la condition nécessaire et suffisante a, elle aussi, la forme d'un problème de recherche de solutions pour un système mêlant équations et inéquations. On se retrouve donc en parallèle avec deux systèmes, dont un et un seul a des solutions. Traduites en termes de matrices, les deux branches de l'alternative ont des formulations du même esprit, voire étonnamment semblables dans le cas du théorème de Ville.
Systèmes d'inéquations strictes et systèmes d'inéquations larges : les théorèmes de Gordan et de Stiemke[modifier | modifier le code]
Il couvre le cas d'un système d'inéquations toutes strictes, de la forme :
![{\displaystyle f_{1}(y)>0,\,f_{2}(y)>0,\ldots ,f_{k}(y)>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ed0cdd2f41a709e0c9a1a4b9b6cf65a218a8f51)
où les
sont des formes linéaires sur un espace vectoriel réel
de dimension finie.
Il y a une obstruction évidente à l'existence de solutions pour un tel système : si on fait une combinaison linéaire à coefficients positifs non tous nuls de cette famille d'inéquations, on obtient une nouvelle inéquation stricte vérifiée par toutes les solutions. Si on peut ajuster les coefficients de cette combinaison linéaire de façon à obtenir l'inéquation absurde
, c'est que le système était inconsistant.
Le théorème de Gordan assure que, à partir de tout système inconsistant, on peut ainsi produire l'inéquation
:
Théorème de Gordan (1873) — Soit
des formes linéaires sur un espace vectoriel réel de dimension finie
. Alors :
![{\displaystyle \{y\in E\,\mid \,f_{1}(y)>0,f_{2}(y)>0,\ldots ,f_{k}(y)>0\}=\varnothing }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a83554b56081bffc1b22b54c455b9cb054d24307)
si et seulement si
- il existe une écriture
à coefficients tous positifs ou nuls dont l'un au moins n'est pas nul.
Il concerne les systèmes d'inéquations linéaires au sens large :
.
Son énoncé est précisément le suivant :
Théorème de Stiemke (1915) — Soit
des formes linéaires sur un espace vectoriel de dimension finie
. Alors :
, l'une au moins de ces inégalités étant stricte![{\displaystyle \}=\varnothing }](https://wikimedia.org/api/rest_v1/media/math/render/svg/28396b3606a839fa0c09f3af7e38bf600b878bab)
si et seulement si
- il existe une écriture
à coefficients tous strictement positifs.
Cet énoncé est rendu un peu plus difficile à lire que les autres théorèmes de la série à cause de la technicité « l'une au moins de ces inégalités étant stricte » ; la raison d'être de celle-ci est que les systèmes d'inéquations larges ne peuvent être complètement inconsistants : ils comptent au moins
parmi leurs solutions, et au-delà tous les points qui vérifient le système d'équations linéaires correspondant. D'où la nécessité de compliquer un peu la forme du système en ne considérant pas comme des solutions significatives celles qui sont dans l'intersection des noyaux de toutes les formes
.
Parmi tous les théorèmes considérés dans cette page, le théorème de Gordan est celui où la démonstration contient le moins de technicités supplémentaires. On peut la fonder sur un théorème de séparation des convexes (celui parfois appelé « deuxième forme géométrique du théorème de Hahn-Banach ») ou par le théorème de projection sur un convexe fermé. C'est ce dernier choix qui est fait ici.
Comme il est souvent pratique pour faire des manipulations dans un dual, munissons
d'une structure euclidienne ; pour chaque indice
, il existe dès lors un vecteur
unique de
qui permette d'écrire pour tout
:
.
Considérons le convexe compact
enveloppe convexe des
points
et notons
la projection orthogonale de
sur ce fermé de
. On sait que pour tout
de
(et en particulier pour les
) on dispose de l'inégalité :
qu'on regroupe en
.
Entrons dans le vif de la preuve de Gordan. Comme pour tous les théorèmes de l'article, l'implication montante est évidente. Montrons donc l'implication descendante, en supposant le système d'inégalités strictes inconsistant. En particulier
n'en est alors pas solution, donc il existe un
pour lequel
. D'où
, puis
, ce qui prouve bien que
appartient à
, et est donc combinaison linéaire à coefficients positifs des
.
Le théorème de Gordan entraîne le théorème de Stiemke[modifier | modifier le code]
On peut donner une démonstration directe du théorème de Stiemke en appelant de nouveau la théorie de la séparation des convexes. Il est toutefois instructif de s'apercevoir que c'est un théorème « dual » du théorème de Gordan, et qu'on peut l'en déduire par des manipulations algébriques simples à défaut d'être naturelles.
On reverra ces mêmes manipulations présentées sous forme matricielle plus loin, en énonçant le théorème de Ville. Elles reposent sur une idée importante qu'on retrouve notamment à la base de la théorie du problème dual en optimisation linéaire : la deuxième branche de l'équivalence dans le théorème de Stiemke, qui est en première lecture un mélange d'inéquations strictes (les conditions
) et d'une équation vectorielle (la condition
) peut, avec un peu de doigté, être transformée en une simple collection d'inéquations strictes, à laquelle on peut appliquer le théorème de Gordan. Stiemke apparaît finalement comme une réécriture de Gordan où les emplacements des deux énoncés équivalents se retrouvent intervertis.
Exécution de la preuve
On commence par extraire de
une famille libre maximale ; quitte à renuméroter, on suppose que c'est
. On la complète arbitrairement en une base
de
et enfin on note
la base de
dont
est la base duale. On a donc, pour tout
entre
et
et tout
entre
et
la relation
(symbole de Kronecker) ; comme les
pour
entre
et
sont des combinaisons linéaires des premiers
, toutes les formes
s'annulent sur tous les
d'indices
.
Une fois ces notations posées, lançons nous dans la preuve de Stiemke. Comme dans chaque énoncé, l'implication montante est évidente. Prouvons l'autre par contraposition, en supposant donc que 0 ne peut pas être écrit sous la forme
avec des
tous strictement positifs, dans le but de construire un
solution du système d'inéquations.
Une relation entre applications linéaires est vraie, si et seulement si, elle est vraie en tout vecteur d'une base donnée ; on peut donc remarquer que :
Le système
n'a pas de solutions.
Insérons dans ce système les informations sur les
, on sait ainsi que :
Le système
n'a pas de solutions.
Point crucial de la preuve, l'inconsistance du système mixte d'inéquations et équations qui précède peut se réexprimer comme inconsistance d'un système plus simple ne comprenant plus que des inéquations :
Le système
n'a pas de solutions.
La forme de ce système rentre dans le cadre du théorème de Gordan. Il existe donc des réels positifs ou nuls
, dont au moins un n'est pas nul, avec lesquels on peut construire une combinaison linéaire nulle des formes apparaissant dans le système qui précède. En annulant successivement le coefficient de chaque
, on constate que :
- pour tout indice
entre
et
,
.
Il découle par ailleurs des relations
que
- pour les indices
entre
et
,
.
Posons alors
. On s'aperçoit alors qu'on vient de construire avec ce vecteur une solution non triviale du système d'inéquations objet de l'énoncé du théorème de Stiemke.
Systèmes mêlant inéquations strictes et larges : le lemme de Farkas et le théorème de Motzkin[modifier | modifier le code]
Le lemme de Farkas énonce une condition nécessaire et suffisante d'inconsistance pour un système d'inéquations linéaires dont exactement une est stricte :
Lemme de Farkas(1902) — Soit
des formes linéaires sur un espace vectoriel réel de dimension finie
. Alors :
![{\displaystyle \{y\in E\,\mid \,f_{1}(y)>0,f_{2}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}=\varnothing }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1188df2760137d53571dc57a1db9915a6c8609d3)
si et seulement si
- il existe une écriture
à coefficients tous positifs ou nuls et avec
.
Enfin le théorème de Motzkin couvre le cas général d'un système mêlant inéquations strictes et inéquations larges, avec une au moins stricte ; le lemme de Farkas en est le cas particulier correspondant à
(le théorème de Gordan correspondant à
) :
Théorème de Motzkin (1936) — Soit
des formes linéaires sur un espace vectoriel réel de dimension finie
et soit p avec
. Alors :
![{\displaystyle \{y\in E\,\mid \,f_{1}(y)>0,f_{2}(y)>0,\ldots ,f_{p}(y)>0,f_{p+1}\geq 0,\ldots ,f_{k}(y)\geq 0\}=\varnothing }](https://wikimedia.org/api/rest_v1/media/math/render/svg/415a9bd671145ed1dcbe91abd8ebe15254b09d82)
si et seulement si
- il existe une écriture
à coefficients tous positifs ou nuls avec
.
Le théorème de Gordan entraîne le lemme de Farkas[modifier | modifier le code]
Le théorème de Gordan se démontre en moins d'une dizaine de lignes à condition de disposer des théorèmes de séparation des convexes ou de projection sur un convexe fermé. On peut à partir de là prouver le lemme de Farkas avec un peu de gymnastique supplémentaire, qui ne nécessite aucun outil avancé mais n'est pas complètement naturelle.
Détails de la déduction de Farkas depuis Gordan
On montre le lemme de Farkas par récurrence sur la dimension. Il est évident en dimension 0 ou 1 ; supposons le vrai en toute dimension strictement inférieure à
.
On vérifie sans mal que si on dispose du théorème de Farkas pour des familles de formes linéaires toutes non nulles, les cas particuliers où telle ou telle des
est la forme nulle s'en déduit sans aucune difficulté. On supposera dès lors toutes les
non nulles.
Supposons inconsistant le système qui apparaît dans l'énoncé du lemme de Farkas. Celui qui apparaît dans l'énoncé de Gordan est a fortiori inconsistant. On peut donc écrire :
![{\displaystyle \lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}=0\qquad (*)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad1a7cacce1eec6a3bbc191771c3e6c9ae8e9dc0)
avec des réels positifs ou nuls
dont un au moins n'est pas nul.
- Cas évident : si
. Le résultat souhaité est obtenu, on a fini.
- Cas problématique : si
. Quitte à renuméroter les
, on peut alors supposer qu'il y a un
tel que les
non nuls soient exactement
. Quitte à multiplier les
par des constantes strictement positives, on peut même supposer, ce qui simplifiera les calculs, que la relation
se réduit à :
.
Notons
, de dimension strictement plus petite que
puisque
n'est pas nulle. Le lemme de Farkas est donc vrai dans
. Par ailleurs le système
est sans solution dans
.
Il existe donc des réels positifs ou nuls
avec
tels que :
- pour tout
de
,
.
Les formes linéaires nulles sur l'hyperplan
sont exactement les multiples de
. Il existe donc un réel
tel que :
.
- Si
, on regroupe cette relation en
et on a terminé ;
- Si
, on récupère la relation en attente
et on termine en écrivant :
et on a aussi terminé.
Le lemme de Farkas entraîne le théorème de Motzkin[modifier | modifier le code]
Bien que le théorème de Motzkin semble plus général que celui de Farkas, il s'en déduit en quelques lignes, comme suit :
On note, pour des indices variant de
à
:
![{\displaystyle {\begin{matrix}C_{1}&=&\{y\in E\,\mid \,f_{1}(y)>0,&f_{2}(y)\geq 0,&f_{3}(y)\geq 0,\ldots ,&f_{p}(y)\geq 0,&f_{p+1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}\\C_{2}&=&\{y\in E\,\mid \,f_{1}(y)\geq 0,&f_{2}(y)>0,&f_{3}(y)\geq 0,\ldots ,&f_{p}(y)\geq 0,&f_{p+1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}\\\vdots &&&&\vdots &&\vdots \\C_{p}&=&\{y\in E\,\mid \,f_{1}(y)\geq 0,&f_{2}(y)\geq 0,&f_{3}(y)\geq 0,\ldots ,&f_{p}(y)>0,&f_{p+1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e2331ad277747175ac5e549912e2144325485be)
On remarque que si on prend
dans
,
dans
,
,
dans
, leur somme est dans l'ensemble des solutions du système traité par le théorème de Motzkin. Si celui-ci est vide, c'est donc que l'un des
est vide. Mais on peut alors appliquer le lemme de Farkas à ce
et il fournit bien un
-uplet
qui répond aux conditions du théorème de Motzkin (en utilisant
).
Comme dans tous les théorèmes rassemblés ici, l'implication montante est une évidence.
Extension à des systèmes d'inéquations affines[modifier | modifier le code]
Une fois connus ces théorèmes, on peut en déduire en tant que de besoin des énoncés pour des systèmes affines, c'est-à-dire où les inéquations n'auraient pas la forme
mais
pour des constantes
. La démarche est explicitée à l'article Lemme de Farkas auquel on renvoie : elle consiste à considérer l'espace affine de référence comme hyperplan affine d'équation
dans un espace vectoriel
. La consistance d'un système affine dans
se ramène alors à la consistance d'un système analogue dans
mais auquel on a ajouté la condition supplémentaire
. Ainsi un système d'inéquations affines larges est-il traité par le lemme de Farkas, tandis qu'un système d'inéquations affines dont une et une seule est stricte se traite-t-il comme un système linéaire couvert par Motzkin avec
(c'est l'énoncé intitulé « lemme de Farkas généralisé » dans l'article lemme de Farkas).
Les théorèmes de l'alternative : point de vue matriciel[modifier | modifier le code]
Pour
matrice réelle, la notation
signifie que tous les termes de
sont positifs ou nuls, la notation
que tous les termes de
sont strictement positifs. Enfin on note
la transposée de la matrice
.
Traductions matricielles des énoncés déjà donnés[modifier | modifier le code]
Commençons par la version matricielle du lemme de Farkas, puisque c'est le théorème le plus notable. Elle s'obtient sans aucune subtilité à partir de la version donnée plus haut, la seule difficulté étant de bien rapprocher les notations de l'une et de l'autre.
Vérification
La vérification qui suit utilise les notations non de la version donnée plus haut mais de la version dite « version vectorielle » dans l'article lemme de Farkas (qui lui est équivalente de façon immédiate) à laquelle on se réfèrera donc.
Pour chaque colonne
de
(
), notons
la forme linéaire définie sur
par
; notons par ailleurs
la forme linéaire
.
L'existence d'une solution pour la première branche de l'alternative, c'est l'existence d'un
-uplet
de nombres positifs ou nuls tels que
, autrement dit c'est la possibilité d'écrire
comme combinaison linéaire à coefficients positifs des
.
L'existence d'une solution pour la deuxième branche de l'alternative, c'est l'existence d'un
qui soit dans
mais qui ne soit pas dans
.
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.
On écrit de même des versions matricielles pour les théorèmes de Gordan et de Stiemke, dont la vérification est du même esprit.
Ce théorème, qui se déduit en quelques lignes du théorème de Gordan dès lors qu'on manipule les notations matricielles, a un énoncé très agréablement symétrique sous cette forme ; on peut bien sûr le réécrire en termes de conditions nécessaire et suffisante d'existence de solutions de systèmes d'inéquations, son charme étant qu'on peut le faire de deux façons selon l'ordre dans lequel on considère les deux branches de l'alternative : au choix on peut y voir une condition nécessaire et suffisante d'existence de solutions en nombres positifs ou nuls pour un système d'inégalités linéaires larges, ou d'existence de solutions en nombres strictement positifs pour un système d'inégalités linéaires strictes.
Démonstration
Il se vérifie en quelques lignes : introduisons la matrice définie par collage de deux blocs :
et explicitons pour cette matrice
l'alternative matricielle énoncée par le théorème de Gordan.
La deuxième branche est immédiate :
est directement équivalent à
et
, ce qui est exactement le système figurant en deuxième branche de l'alternative dans l'énoncé qu'on est en train de montrer.
La première demande un peu plus de concentration. L'existence d'un
tel que
avec
et
revient, en appelant
le vecteur-colonne regroupant les
premières composantes de
et
celui regroupant les
dernières, à l'existence de
avec :
,
,
et
.
Ce système équivaut immédiatement à :
,
,
et
(il ne peut avoir de solution avec
mais
).
Enfin on s'aperçoit que ce dernier système a des solutions, si et seulement si, le système plus simple, de seule inconnue
:
en possède.
On reconnaît la première branche de l'alternative dans l'énoncé du théorème de Ville, qui est ainsi prouvé.
Sauf précisions plus spécifiques, les informations fournies par cet article sont issues, sur un mode assez distancié, des pages 51 et suivantes de Linear Programming 2: Theory and Extensions, de George Dantzig et Mukund Thapa, Springer, 2003 (ISBN 978-0387986135).
La démonstration du lemme de Farkas via le théorème de Gordan est issue de Convex Analysis and Nonlinear Optimization, Theory and Examples de Jonathan M. Borwein et Adrian S. Lewis, coll. « Ouvrages de mathématiques de la Société mathématique du Canada », vol. 3, 2e édition, Springer, 2006 (ISBN 978-0387989402), p. 24-25.