Théorèmes de l'alternative - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Systèmes d'inéquations strictes et systèmes d'inéquations larges : les théorèmes de Gordon et de Stiemke - Les théorèmes de l'alternative : point de vue matriciel - Systèmes mêlant inéquations strictes et larges : le lemme de Farkas et le théorème de Motzkin

Systèmes mêlant inéquations strictes et larges : le lemme de Farkas et le théorème de Motzkin

Les énoncés

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 $f_1,\ldots,f_k$ des formes linéaires sur un espace vectoriel réel de dimension finie $E$ . Alors :

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

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 à $p = 1$ (le théorème de Gordan correspondant à $p = n$ ) :

Théorème de Motzkin (1936) — Soit $f_1,\ldots,f_k$ des formes linéaires sur un espace vectoriel réel de dimension finie $E$ et soit p avec $1\leq p \leq n$ . Alors :

$\{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\}=\emptyset$

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

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.

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 à $\mathrm{dim}\, E$ .

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 $f j$ est la forme nulle s'en déduit sans aucune difficulté. On supposera dès lors toutes les $f j$ 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 :

avec des réels positifs ou nuls $λ j$ dont un au moins n'est pas nul.

Cas évident : si $\lambda_1\not=0$ . Le résultat souhaité est obtenu, on a fini.

Cas problématique : si $λ 1 = 0$ . Quitte à renuméroter les $f j$ , on peut alors supposer qu'il y a un $p\leq k$ tel que les $λ j$ non nuls soient exactement $\lambda_2, \ldots,\lambda_p$ . Quitte à multiplier les $f j$ par des constantes strictement positives, on peut même supposer, ce qui simplifiera les calculs, que la relation $( * )$ se réduit à :

Notons $H=\mathrm{Ker}\, f_2$ , de dimension strictement plus petite que $E$ puisque $f 2$ n'est pas nulle. Le lemme de Farkas est donc vrai dans $H$ . Par ailleurs le système $f_1(y)>0,f_3(y)\geq 0,\ldots,f_k(y)\geq0$ est sans solution dans $H$ .

Il existe donc des réels positifs ou nuls $\mu_1,\mu_3\ldots,\mu_k$ avec $μ 1 > 0$ tels que :

pour tout

y

H

Les formes linéaires nulles sur l'hyperplan $H=\mathrm{Ker}\, f_2$ sont exactement les multiples de $f 2$ . Il existe donc un réel $ν$ tel que :

- Si $\nu\leq 0$ , on regroupe cette relation en $\mu_1 f_1-\nu f_2+\mu_3f_3+\cdots+\mu_kf_k=0$ et on a terminé ;

- Si $ν > 0$ , on récupère la relation en attente $f_2+\cdots+f_p=0$ et on termine en écrivant : $\mu_1 f_1+(\mu_3+\nu)f_3+\cdots+(\mu_p+\nu)f_p+\mu_{p+1}f_{p+1}+\mu_kf_k=0$ et on a aussi terminé.

Le lemme de Farkas entraîne le théorème de Motzkin

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 $1$ à $p$ :

$\begin{matrix} C_1&=&\{y\in E\,\mid\,f_1(y)>0,&f_2(y)\geq0,&f_3(y)\geq0,\ldots,&f_p(y)\geq0,&f_{p+1}(y)\geq0,\ldots,f_k(y)\geq0\}\\ C_2&=&\{y\in E\,\mid\,f_1(y)\geq0,&f_2(y)>0,&f_3(y)\geq0,\ldots,&f_p(y)\geq0,&f_{p+1}(y)\geq0,\ldots,f_k(y)\geq0\}\\ \vdots&&&&\vdots&&\vdots\\ C_p&=&\{y\in E\,\mid\,f_1(y)\geq0,&f_2(y)\geq0,&f_3(y)\geq0,\ldots,&f_p(y)>0,&f_{p+1}(y)\geq0,\ldots,f_k(y)\geq0\}\\ \end{matrix}$

On remarque que si on prend $y 1$ dans $C 1$ , $y 2$ dans $C 2$ , $\ldots$ , $y p$ dans $C p$ , 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 $C j$ est vide. Mais on peut alors appliquer le lemme de Farkas à ce $C j$ et il fournit bien un $k$ -uplet $(\lambda_1,\ldots,\lambda_k)$ qui répond aux conditions du théorème de Motzkin (en utilisant $\lambda_j\not=0$ ).

Comme dans tous les théorèmes rassemblés ici, l'implication montante est une évidence.

Extension à des systèmes d'inéquations affines

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 $f_j(y) \geq 0$ mais $f_j(y)\geq c_j$ pour des constantes $c j$ . 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 $g (y) = 1$ dans un espace vectoriel $\hat E$ . La consistance d'un système affine dans $E$ se ramène alors à la consistance d'un système analogue dans $\hat E$ mais auquel on a ajouté la condition supplémentaire $g (y) > 0$ . 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 $p = 2$ (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

✨ Pourquoi les étoiles paraissent plus brillantes l'été ?

🌱 Comment les plantes résistent-elles à une lumière trop intense ?

⚫ Une IA révèle que le trou noir supermassif de notre galaxie pointe vers la Terre

🏔️ Découverte d'un monde perdu sous l'Antarctique

🌍 Découverte: cette règle universelle régit toute vie sur terre

⏳ L'Univers pourrait disparaître plus tôt que prévu: ce que révèle cette étude

🌍 Les dernières mesures révèlent un niveau de CO₂ jamais vu depuis 4 millions d'années

🛡️ Le paradoxe des gangs de rue

💰 Quelle quantité d'or existe-t-il vraiment sur Terre ?

🦟 Pourquoi les moustiques sont plus nombreux et piquent davantage en été ?

⚫ Ces trous noirs interagissent avec la lumière fossile du Big Bang

🦕 Et si les dinosaures détenaient le secret pour vaincre le cancer ?

😎 Comment font les lunettes de soleil pour filtrer les UV ?

🚶‍♂️‍➡️ La marche des babouins éclaire l'évolution de la bipédie humaine

🔭 James Webb capture cette image directe d'une étrange planète à 60 années-lumière

🦋 Pourquoi et comment les chenilles deviennent-elles des papillons ?

🔭 Voici la plus grande carte de l'Univers. Ses révélations sont surprenantes !

😴 Penser que l'on est éveillé alors que l'on dort, normal ?

🌊 Ce cratère raconte l'histoire de l'eau sur Mars

🐝 Comment les fleurs attirent-elles les insectes pollinisateurs ?

💥 La collision entre notre Voie lactée et la galaxie d'Andromède remise en question

🎶 Pourquoi les oiseaux chantent-ils autant et si fort au printemps ?

💡 Générer de la lumière à partir du vide, c'est possible

Découverte d'un deuxième système d'apprentissage dans le cerveau

☀️ Comment se produit un coup de chaleur et comment s'en protéger ?

⚽ Comment fonctionne la physique d'un tir puissant au foot ?

🧠 Un algorithme révèle comment notre cerveau se motive

🔭 Une si grande planète orbite une si petite étoile, comment est-ce possible ?

🐋 Les baleines développent de nouvelles méthodes pour communiquer avec nous

🥚 Le noyau de Mars sent l'œuf pourri

🧠 On sait enfin pourquoi le sémaglutide fait maigrir

🌱 La vie pourrait renaître sur Europe après la mort de la Terre

🌿 Confirmation scientifique: ce remède ancestral fait naturellement maigrir, et pas qu'un peu !

💥 Des astronomes identifient les plus puissantes explosions depuis le Big Bang

🦕 Ce crâne de stégosaure, le plus complet jamais découvert, réécrit l'histoire

🛏️ Les punaises de lit, ces compagnons indésirables depuis la préhistoire

🕸️ Connaissez-vous la toile cosmique, l'architecte de l'Univers ?

🌋 L'éruption de l'Etna vue depuis l'espace

🐋 Il y a 20 000 ans, l'Homme fabriquait des outils avec des os de baleines

🟠 Quel est le rôle de ce labyrinthe sur Mars ?

🎯 Cette stratégie innovante contre le cancer du sein offre une survie de 100%

💥 Le pulsar à trou noir: un objet qui intrigue les astrophysiciens

🐒 Première: ces singes kidnappent les bébés d'une autre espèce

🌍 Découverte d'une super-Terre à l'habitabilité intermittente

🧠 Ces cellules pourraient jouer un rôle bien plus important que les neurones dans la mémoire

🛰️ Une carte photographique de la Terre toutes les 35 minutes

Pourquoi l'oxygène est-il si indispensable à autant d'êtres vivants ?

🐱 Pourquoi certains chats miaulent et ronronnent plus que d'autres ?

Découverte: un antidouleur sans effets secondaires

🤔 Ces expériences remettent en question un concept fondamental de la thermodynamique

Page générée en 0.103 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales
Version anglaise | Version allemande | Version espagnole | Version portugaise