Cône tangent

En analyse convexe, le cône tangent au sens de Bouligand, ou cône contingent, est une certaine approximation au premier ordre d'un ensemble en un point, comme l'application dérivée d'une fonction est son approximation au premier ordre en un point. Cette notion est par exemple utilisée pour établir les conditions d'optimalité du premier ordre des problèmes d'optimisation de dimension finie.

Notations

Dans tout cet article, $E$ désigne un espace vectoriel réel — topologique si nécessaire (si $E$ est de dimension finie, on le suppose muni de sa topologie usuelle) — $X$ une partie non vide de $E$ et $x$ un point de $E$. On note :

• $\Lambda X:=\{\lambda x\mid \lambda \in \Lambda ,x\in X\}$, pour tout $\Lambda \subset \mathbb {R}$ (lorsque $X=\{x\}$, on utilise la notation simplifiée $\Lambda x:=\Lambda \{x\}$). $X$ est donc un cône si $\mathbb {R} _{+}^{*}X\subset X$.
• ${\overline {X}}$ l'adhérence de $X$ ;
• $\operatorname {aff} X$ son enveloppe affine, $\operatorname {ir} X$ son intérieur relatif et $\partial _{\rm {rel}}X={\overline {X}}\setminus \operatorname {ir} X$ sa frontière relative ;
• si $X$ est un sous-espace affine : ${\overrightarrow {X}}$ sa direction.

On note en outre :

• $\operatorname {Im} f$ l'image d'une application $f$ ;
• $\operatorname {Ker} f$ le noyau d'une application linéaire $f$ ;

Cône des directions admissibles

Le cône des directions admissibles, ou cône radial de $X$ en $x$, noté $\operatorname {R} _{X}(x)$, est défini par

$\operatorname {R} _{X}(x):=\{d\in E\mid x+td\in X$ pour tout réel $t>0$ petit$\}.$

Ce cône est donc vide si $x\notin \operatorname {aff} X$, et égal à ${\overrightarrow {\operatorname {aff} X}}$ tout entier dès que $X-x$ est une partie absorbante de ce sous-espace.

Cône tangent

Comme pour le calcul de la dérivée d'une fonction, la définition des directions tangentes qui sont les éléments du cône tangent requiert un passage à la limite. Il n'est pas satisfaisant en effet de prendre le cône des directions admissibles comme cône tangent à $X$ en $x$. Par exemple, le cône des directions admissibles à un cercle de $\mathbb {R} ^{2}$ est vide en tout point, si bien que l'on ne retrouve pas, avec cette notion, celle des directions tangentes connue, aussi il en faut une nouvelle :

Direction tangente et cône tangent, au sens de Bouligand — Le cône tangent, ou ensemble des directions tangentes (au sens de Bouligand) à $X\subset E$ en $x\in E$, noté $\operatorname {T} _{X}(x)$ (ou parfois $\operatorname {T} (X,x)$), est défini par :

$\operatorname {T} _{X}(x):=\cap _{\varepsilon >0}{\overline {\left]1/\varepsilon ,+\infty \right[\;(X-x)}}$.

Il résulte de cette définition que $\operatorname {T} _{X}(x)$ :

• est un cône fermé inclus dans l'adhérence de ${\overrightarrow {\operatorname {aff} X}}$ ;
• est égal à cette adhérence dès que $x\in \operatorname {ir} X$ (puisque $\operatorname {R} _{X}(x)\subset \operatorname {T} _{X}(x)$) ;
• est vide si $x\notin {\overline {X}}$ (donc n'a d'intérêt que si $x\in \partial _{\rm {rel}}X$) ;
• est inchangé lorsqu'on remplace $X$ par ${\overline {X}}$ ;
• commute aux réunions finies, c'est-à-dire : $\operatorname {T} _{X\cup Y}(x)=\operatorname {T} _{X}(x)\cup \operatorname {T} _{Y}(x)$ (pour toute partie $Y$ de $E$) ;
• est donc une fonction croissante de $X$, c'est-à-dire : $X\subset Y\Rightarrow \operatorname {T} _{X}(x)\subset \operatorname {Y} _{Y}(x)$, ce qui s'écrit aussi, par exemple : $\operatorname {T} _{\cap _{i\in I}X_{i}}(x)\subset \cap _{i\in I}\operatorname {T} _{X_{i}}(x)$ (pour toute famille non vide $(X_{i})_{i\in I}$ de parties de $E$).

Lorsque $E$ est à bases dénombrables de voisinages, par exemple lorsque c'est un espace vectoriel normé, l'adhérence d'une partie de $E$ se réduit à sa fermeture séquentielle, et la définition du cône tangent se traduit alors par :

$d\in \operatorname {T} _{X}(x)$ s'il existe des suites $\{t_{k}\}\subset \mathbb {R}$ et $\{x_{k}\}$ telles que

$\{x_{k}\}\subset X,\qquad t_{k}\to 0^{+}\qquad {\mbox{et}}\qquad {\frac {x_{k}-x}{t_{k}}}\to d$

ou encore, s'il existe des suites $\{t_{k}\}\subset \mathbb {R}$ et $\{d_{k}\}\subset E$ telles que

$x+t_{k}d_{k}\in X,\qquad t_{k}\to 0^{+}\qquad {\mbox{et}}\qquad d_{k}\to d.$

Autrement dit, $d\in \operatorname {T} _{X}(x)$ s'il existe une suite de vecteurs $d_{k}\in E$ convergeant vers $d$, telle que $x+\mathbb {R} _{+}^{*}d_{k}$ rencontre $X$ en des points de plus en plus proches de $x$ lorsque $k\to \infty$.

Cône normal

Pour définir le cône normal, on a besoin d'un produit scalaire sur $E$. On suppose donc que $E$ est un espace préhilbertien et l'on note $\langle \cdot ,\cdot \rangle$ son produit scalaire.

Vecteur normal, cône normal — Le cône normal, ou ensemble des vecteurs normaux à $X$ en $x\in {\overline {X}}$, noté $\operatorname {N} _{X}(x)$, est le cône dual négatif du cône tangent : $\operatorname {N} _{X}(x):=-{\operatorname {T} _{X}(x)}^{*}$ :

$p\in \operatorname {N} _{X}(x)\Leftrightarrow \forall d\in \operatorname {T} _{X}(x)\quad \langle p,d\rangle \leqslant 0.$

Par conséquent, $\operatorname {N} _{X}(x)$ est un cône convexe fermé.

Exemple

Soit $X$ le cône (non convexe) $(\mathbb {R} _{+}\times \{0\})\cup (\{0\}\times \mathbb {R} _{+})$. Alors, $\operatorname {T} _{X}(0)=X$ donc $\operatorname {N} _{X}(0)=\mathbb {R} _{-}\times \mathbb {R} _{-}$.

Cas d'un convexe

Dans le cas où l'ensemble est convexe, le calcul du cône tangent et du cône normal se simplifient.

Cônes tangent et normal à un convexe — Dans un espace vectoriel topologique $E$, soit $x$ un point de l'adhérence d'un convexe $C$. Alors :

• $\operatorname {T} _{C}(x)={\overline {\mathbb {R} _{+}(C-x)}}$ ;
• $\operatorname {N} _{C}(x)=-(C-x)^{*}$ et $\operatorname {T} _{C}(x)=-\operatorname {N} _{C}(x)^{*}$, en supposant que $E$ est préhilbertien.

Transport affine des cônes tangent et normal à un convexe : image directe — Soient $E$ et $F$ deux espaces vectoriels topologiques, $a:E\to F:x\mapsto Ax+b$ une application affine continue ($A:E\to F$ est linéaire continue et $b\in F$), et $x$ un point de l'adhérence d'un convexe $C\subset E$.

1. $\operatorname {T} _{a(C)}{(a(x))}={\overline {A[\operatorname {T} _{C}{(x)}]}}$ ;
2. $\operatorname {N} _{a(C)}{(a(x))}=(A^{*})^{-1}[\operatorname {N} _{C}(x)]$, en supposant que $E$ est hilbertien et $F$ préhilbertien, et en notant $A^{*}$ l'adjoint de $A$.

Démonstration

On se ramène facilement par translation au cas où $b=0$ (donc $a=A$) et $x=0$ (donc $A(x)=0$).

1. $\operatorname {T} _{A(C)}{(0)}={\overline {\mathbb {R} _{+}A(C)}}={\overline {A(\mathbb {R} _{+}C)}}={\overline {A({\overline {\mathbb {R} _{+}C}})}}={\overline {A[\operatorname {T} _{C}{(0)}]}}$. L'adhérence est ici nécessaire, puisque par exemple (voir infra) si $C$ est un cône convexe fermé alors $\operatorname {T} _{C}{(0)}=C$ et $A(C)$ n'est pas nécessairement fermé ;
2. $\operatorname {N} _{A(C)}{(0)}=-A(C)^{*}=-(A^{*})^{-1}(C^{*})=(A^{*})^{-1}[\operatorname {N} _{C}(0)]$.

Cas d'un convexe en dimension finie

En dimension finie, grâce à l'existence d'hyperplans d'appui, on déduit de l'expression ci-dessus de $\operatorname {N} _{C}(x)$ :

Vecteur non nul normal à un convexe — Dans un espace euclidien, soit $x$ un point de la frontière relative d'un convexe $C$. Alors, $\operatorname {N} _{C}(x)\cap {\overrightarrow {\operatorname {aff} (C)}}$ contient un vecteur non nul.

Le transport affine par image réciproque est moins classique que celui (ci-dessus) par image directe, et nécessite plus de précautions :

Transport affine des cônes tangent et normal à un convexe : image réciproque^{[réf. nécessaire]} — Soient $E$ et $F$ deux espaces euclidiens, $a:E\to F:x\mapsto Ax+b$ une application affine, $A^{*}$ l'adjoint de $A$, $D\subset F$ un convexe, et $x\in {\overline {a^{-1}(D)}}$.

1. $\operatorname {N} _{a^{-1}(D)}{(x)}=A^{*}[\operatorname {N} _{D\cap \operatorname {Im} a}(a(x))]$. En particulier, l'ensemble $A^{*}[\operatorname {N} _{D\cap \operatorname {Im} a}(a(x))]$ est fermé ;
2. $\operatorname {T} _{a^{-1}(D)}{(x)}=A^{-1}[\operatorname {T} _{D\cap \operatorname {Im} a}(a(x))]$.

Démonstration

Comme précédemment, supposons sans perte de généralité que $b=0$ et $x=0$.

1. Puisque ${\overline {A^{-1}(D)}}$ est stable par translation par $\operatorname {Ker} A$ et (par hypothèse) contient $0$, il contient $\operatorname {Ker} A$, donc son dual $A^{-1}(D)^{*}$ est inclus dans $(\operatorname {Ker} A)^{*}=\operatorname {Im} {(A^{*})}$. Par conséquent, $\operatorname {N} _{A^{-1}(D)}{(0)}=-A^{-1}(D)^{*}=-A^{-1}(D)^{*}\cap \operatorname {Im} {(A^{*})}=-A^{*}[(D\cap \operatorname {Im} A)^{*}]=A^{*}[\operatorname {N} _{D\cap \operatorname {Im} A}(0)]$. La fermeture de cet ensemble peut paraître surprenante car (voir infra) l'image par une application linéaire d'un cône convexe fermé n'est pas nécessairement fermée. En guise de certification, voici une autre preuve de ce fait. On sait que l'image par l'application linéaire $A^{*}$ d'une partie $K\subset F$ est fermée si et seulement si $K+\operatorname {Ker} {(A^{*})}$ est fermé. Dans le cas présent, $K:=\operatorname {N} _{D\cap \operatorname {Im} A}(0)=-\left(D\cap \operatorname {Im} A\right)^{*}$ est un cône convexe fermé qui contient $(\operatorname {Im} A)^{*}=\operatorname {Ker} {(A^{*})}$, si bien que $K+\operatorname {Ker} {(A^{*})}=K$ est fermé ;
2. $\operatorname {T} _{A^{-1}(D)}{(0)}=-[\operatorname {N} _{A^{-1}(D)}{(0)}]^{*}=-[A^{*}[\operatorname {N} _{D\cap \operatorname {Im} A}(0)]]^{*}=A^{-1}[-[\operatorname {N} _{D\cap \operatorname {Im} A}(0)]^{*}]=A^{-1}[\operatorname {T} _{D\cap \operatorname {Im} A}(0)]$.

Exemples

Polyèdre convexe

Soit $P$ un polyèdre convexe de $\mathbb {R} ^{n}$, que l'on suppose donné comme une intersection d'un nombre fini de demi-espaces :

$P:=\{x\in \mathbb {R} ^{n}\mid Ax\leqslant b\}$,

où $A$ est une matrice de type $m\times n$, $b\in \mathbb {R} ^{m}$ et l'inégalité est entendue composante par composante : $(Ax)_{i}\leqslant b_{i}$ pour tout $i\in \{1,\ldots ,m\}$. On note pour un point $x\in P$ :

$I(x):=\{i\in \mathbb {N} \mid 1\leqslant i\leqslant m,~(Ax-b)_{i}=0\}$.

Alors les cônes tangent et normal en $x\in P$ s'écrivent

$\operatorname {T} _{P}(x)=\operatorname {R} _{P}(x)=\{d\in \mathbb {R} ^{n}\mid (Ad)_{I(x)}\leqslant 0\}\quad {\text{et}}\quad \operatorname {N} _{P}(x)=\operatorname {cone} \{A_{i}^{\!\top \!}\mid i\in I(x)\}$,

où $A_{i}^{\!\top \!}\in \mathbb {R} ^{n}$ est le vecteur formé par la ligne $i$ de $A$ et « $\operatorname {cone}$ » désigne l'opérateur qui prend l'enveloppe conique d'un ensemble (le plus petit cône convexe pointé contenant l'ensemble). Pour l'écriture du cône normal, on a supposé que $\mathbb {R} ^{n}$ était muni du produit scalaire euclidien.

Cône convexe fermé

Soient $C$ un cône convexe fermé d'un espace euclidien et $x\in C$. Alors,

$\operatorname {N} _{C}(x)=(-C^{*})\cap (x^{\bot })\quad {\text{donc}}\quad \operatorname {T} _{C}(x)={\overline {C+\mathbb {R} x}}$,

en particulier, $\operatorname {N} _{C}(0)=-C^{*}$ et $\operatorname {T} _{C}(0)=C$.

Remarquons que $C+\mathbb {R} x$ n'est pas toujours fermé (donc l'image d'un cône convexe fermé $C\times D$ par l'application linéaire $+$ n'est pas toujours fermée). Par exemple, dans l'espace $\mathbb {S} ^{n}$ des matrices symétriques réelles d'ordre $n$, muni du produit scalaire usuel ($\langle A,B\rangle :=\operatorname {tr} (AB)$ où $\operatorname {tr}$ désigne la trace), soit $\mathbb {S} _{+}^{n}$ le cône (autodual) de celles qui sont positives. Les cônes normal et tangent à $\mathbb {S} _{+}^{n}$ en $A\in \mathbb {S} _{+}^{n}$ s'écrivent

$\operatorname {N} _{\mathbb {S} _{+}^{n}}{(A)}=(-\mathbb {S} _{+}^{n})\cap (A^{\bot })\quad {\text{et}}\quad \operatorname {T} _{\mathbb {S} _{+}^{n}}{(A)}=\{D\in \mathbb {S} ^{n}\mid \forall v\in \operatorname {Ker} A\;\;v^{\!\top \!}Dv\geqslant 0\}.$

Ainsi pour $A={\begin{pmatrix}1&0\\0&0\end{pmatrix}}$, $\mathbb {S} _{+}^{2}+\mathbb {R} A=\left\{\left.{\begin{pmatrix}a&b\\b&c\end{pmatrix}}\in \mathbb {S} ^{2}~\right|~(b=c=0)\quad {\text{ou}}\quad c>0\right\}$ et $\operatorname {T} _{\mathbb {S} _{+}^{2}}{(A)}=\left\{\left.{\begin{pmatrix}a&b\\b&c\end{pmatrix}}\in \mathbb {S} ^{2}~\right|~c\geq 0\right\}$.

Qualification de contraintes

Un ensemble peut être représenté au moyen de fonctions. Par exemple, on peut utiliser des contraintes d'égalité et d'inégalité comme ci-dessous

$X=\{x\in E\mid c_{E}(x)=0,c_{I}(x)\leqslant 0\},$

où les contraintes d'égalité sont définies au moyen de la fonction $c_{E}:E\to \mathbb {R} ^{m_{E}}$ et les contraintes d'inégalité sont définies au moyen de la fonction $c_{I}:E\to \mathbb {R} ^{m_{I}}$. L'inégalité vectorielle $c_{I}(x)\leqslant 0$ doit ici être entendue composante par composante. On note $E$ l'ensemble des indices des contraintes d'égalité, qui s'écrivent donc aussi $c_{i}(x)=0$ pour tout indice $i\in E$. De même pour l'ensemble $I$ des contraintes d'inégalité.

Se pose alors la question de savoir calculer le cône tangent en un point $x$ à partir des dérivées premières des fonctions $c_{E}$ et $c_{I}$ en $x$.

Il est naturel de s'intéresser à l'expression suivante obtenue en linéarisant les fonctions $c_{E}$ et $c_{I}$ en $x$ :

$\operatorname {T} '_{X}(x):=\{d\in E\mid c'_{E}(x)\cdot d=0,\;c'_{I^{0}(x)}(x)\cdot d\leqslant 0\},$

où l'on a noté

$I^{0}(x):=\{i\in I\mid c_{i}(x)=0\}.$

On peut montrer que, sous des hypothèses raisonnables, on a toujours

$\operatorname {T} _{X}(x)\subset \operatorname {T} '_{X}(x).$

On aimerait avoir égalité pour pouvoir calculer le cône tangent par une formule explicite, mais cette égalité n'est pas toujours vérifiée. On dit que les contraintes (on devrait dire les fonctions définissant les contraintes) $c_{E}$ et $c_{I}$ sont qualifiées en $x$ si $\operatorname {T} _{X}(x)=\operatorname {T} '_{X}(x).$ Comme $\operatorname {T} _{X}(x)$ ne dépend que de l'ensemble $X$, pas des fonctions $c_{E}$ et $c_{I}$, il s'agit d'une notion assurant que la représentation de $X$ par $c_{E}$ et $c_{I}$ convient.

Annexes

Bibliographie

• (en) J. F. Bonnans et A. Shapiro, Perturbation Analysis of Optimization Problems, New York, Springer, 2000 (lire en ligne)
• J.-B. Hiriart-Urruty, Optimisation et analyse convexe, EDP Sciences, 2009 (1^re éd. 1998, PUF) (lire en ligne)
• (en) J.-B. Hiriart-Urruty et C. Lemaréchal, Convex Analysis and Minimization Algorithms, vol. 1, Springer, coll. « Grund. math. Wiss. » (n^o 305), 1993 (lire en ligne), p. 133-142
• (en) J.-B. Hiriart-Urruty et C. Lemaréchal, Fundamentals of Convex Analysis, Springer, 2004 (1^re éd. 2001) (lire en ligne)
• (en) Johannes Jahn, Introduction to the Theory of Nonlinear Optimization, Springer, 2007, 3^e éd. (1^re éd. 1994), chap. 4 (« Tangent Cones »), p. 79-104
• (en) Akhtar A. Khan, Christiane Tammer et Constantin Zălinescu, Set-valued Optimization: An Introduction with Applications, Springer, 2015 (lire en ligne)
• (en) R. T. Rockafellar, « Lagrange Multipliers and Optimality », SIAM Review, vol. 35,‎ 1993, p. 183-238 (lire en ligne)

Lien externe

J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris