Formes linéaires positivement liées

supp

@Kubotai
J'ai vu passer ta question (hier, je crois). Le résultat énoncé est un cas particulier d'un théorème de dualité sur les cônes de type fini, théorème qui se déduit de l'alternative de Farkas. Mais une fois que l'on a dit cela, on n'a rien dit qui va dans ton sens. Certes, je pourrais te citer le théorème de dualité en question, mais ce n'est absolument pas ce que tu veux.

Et j'ai envie de jouer cartes sur table (je connais un peu Farkas et je dispose du Tauvel). Cela serait peut-être une bonne chose de répondre pour soi-même (j'insiste pour soi-même, pas sur le forum) aux questions ci-dessous (elles s'adressent à toi et également à moi) :

1) Combien de temps comptons nous passer pour décrypter le corrigé ?
2) Est ce que nous aurions pu trouver la preuve ``tout seul'' ?
3) Qu'en restera-t-il plus tard de cet exercice ?
4) Sommes nous capables de faire la preuve de tête en nous promenant dans les bois (ou ailleurs, c'est sans importance)
5) L'exercice arrive à la page 4 de l'ouvrage : est ce que ce n'est pas rageant ?

Je suis tout ce qu'il y a de plus sérieux. Par exemple, à propos de 1), j'y ai déjà passé un peu de temps et j'ai les mêmes soucis que toi en ce qui concerne l'inclusion $T(\varphi_r) \subset T(\varphi_r + \lambda \varphi_q)$. J'ai aussi le souci de bien intégrer les notations dans ma petite tête (ce n'est pas encore le cas mais j'ai peut-être pas assez lu). Quant à l'itération évoquée pour la chute et le coup du proche en proche, cela fout les pétoches quand on n'est pas encore à l'aise au premier tour de manège.

On raisonne par récurrence sur le cardinal de la famille positivement liée.
Soit $F=(\phi_1,\dots, \phi_k)$ une famille positivement liée.
On peut supposer que toutes les formes linéaires $\phi_i$ sont non nulles.
(En effet, si $\phi_i=0$, on rajoutera $1.\phi_i$ à la combinaison linéaire obtenue)..
Soit $K=\ker \phi_1$, alors $\phi_2, \dots, \phi_k$ restreintes à $K$, sont positivement liées.
Donc, il existe $\alpha_2, \dots, \alpha_k >0$ tels que, pour tout $x \in \ K$, $\alpha_2 \phi_2(x)+ \dots +\alpha_k \phi_k (x)=0$ par hypothèse de récurrence.
Donc $\ker \phi_1 \subset \ker(\alpha_2 \phi_2+ \dots+ \alpha_k \phi_k)$, donc il existe $\alpha_1 \in \R$, tel que $\alpha_2 \phi_2+ \dots+ \alpha_k \phi_k = - \alpha_1 \phi_1$.

Si $\alpha_1>0$, on obtient une combinaison linéaire à coefficients strictement positifs de somme nulle pour la famille $F$.

Si $\alpha_1<0$, alors $\phi_2(x), \dots,\phi_k(x) \in \R^+$ est équivalent à $\phi_1(x), \dots\phi_k(x) \in \R^+$, donc $\phi_2, \dots, \phi_k$ est positivement liée. Donc, par hypothèse de récurrence, il existe $\beta_2, \dots, \beta_k>0$ tels que $\beta_2 \phi_2+ \dots+ \beta_k \phi_k=0$.
Donc, pour tout $\lambda \in \R$, $-\alpha_1 \phi_1 +(-\alpha_2+\lambda \beta_2) \phi_2+ \dots+(-\alpha_k+\lambda \beta_k) \phi_k =0$. Il reste à choisir $\lambda$ suffisament grand pour obtenir une combinaison linéaire à coefficients strictement positifs de somme nulle.

Si $\alpha_1=0$, alors soit $\phi_1$ est engendrée par $\phi_2, \dots,\phi_k$, donc il existe $\lambda_2, \dots, \lambda_k \in \R$ tels que $\phi_1-\lambda_2\phi_2+ \dots + \lambda_k \phi_k=0$, donc c'est fini en ajoutant $\lambda(\alpha_2 \phi_2+ \dots+ \alpha_k \phi_k)=0$, avec $\lambda$ suffisament grand.
Soit $\phi_1$ n'est pas engendrée par $(\phi_2, \dots, \phi_k)$, donc il existe $x \in E$ tel que $\phi_1(x)=1$ et $\phi_2(x)= \dots=\phi_k(x)=0$. (en effet, $\ker \phi_2 \cap \dots \cap \ker \phi_k \subset \ker \phi_1$ est équivalent à $\phi_1 \in \mathrm{Vect}(\phi_2, \dots , \phi_k)$, donc par contraposée, on obtient l'existence d'un tel $x$). Donc on voit que la famille $F$ n'est pas positivement liée (contradiction).

[J'ai édité mon message]

supp

$\newcommand \scp[2] {\langle#1\,|\,#2\rangle}$@Kubotai
Je pense que l'exercice de Tauvel n'implique pas Farkas pour la raison qui suit. Je note $C$ le cône (dans le dual $E^*$) engendré par les formes linéaires $\varphi_i$ et $C^*$ son cône dual dans $E$ i.e. en utilisant $\scp{\varphi}{x}$ pour $\varphi(x)$ :
$$
C = \R_+ \varphi_1 + \cdots + \R_+ \varphi_n
\qquad\qquad
C^* = \{x \in E \mid \scp {C}{x} \ge 0 \} = \{x \in E \mid \scp{\varphi}{x} \ge 0 \ \forall \varphi \in C \}
$$
L'hypothèse de Tauvel c'est $C^* = (-C)^*$ (prendre le temps). Et la conclusion c'est $-C = C$. En effet, c'est bien la conclusion puisque, pour $n=3$ par exemple, si l'on a des coefficients $a_i, b_j, c_k \ge 0$ :
$$
\left\{
\begin {array} {c}
-\varphi_1 = a_1\varphi_1 + a_2\varphi_2 + a_3\varphi_3 \\
-\varphi_2 = b_1\varphi_1 + b_2\varphi_2 + b_3\varphi_3 \\
-\varphi_3 = c_1\varphi_1 + c_2\varphi_2 + c_3\varphi_3 \\
\end {array}
\right.
\qquad\qquad
\left\{\begin {array} {l}
0 = (a_1+1)\varphi_1 + a_2\varphi_2 + a_3\varphi_3 \\
0 = b_1\varphi_1 + (b_2+1)\varphi_2 + b_3\varphi_3 \\
0 = c_1\varphi_1 + c_2\varphi_2 + (c_3+1)\varphi_3 \\
\end {array}
\right.
$$
En additionnant les 3 égalités à droite, on obtient bien le critère de positivement liées. I.e. $C = -C$ c'est pareil que conclusion de l'exo. Et donc l'énoncé de l'exercice peut-être écrit :
$$
C^* = (-C)^* \qquad \Longrightarrow\qquad C = -C \qquad \qquad \text {(Tauvel)}
$$
Tandis qu'une forme de Farkas (encore une) est pour deux cônes de type fini $C_1, C_2$
$$
C_1^* = C_2^* \qquad \Longrightarrow\qquad C_1 = C_2 \qquad \qquad \qquad \text {(Farkas)}
$$
Et c'est pour cela que cela m'étonnerait fort que (Tauvel) implique (Farkas)

$\def\conv{\text{conv}}$@side
Je me permets de te signaler que, d'une part tu veux démontrer le résultat de l'exercice de Tauvel à partir d'un des nombreux énoncés de Farkas et que d'autre part, tu introduis de l'analyse réelle (ouvert convexe) dans un domaine dans lequel cela n'a pas lieu d'être.

Quitte à être lourd, je vais redire ce que j'ai déjà signalé. D'abord, Farkas se décline sous plusieurs formulations (au moins une dizaine à ma connaissance). Ensuite son champ d'applications est d'une part la théorie des cônes de type fini sur un corps (commutatif) totalement ordonné $\R$ et d'autre part la théorie de la convexité ``de génération finie'' (polyèdres, polytopes) sur un corps totalement ordonné. Ce n'est donc pas spécifique à $\R = \mathbb R$. Un cas particulier est d'ailleurs $\R = \mathbb Q$ en liaison avec le monde des variétés toriques.

A noter que Farkas n'est pas le seul outil. Un autre célèbre dans ce domaine est ``l'élimination de Fourier-Motzkin''.

J'en viens à une déclinaison convexe de Farkas : c'est l'alternative convexe de Farkas. Qui se déduit par un procédé automatique de l'autre alternative de Farkas (liée à la positivité). Contexte $u_1, \cdots, u_n \in \R^m$, rien de plus. On dispose alors de l'alternative (exclusive) suivante :

1) Ou bien $0$ appartient à la $\R$-enveloppe convexe $\conv_\R(u_1, \cdots, u_n)$ de $u_1, \cdots, u_n$.

2) Ou bien, il existe un hyperplan affine qui sépare strictement $0$ et $\conv_\R(u_1, \cdots, u_n)$ i.e. une forme affine $\nu : \R^m \to \R$ vérifiant :
$$
\nu(u_j) > 0 \quad j = 1, \cdots, n \qquad \nu(0) < 0
$$
Et ceci est effectif au sens où, dans les deux branches, on apporte le certificat de ce que l'on affirme. Ici, Farkas agit comme un théorème de séparation (dans un terrain de génération finie).

PS1 : je n'ai pas réussi à retrouver sur net un papier self-contained (années 1991-92) de André Warusfel : programmation linéaire sur un corps totalement ordonné. Il me semble en avoir parlé sur le forum il y a 1 ou 2 ans. Self-contained mais difficile à lire. Il est préférable de consulter d'autres sources. J'aime bien le ``Solving inequalities and Proving Farkas's Lemma Made Easy'' de Avis & Kaluzny http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Avis.pdf

PS2 : je suis loin de connaître toutes les instances de Farkas. Il en existe par exemple des versions purement combinatoires que je n'ai pas étudiées. Pareil : pas réussi à retrouver un numéro de RMS (années 1990, vague) avec un article Aspects Combinatoires de la propriété de Farkas (Marc Tenti)