Cône dual

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

Définitions[modifier | modifier le code]

Soit P une partie non vide d'une espace euclidien \mathbb{E}, dont le produit scalaire est noté \langle\cdot,\cdot\rangle. Le cône dual de P est l'ensemble P^+\subset\mathbb{E} défini par


P^+:=\{y\in\mathbb{E}:\langle x,y\rangle\geqslant0,~\mbox{pour tout}~x\in P\}.

Ce cône porte aussi parfois le nom de cône dual positif, tandis que son opposé


P^-:=-P^+=\{y\in\mathbb{E}:\langle x,y\rangle\leqslant0,~\mbox{pour tout}~x\in P\}

porte le nom de cône dual négatif (ou parfois cône polaire, bien que ce dernier renvoie aussi à un autre concept).

Le cône bidual de P est le cône dual de son cône dual P^+. On le note


P^{++}:=(P^+)^+.

On dit qu'un cône K est autodual si


K^+=K.

Un tel cône est nécessairement convexe et fermé (voir ci-dessous).

Notations[modifier | modifier le code]

Soit P une partie non vide d'un espace vectoriel \mathbb{E}. On note

Premières propriétés[modifier | modifier le code]

On peut voir P^+ comme une intersection de demi-espaces fermés de \mathbb{E} :


P^+:=\bigcap_{x\in P}\,\{y\in\mathbb{E}:\langle x,y\rangle\geqslant0\}.

On en déduit la propriété suivante.

Propriétés I — Soit P une partie non vide de \mathbb{E}. Alors son cône dual P^+ est un cône convexe fermé non vide de \mathbb{E}.

On a aussi les propriétés suivantes.

Propriétés II — Soient \mathbb{E} un espace euclidien, P, P_1 et P_2 des parties non vides de \mathbb{E} et (P_i)_{i\in I} une famille quelconque de parties P_i non vides de \mathbb{E}. Alors

  1. P_1\subset P_2 \Longrightarrow P_1^+\supset P_2^+ et P_1^{++}\subset P_2^{++},
  2. P^+=(\R_+ P)^+, P^+=(\operatorname{co} P)^+, P^+=(\operatorname{adh} P)^+,
  3. P^{++}=\overline{\operatorname{co}}(\R_+P), en particulier P\subset P^{++},
  4. P^{++}=P si, et seulement si, P est un cône convexe fermé,
  5. (P_1+P_2)^+\supset P_1^+\cap P_2^+, avec égalité si 0\in \operatorname{adh}(P_1\cap P_2),
  6. (\cup_{i\in I} P_i)^+=\cap_{i\in I} P_i^+.

Lemme de Farkas et conséquences[modifier | modifier le code]

Le lemme de Farkas a diverses interprétations (voir l'article Lemme de Farkas). 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é[modifier | modifier le code]

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 la relation

\mathcal{N}(A^\top)^\perp=\mathcal{R}(A),

qui nous apprend ce qu'est le cône dual d'un ensemble défini par des équations linéaires homogènes (on a noté \mathcal{R}(A) l'image d'une matrice A et \mathcal{N}(A^\top)^\perp l'orthogonal du noyau de sa transposée). 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 sera un corollaire du résultat plus général suivant. Dans celui-ci, on note A^*:\mathbb{F}\to\mathbb{E} l'application linéaire adjointe de l'application linéaire A:\mathbb{E}\to\mathbb{F} et A(K):=\{Ax:x\in K\} l'image du cône K par A.

Lemme de Farkas généralisé — Soient \mathbb{E} et \mathbb{F} deux espaces euclidiens, A:\mathbb{E}\to \mathbb{F} une application linéaire, K un cône convexe non vide de \mathbb{E} et L un cône convexe non vide de \mathbb{F}. Alors


\{y\in L^+ : A^*y\in K^+\}^+ = \overline{A(K)+L}.

On ne peut pas se passer de l'adhérence dans le membre de droite de l'identité car le cône convexe A(K)+L n'est pas nécessairement fermé (même si K est un cône convexe fermé) alors que, en tant que cône dual, le cône du membre de droite est toujours fermé. Signalons toutefois que si K et L sont des cônes polyédriques (comme l'orthant positif d'un certain \mathbb{R}^p), alors A(K)+L est aussi un cône polyédrique, donc un fermé ; dans ce cas, on peut ôter l'adhérence dans le membre de droite.

Observons que \{y\in L^+ : A^*y\in K^+\}=L^+\cap((A^*)^{-1}(K^+)) est l'intersection du cône convexe fermé L^+ et de l'image réciproque par l'application linéaire (continue) A^* du cône convexe fermé K^+ ; il s'agit donc d'un cône convexe fermé. Il est donc égal à son bidual. Dès lors, par le lemme de Farkas généralisé :

(A(K)+L)^+ = \{y\in L^+ : A^*y\in K^+\},

sans que l'on ait besoin de prendre d'adhérence à gauche.

Lemme de Farkas généralisé

Le résultat de la proposition peut s'interpréter géométriquement comme suit. De manière à simplifier la présentation, supposons que L=\{0\} et donc que L^+=\mathbb{F}. Alors le résultat devient

\{y\in \mathbb{F} : A^*y\in K^+\}^+ = \overline{A(K)}

et signifie qu'un vecteur b\notin\operatorname{adh}(A(K)) si, et seulement si, b\notin\{y\in \mathbb{F} : A^*y\in K^+\}^+, ce qui revient à dire qu'il existe un vecteur y_0\in\mathbb{F} tel que \langle y_0,b\rangle<0 et A^*y_0\in K^+. Cette propriété exprime donc le fait que l'hyperplan \{y\in\mathbb{F}:\langle y_0,y\rangle=0\} sépare strictement le singleton \{b\} de l'adhérence du cône convexe A(K). La démonstration de ce lemme généralisé peut d'ailleurs se faire par séparation stricte de ces deux derniers convexes (Hahn-Banach).

L'identité précédente 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\operatorname{adh}A(K) et donc que


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

Si A(K) est fermé, 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, voir Lasserre (1997[1]). Lorsque K est l'orthant positif de \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[modifier | modifier le code]

Voici un premier corollaire, plus proche de la contribution originale de Farkas.

Corollaire 1 (Farkas) — Soient A_1 et A_2 deux matrices ayant le même nombre de lignes. Alors


\{y : A^\top_1 y = 0, A^\top_2 y\geqslant 0\}^+ = \{A_1 x_1 + A_2 x_2 :
x_1 ~\mbox{quelconque},~ x_2 \geqslant 0\},

\{\cdot\}^+ désigne le cône dual pour le produit scalaire euclidien.

On retrouve l'identité \mathcal{N}(A^\top)^\perp=\mathcal{R}(A) lorsque A_1=A et A_2=0.

Le second corollaire concerne la polyédricité du cône dual.

Corollaire 2 (dual d'un polyèdre convexe) — Soit P un polyèdre convexe d'un espace euclidien \mathbb{E}. Alors P^+ est un polyèdre convexe.

Le troisième corollaire donne une règle de calcul du cône dual d'une intersection.

Corollaire 3 (dual d'une intersection) — Si K_i, i\in[\![1,m]\!], sont des cônes convexes fermés d'un espace euclidien \mathbb{E}, alors


(K_1\cap\cdots\cap K_m)^+=\overline{K_1^++\cdots+K_m^+}.

On peut enlever l'adhérence si les K_i sont polyédriques ou si (\operatorname{intr}K_1)\cap\cdots\cap (\operatorname{intr}K_m)\ne\varnothing.

On ne peut pas se passer de l'adhérence dans le résultat précédent, même si K_1\cap(\operatorname{intr}K_2)\cap\cdots\cap (\operatorname{intr}K_m)\ne\varnothing. Par exemple, dans \R^3, si m=2, si K_1 est le cornet \R^3_\triangledown et si K_2=\{x\in\R^3:x_2=x_3\}, alors K_1^+=\R^3_\triangledown (autodualité du cornet), K_2^+=\{d\in\R^3:d_1=0, d_2+d_3=0\}, K_1\cap (\operatorname{intr}K_2)=K_1\cap K_2=\{x\in\R^3:x_1=0, x_2=x_3\geq0\}\ne\varnothing, alors que K_2^++K_3^+=\{d:d_2+d_3>0\}\cup \{d\in\R^3:d_1=0, d_2+d_3=0\} n'est pas fermé.

Aspects topologiques[modifier | modifier le code]

Intérieur et intérieur relatif du cône dual — Soient \mathbb{E} un espace euclidien (produit scalaire et norme associés notés \langle\cdot,\cdot\rangle et \|\cdot\| respectivement), P\subset\mathbb{E} et P_{(\operatorname{aff} P^+)} le projecteur orthogonal sur le sous-espace vectoriel \operatorname{aff} P^+, qui est l'enveloppe affine du cône dual P^+ de 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{intr} 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[modifier | modifier le code]

Clairement, si x\in\R^n, on peut écrire


x=x^++x^-,

x^+:=\max(0,x) (composante par composante) et x^-:=\min(0,x) (composante par composante). On observe que x^+ est la projection orthogonale (pour le produit scalaire euclidien) de x sur \R^n_+ et que x^- est la projection orthogonale (pour le produit scalaire euclidien) de x sur \R^n_- (le cône dual négatif de \R^n_+). La décomposition de Moreau[2] généralise l'identité pour des cônes différents de l'orthant positif \R^n_+.

Décomposition de Moreau — Soient \mathbb{E} un espace euclidien dont le produit scalaire est noté \langle\cdot,\cdot\rangle, K un cône convexe fermé de \mathbb{E} et 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 \mathbb{E}, les propriétés suivantes sont équivalentes :

  1. z=x+y, x\in K, y\in K^- et \langle x,y\rangle=0,
  2. 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.

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. (en) J. B. Lasserre (1997). A Farkas lemma without a standard closure condition. SIAM Journal on Control and Optimization, 35, 265–272.
  2. J.-J. Moreau (1965). Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93, 273–299.

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) J.-B. Hiriart-Urruty, C. Lemaréchal (2001). Fundamentals of convex analysis. Springer-Verlag, Berlin.
  • (en) R.T. Rockafellar (1970). Convex Analysis. Princeton Mathematics Ser. 28. Princeton University Press, Princeton, New Jersey.