Cône dual

En mathématiques, et plus précisément en analyse convexe, le cône dual d'une partie $P$ d'un espace euclidien $E$ est l'ensemble des vecteurs de $E$ qui font un angle plus petit que $\pi /2$ avec les vecteurs de $P$ . C'est un cône convexe fermé non vide.

Un ensemble

C

du plan euclidien et son cône dual

C^{*}

On définit plus généralement, pour une partie $P$ d'un espace vectoriel réel $E$ , le cône dual (algébrique) de $P$ , qui est un cône de l'espace dual $E^{*}$ et, si $E$ est un espace vectoriel topologique, le cône dual topologique de $P$ , qui est un cône du dual topologique $E'$ .

Définitions

Soit $P$ une partie non vide d'un espace vectoriel réel $E$ . Le cône dual de $P$ est l'ensemble $P^{*}\subset E^{*}$ défini par

$P^{*}:=\{y\in E^{*}\mid \forall x\in P\;\;\langle y,x\rangle \geqslant 0\},$

c'est-à-dire l'ensemble des formes linéaires sur $E$ qui sont positives sur $P$ .

Ce cône porte aussi parfois le nom de cône dual positif, tandis que son opposé $-P^{*}$ porte le nom de cône dual négatif (ou parfois cône polaire[1], bien que ce dernier renvoie aussi à un autre concept).

Le cône bidual de $P$ est $P^{**}:=(P^{*})^{*}$ .

Lorsque $E$ est un espace vectoriel topologique réel , on définit de façon analogue le cône dual topologique : $P^{'}\subset P^{*}$ est le cône des formes linéaires continues sur $E$ qui sont positives sur $P$ .

Si $E$ est de dimension finie, $E'=E^{*}$ et $P'=P^{*}$ .

Si $E$ est un espace de Hilbert réel, le théorème de représentation de Riesz permet d'identifier $E'$ à $E$ et donc $P'$ à un cône de $E$ . Un cône est alors dit autodual s'il est égal à son dual.

L'intersection de ces deux cas particuliers est celui où $E$ est un espace euclidien. Seul ce cas sera considéré dans la suite de cet article.

Notations

$E$ et $F$ désigneront des espaces euclidiens (produit scalaire et norme associés notés $\langle \cdot ,\cdot \rangle$ et $\|\cdot \|$ respectivement).

Soit $P$ une partie de $E$ . On note

${\overline {P}}$ l'adhérence de $P$ .
$\operatorname {co} P$ l'enveloppe convexe de $P$ et ${\overline {\operatorname {co} }}P:={\overline {\operatorname {co} P}}$ son enveloppe convexe fermée.

On note $\operatorname {aff} C$ l'enveloppe affine d'un convexe non vide $C$ de $E$ et $\operatorname {ir} C$ son intérieur relatif.

Pour toute application linéaire $A:E\to F$ , l'application $A^{*}:F\to E$ est l'adjointe de $A$ .

Pour toute matrice $A$ , la matrice $A^{\top }$ est la transposée de $A$ .

Premières propriétés

$P^{*}$ est clairement un cône convexe fermé non vide de $E$ , comme intersection de la famille non vide des demi-espaces fermés $\{y\in E\mid \langle x,y\rangle \geqslant 0\}$ , indexée par $x\in P$ .

On a aussi les propriétés suivantes.

Soient $P$ et $Q$ des parties non vides de $E$ et $(P_{i})_{i\in I}$ une famille non vide de parties non vides de $E$ . Alors :

$(\cup _{i\in I}P_{i})^{*}=\cap _{i\in I}P_{i}^{*}$ [2] ;

$P^{*}=\left({\overline {\operatorname {co} }}(\mathbb {R} _{+}P)\right)^{*}$ ;

le bidual de $P$ est le plus petit cône convexe fermé contenant $P$ : $P^{**}={\overline {\operatorname {co} }}(\mathbb {R} _{+}P)$ ;

$(P+Q)^{*}\supset P^{*}\cap Q^{*}$ , avec égalité si $0\in {\overline {P\cap Q}}$ ;

si $P$ et $Q$ sont des cônes convexes fermés alors $(P\cap Q)^{*}={\overline {P^{*}+Q^{*}}}$ .

Remarques

Dans l'égalité du point 3, l'inclusion immédiate ${\overline {\operatorname {co} }}(\mathbb {R} _{+}P)\subset P^{**}$ traduit le fait que $P^{**}$ est un cône convexe fermé contenant $P$ . L'inclusion réciproque, $P^{**}\subset {\overline {\operatorname {co} }}(\mathbb {R} _{+}P)$ , peut s'interpréter géométriquement comme suit. Elle signifie que si un vecteur $b$ n'appartient pas à ${\overline {\operatorname {co} }}(\mathbb {R} _{+}P)$ , alors $b\notin P^{**}$ , ce qui revient à dire qu'il existe un vecteur $y_{0}\in P^{*}=\left({\overline {\operatorname {co} }}(\mathbb {R} _{+}P)\right)^{*}$ tel que $\langle y_{0},b\rangle <0$ , ou encore, tel qu'un certain hyperplan orthogonal à $y_{0}$ sépare strictement $\{b\}$ de ${\overline {\operatorname {co} }}(\mathbb {R} _{+}P)$ . La démonstration du point 3 peut d'ailleurs se faire par séparation stricte de ces deux convexes (théorème de Hahn-Banach).
Dans le point 5 (qui se déduit du 4 par dualité), on peut enlever l'adhérence si $P$ et $Q$ sont polyédriques (comme l'orthant positif d'un certain $\mathbb {R} ^{p}$ ) �?car $P^{*}+Q^{*}$ est alors polyédrique donc fermé �?ou si $\operatorname {ir} P\cap \operatorname {ir} Q\neq \varnothing$ , mais il ne suffit pas que $P\cap \operatorname {ir} Q\neq \varnothing$ . Par exemple, dans $\mathbb {R} ^{3}$ , si $P$ est le cornet $\mathbb {R} _{\triangledown }^{3}$ et si $Q=\{x\in \mathbb {R} ^{3}\mid x_{2}=x_{3}\}$ , alors $P^{*}=\mathbb {R} _{\triangledown }^{3}$ (autodualité du cornet), $Q^{*}=\{d\in \mathbb {R} ^{3}\mid d_{1}=0,\;d_{2}+d_{3}=0\}$ , $P\cap \operatorname {ir} Q=P\cap Q=\{x\in \mathbb {R} ^{3}\mid x_{1}=0,\;x_{2}=x_{3}\geq 0\}\neq \varnothing$ , alors que $P^{*}+Q^{*}=\{d\in \mathbb {R} ^{3}\mid d_{2}+d_{3}>0\}\cup \{d\in \mathbb {R} ^{3}\mid d_{1}=0,\;d_{2}+d_{3}=0\}$ n'est pas fermé.

Lemme de Farkas et conséquences

Le lemme de Farkas a diverses interprétations. Nous le voyons ici comme un moyen de calculer le cône dual d'un ensemble défini au moyen d'une application linéaire.

Un lemme de Farkas généralisé

La notion de cône dual généralise celle de sous-espace vectoriel orthogonal, puisque si $P$ est un sous-espace vectoriel, $P^{*}=P^{\perp }$ . On connaît bien, pour une matrice $A$ , la relation

${\operatorname {Ker} {(A^{\top })}}^{\perp }=\operatorname {Im} {(A)}$ ,

qui nous apprend ce qu'est le cône dual d'un ensemble défini par un système d'équations linéaires homogènes. Une question naturelle est alors de se demander ce qu'est le cône dual d'un ensemble donné par des inégalités linéaires homogènes. La réponse à cette question est donnée par le lemme de Farkas (voir infra), que l'on peut généraliser comme suit.

Lemme de Farkas généralisé �?/span> Soient $A:E\to F$ une application linéaire et $K$ un cône convexe non vide de $E$ . Alors,

\left({A^{*}}^{-1}(K^{*})\right)^{*}={\overline {A(K)}}.

Lemme de Farkas généralisé.

Un calcul immédiat montre que pour toute partie non vide $K$ de $E$ , $\left({A^{*}}^{-1}(K^{*})\right)^{*}=A(K)^{**}$ . Par conséquent, le « lemme de Farkas généralisé » est un simple avatar de la propriété 3 ci-dessus (pour tout cône convexe $P$ , $P^{**}={\overline {P}}$ ) et s'interprète donc géométriquement de la même manière.

Remarquons que l'identité du « lemme de Farkas généralisé » s'écrit aussi ${A^{*}}^{-1}(K^{*})=(A(K))^{*}$ car �?contrairement à $A(K)$ �?le cône convexe ${A^{*}}^{-1}(K^{*})$ est nécessairement fermé, donc égal à son bidual.

L'identité du « lemme de Farkas généralisé » permet de donner une condition nécessaire pour que le système linéaire $Ax=b$ ait une solution $x$ dans $K$ . Il faut en effet que $b\in A(K)\subset {\overline {A(K)}}$ et donc que

{\mbox{pour tout}}~y~{\mbox{tel que}}~A^{*}y\in K^{*}~{\mbox{on ait}}~\langle y,b\rangle \geqslant 0.

Si $A(K)$ est fermé (par exemple si $K$ �?donc aussi $A(K)$ �?est polyédrique, ou si $K$ est fermé et $-K\cap \operatorname {Ker} A\subset K$ ), cette condition sur $A$ et $b$ est aussi suffisante. Si $A(K)$ n'est pas fermé, on peut trouver des conditions nécessaires et suffisantes pour que $b\in A(K)$ , qui renforcent l'expression ci-dessus[3]. Lorsque $K$ est l'orthant positif de $\mathbb {R} ^{n}$ , $A(K)$ est fermé et le résultat, exprimé sous une forme différente, est alors connu sous le nom de théorème de l'alternative (diverses variantes sont considérées dans l'article Théorèmes de l'alternative).

Corollaires

Corollaire 1 (Farkas) �?/span> Pour toute matrice $B$ ,

\{y\mid B^{\top }y\geqslant 0\}^{*}=\{Bx\mid x\geqslant 0\},

où $\{\cdot \}^{*}$ désigne le cône dual pour le produit scalaire euclidien.

On retrouve l'identité ${\operatorname {Ker} {(A^{\top })}}^{\perp }=\operatorname {Im} {(A)}$ lorsque $B={\begin{pmatrix}A&-A\end{pmatrix}}$ (par blocs).

Corollaire 2 (dual d'un polyèdre convexe) �?/span> Le cône dual d'un polyèdre convexe de $E$ est un polyèdre convexe.

Aspects topologiques

Intérieur et intérieur relatif du cône dual �?/span> Soient $P\subset E$ et $P_{(\operatorname {aff} {P^{*}})}$ le projecteur orthogonal sur le sous-espace vectoriel $\operatorname {aff} {P^{*}}$ . Alors

{\begin{array}{rcl}d\in \operatorname {int} {P^{*}}&\Longleftrightarrow &\exists \,\varepsilon >0,~\forall \,x\in P,~{\mbox{on a}}~\langle d,x\rangle \geqslant \varepsilon \|x\|.\\d\in \operatorname {ir} {P^{*}}&\Longleftrightarrow &\exists \,\varepsilon >0,~\forall \,x\in P,~{\mbox{on a}}~\langle d,x\rangle \geqslant \varepsilon \|P_{(\operatorname {aff} {P^{*}})}x\|.\end{array}}

Décomposition de Moreau

Clairement, tout $x\in \mathbb {R} ^{n}$ est la somme de ses parties positive et négative $\max(0,x)$ et $\min(0,x)$ (composante par composante), c'est-à-dire de ses projetés orthogonaux (pour le produit scalaire euclidien) sur $\mathbb {R} _{+}^{n}$ et $\mathbb {R} _{-}^{n}$ . La décomposition de Moreau[1] généralise l'identité pour des cônes différents de l'orthant positif $\mathbb {R} _{+}^{n}$ .

Décomposition de Moreau �?/span> Soient $K$ un cône convexe fermé de $E$ et $K^{-}=-K^{*}$ son cône dual négatif. On note $P_{K}$ et $P_{K^{-}}$ les projecteurs orthogonaux sur $K$ et $K^{-}$ respectivement. Alors, pour $x$ , $y$ et $z$ donnés dans $E$ , les propriétés suivantes sont équivalentes :

$z=x+y$ , $x\in K$ , $y\in K^{-}$ et $\langle x,y\rangle =0$ ,
$x=P_{K}(z)$ et $y=P_{K^{-}}(z)$ .

La décomposition de $z$ en $x+y$ comme au point 1 ci-dessus est appelée la décomposition de Moreau de $z$ , correspondant au cône $K$ .

Notes et références

J.-J. Moreau, « Proximité et dualité dans un espace hilbertien », Bull. Soc. Math. Fr., n^o 93, 1965, p. 273-299.
En particulier, $P\subset Q\Rightarrow P^{*}\supset Q^{*}$ .
Voir (en) J. B. Lasserre, « A Farkas lemma without a standard closure condition », SIAM Journal on Control and Optimization, vol. 35,�?/span> 1997, p. 265-272.