Sous-différentiel

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

En mathématiques, et plus précisément en analyse convexe, le sous-différentiel est un concept permettant de décrire la variation locale d'une fonction convexe (à valeurs réelles donc) non nécessairement différentiable dans un sens classique, celui auquel on attache aujourd'hui le nom de Fréchet. Au lieu d'être la pente de l'application linéaire tangente (c'est-à-dire, la dérivée) au point considéré, qui n'existe pas nécessairement, le sous-différentiel d'une fonction convexe est l'ensemble des pentes de toutes les minorantes affines de la fonction, qui sont exactes en ce point, c'est-à-dire qui ont en ce point la même valeur que la fonction convexe qu'elles minorent. Dans cette description le mot pente peut être entendu comme un élément de l'espace dual. La convexité de la fonction assure qu'on peut lui trouver des minorantes affines exactes en presque tout point de son domaine ; on met donc à profit cette propriété pour définir le sous-différentiel. Si l'on peut trouver une minorante affine exacte en un point donné, on dit que la fonction convexe est sous-différentiable en ce point.

On sait que la notion de dérivée est fondamentale en analyse car elle permet d'approcher localement des fonctions par des modèles linéaires, plus simples à étudier. Ces modèles fournissent des renseignements sur les fonctions qu'ils approchent, si bien que de nombreuses questions d'analyse passent par l'étude des fonctions linéarisées (stabilité, inversibilité locale, etc). On rencontre beaucoup de fonctions convexes qui ne sont pas différentiables au sens classique, en particulier lorsque celles-ci résultent de constructions qui n'ont rien pour assurer la différentiabilité des fonctions qu'elles produisent. Il en est ainsi de la fonction duale associée à un problème d'optimisation sous contraintes, pour en citer un exemple emblématique. Pour ces fonctions convexes non lisses, le sous-différentiel joue donc un rôle similaire à celui de la dérivée des fonctions plus régulières.

La notion de sous-différentiel connaît diverses extensions aux fonctions non nécessairement convexes, par exemple aux fonctions localement lipschitziennes[1].

Connaissances supposées : l'algèbre linéaire, le calcul différentiel (notamment les propriétés de la dérivée directionnelle au sens de Dini pour les fonctions convexes prenant des valeurs infinies), les bases de l'analyse convexe (notamment les principales notions attachées aux ensembles et aux fonctions convexes, mais surtout la notion de fonction conjuguée).

Fonction d'une seule variable[modifier | modifier le code]

Définition[modifier | modifier le code]

une fonction convexe (en bleu) et les "lignes sous-tangentes" en x_0 (rouge).

De manière rigoureuse, une sous-dérivée d'une fonction convexe f:I\to\R en un point x_0 de l'intervalle ouvert I est un nombre réel s tel que


f(x) \geqslant f(x_0) + s(x-x_0),

pour tout x dans I. On peut montrer que l'ensemble des sous-dérivées en x_0 est un ensemble non vide et un intervalle fermé de la forme [a,b], avec a et b les bornes :


\begin{array}{rcl}
a&=&\lim_{x\to x_0^-}\frac{f(x)-f(x_0)}{x-x_0},\\
b&=&\lim_{x\to x_0^+}\frac{f(x)-f(x_0)}{x-x_0},
\end{array}

que l'on sait exister et vérifier a\leqslant b.

L'ensemble [a,b] de toutes les sous-dérivées est appelé le sous-différentiel de la fonction f en x_0.

Exemples[modifier | modifier le code]

Considérons la fonction f(x)=|x| qui est convexe. Alors, le sous-différentiel à l'origine est l'intervalle [−1, 1]. Le sous-différentiel en n'importe quel point x0<0 est le singleton {−1} et le sous-différentiel en n'importe quel point x0>0 est le singleton {1}.

Propriétés[modifier | modifier le code]

  • Une fonction convexe f:IR est différentiable en x0 si et seulement si le sous-différentiel ne contient qu'un seul point, qui est alors la dérivée de f en x0.
  • Un point x0 est un minimum local de f si et seulement si zéro est contenu dans le sous-différentiel, c'est-à-dire, dans la figure ci-dessus, on peut tracer une droite horizontale "sous-tangente" au graphe de f en (x0, f(x0)). La dernière propriété est une généralisation du fait que la dérivée d'une fonction dérivable en un minimum local est nulle.

Fonction définie sur un espace euclidien[modifier | modifier le code]

On suppose dans cette section que \mathbb{E} est un espace euclidien (de dimension finie donc) dont le produit scalaire est noté \langle\cdot,\cdot\rangle et la norme associée \|\cdot\|. On note par ailleurs

Définition[modifier | modifier le code]

La notion de sous-différentiel peut être généralisée à une fonction convexe de plusieurs variables réelles, pouvant également prendre la valeur +\infty. Cette dernière extension trouve son utilité, par exemple en optimisation, lorsque la fonction résulte d'une construction qui n'assure pas a priori la finitude des valeurs qu'elle prend. Comme pour la notion de gradient, on a besoin que l'espace sur lequel est définie la fonction soit muni d'un produit scalaire si l'on veut construire des objets dans cet espace et non dans son dual. Les concepts seront mieux révélés en travaillant sur un espace euclidien abstrait, qui pourra, si on le souhaite, être vu comme \R^n muni du produit scalaire euclidien.

Sous-gradient — Soit f : \mathbb{E}\to\R\cup\{+\infty\}, une fonction convexe et propre. On dit que s\in\mathbb{E} est un sous-gradient de f en x\in\operatorname{dom}\,f si l'une des propriétés équivalentes suivantes est vérifiée :

  1. \forall\,d\in\mathbb{E},~f'(x;d)\geqslant \langle s,d\rangle,
  2. \forall\,y\in\mathbb{E},~f(y)\geqslant f(x) + \langle s, y-x\rangle,
  3. x minimise y\in\mathbb{E}\mapsto f(y)-\langle s,y\rangle,
  4. f^*(s) + f(x) \leqslant \langle s, x\rangle,
  5. f^*(s) + f(x) = \langle s, x\rangle.

La lettre s renvoie à slope (pente) ou sous-gradient (si l'on préfère). La propriété 1 exprime le fait que la fonction d\in\mathbb{E}\mapsto \langle s, d\rangle est une minorante linéaire de la fonction dérivée directionnelle f'(x;\cdot) : d\in\mathbb{E}\mapsto f'(x;d)\in\R\cup\{\pm\infty\} (que l'on sait toujours exister lorsque f est convexe), exacte en 0. La propriété 2 exprime le fait que la fonction y\in\mathbb{E}\mapsto f(x) + \langle s, y-x\rangle est une minorante affine de f exacte en x. Les propriétés 4 et 5 expriment la même chose que la propriété 2 en utilisant la fonction conjuguée f^* de f.

Sous-différentiel — L'ensemble des sous-gradients de f en x est appelé le sous-différentiel de f en x. Il est noté


\partial f(x).

On dit que f est sous-différentiable en x si \partial f(x)\ne\varnothing. Par convention, \partial f(x)=\varnothing si x\notin\operatorname{dom}\,f.

Propriétés[modifier | modifier le code]

Optimalité[modifier | modifier le code]

La propriété 2 de la définition du sous-différentiel permet d'obtenir immédiatement une expression simple de l'optimalité d'un point.

Condition d'optimalité — Soit f\in\operatorname{Conv}(\mathbb{E}). Un point \bar{x}\in\mathbb{E} minimise f sur \mathbb{E} si, et seulement si, 0\in\partial f(\bar{x}).

Cette condition nécessaire et suffisante d'optimalité du premier ordre (ainsi qualifiée parce qu'elle ne fait intervenir que les « dérivées » premières de la fonction) est typique des problèmes d'optimisation convexes (voir la section Conditions du premier ordre sans contrainte de l'article Conditions d'optimalité).

Trouver les minimiseurs d'une fonction convexe propre revient donc à trouver les « zéros » de son sous-différentiel. Ce résultat est à rapprocher de celui selon lequel les minimiseurs d'une fonction convexe différentiable sont les points qui annulent son gradient. Ce résultat est plus riche qu'il ne paraît à première vue. En effet, du fait que la fonction peut prendre la valeur +\infty, il traite également de la minimisation d'une fonction convexe sous contraintes convexes (l'ensemble admissible étant le domaine de la fonction).

Sous-différentiabilité[modifier | modifier le code]

Rappelons que l'on dit que f\in\operatorname{Conv}(\mathbb{E}) est sous-différentiable en x\in\operatorname{dom}\,f si \partial f(x)\ne\varnothing. Affirmer qu'un ensemble est non vide est une propriété forte qui, dans certains cas, revient à montrer qu'un certain problème a une solution.

La propriété 1 définissant un sous-gradient s, à savoir


\forall\,d\in\mathbb{E},\quad f'(x;d)\geqslant \langle s,d\rangle,

montre clairement que f ne peut être sous-différentiable en x si la dérivée directionnelle f'(x;\cdot) prend en une direction la valeur -\infty puisque le membre de droite de l'inégalité ci-dessus est toujours fini. La réciproque de cette observation est le sujet de la proposition qui suit. Une telle situation se présente pour la fonction convexe définie par


f(x)=
\left\{\begin{array}{ll}
-\sqrt{x} & \mbox{si}~ x\geqslant 0 \\
+\infty & \mbox{sinon}.
\end{array}\right.

Cette fonction n'est pas sous-différentiable en zéro, parce que f'(0;1)=-\infty. Évidemment, si f'(x;d)=-\infty, alors f'(x;-d)=+\infty, mais ce n'est pas la valeur +\infty de la dérivée directionnelle qui empêche f d'être sous-différentiable en x. C'est ce que montre la fonction indicatrice de l'intervalle [0,+\infty[, dont le sous-différentiel en zéro est l'intevalle {]-\infty,0]}.

Sous-différentiabilité — Si f\in\operatorname{Conv}(\mathbb{E}) et x\in\mathbb{E}, les propriétés suivantes sont équivalentes :

  1. f est sous-différentiable en x,
  2. il existe y\in\operatorname{intr}\,(\operatorname{dom}\,f) tel que f'(x;y-x)>-\infty,
  3. f'(x;\cdot) ne prend pas la valeur -\infty.

Ces propriétés sont vérifiées si x\in\operatorname{intr}\,(\operatorname{dom}\,f).

Propriétés géométriques et topologiques[modifier | modifier le code]

On note ci-dessous \operatorname{aff}\,P l'enveloppe affine d'une partie P\subset\mathbb{E}.

Propriétés géométriques et topologiques du sous-différentiel — Soient f\in\operatorname{Conv}(\mathbb{E}), \mathbb{E}_0 le sous-espace vectoriel parallèle à \operatorname{aff}\,(\operatorname{dom}\, f), P_{\mathbb{E}_0} le projecteur orthogonal sur \mathbb{E}_0 et x\in\operatorname{dom}\, f. On note f|_{x+\mathbb{E}_0} la restriction de f à x+\mathbb{E}_0= \operatorname{aff}\,(\operatorname{dom}\, f). Alors

  1. \partial f(x)=\partial f|_{x+\mathbb{E}_0}(x)+\mathbb{E}_0^\perp, en particulier P_{\mathbb{E}_0}\partial f(x)=\partial f|_{x+\mathbb{E}_0}(x),
  2. \partial f(x) est convexe et fermé (éventuellement vide),
  3. x\in\operatorname{intr}\,(\operatorname{dom}\, f) ~\Longleftrightarrow~ P_{\mathbb{E}_0}\partial f(x) est non vide et borné,
  4. x\in\operatorname{int}\,(\operatorname{dom}\, f) ~\Longleftrightarrow~ \partial f(x) est non vide et borné.

Si f ne prend que des valeurs réelles, alors \operatorname{dom}\, f=\mathbb{E} et son sous-différentiel est un ensemble non vide, convexe et compact (par les points 2 et 4).

Formule du max[modifier | modifier le code]

Le sous-différentiel peut être défini en utilisant la dérivée directionnelle (propriété 1 de la définition). La proposition suivante montre que l'on peut retrouver les dérivées directionnelles à partir du sous-différentiel : f'(x;\cdot) est la fonction d'appui de \partial f(x).

Formule du max — Si f\in\operatorname{Conv}(\mathbb{E}) et x\in\operatorname{intr}\,(\operatorname{dom}\,f), alors


\forall\,d\in \mathbb{E}:\qquad
f'(x;d)=\sup_{s\in\partial f(x)}\,\langle s,d\rangle.

Le supremum est atteint si f'(x;d)<+\infty.

Le résultat précédent ne tient plus si x est sur la frontière relative du domaine de f. Voici un contre-exemple : f est l'indicatrice de la boule-unité fermée de \R^2, pour la norme euclidienne, et x=(-1,0). Alors f'(x;0)=0 et si d\ne0 :


f'(x;d)=
\left\{\begin{array}{lll}
0 & \mbox{si} & d_1>0 \\
+\infty & \mbox{si} & d_1\leqslant 0.
\end{array}\right.

Dès lors, la fonction \delta_x:d\mapsto f'(x;d) n'est pas fermée et ne peut donc être la fonction d'appui d'un ensemble, en particulier elle n'est pas la fonction d'appui du sous-différentiel. D'ailleurs, ce dernier s'écrit \partial f(x)=\{s\in\R^2:s_1\leqslant 0,~s_2=0\} et


\sigma_{\partial f(x)}(d)=
\left\{\begin{array}{lll}
0 & \mbox{si} & d_1\geqslant 0 \\
+\infty & \mbox{si} & d_1<0
\end{array}\right.

est l'enveloppe convexe fermée de \delta_x. Cette propriété est tout à fait générale pour les fonctions de \operatorname{C\overline{onv}}(\mathbb{E}).

La multifonction sous-différentiel[modifier | modifier le code]

On peut voir \partial f comme une multifonction ou fonction multivoque, qui à un élément de \mathbb{E} fait correspondre une partie de \mathbb{E}, c'est-à-dire un élément de l'ensemble \mathcal{P}(\mathbb{E}) des parties de \mathbb{E}. On note


\partial f:\mathbb{E}\multimap \mathbb{E}:x\mapsto\partial f(x)

cette correspondance.

Rappelons quelques notions d'analyse multifonctionnelle. Soit \varphi:\mathbb{E}\multimap \mathbb{F} une multifonction. On définit le domaine, l'image et le graphe de \varphi respectivement par


\begin{array}{rcl}
\operatorname{dom}\,\varphi &:=& \{x\in \mathbb{E}:\varphi(x)\ne\varnothing\},
\\
\mathcal{R}(\varphi) &:=& \cup\{\varphi(x):x\in\operatorname{dom}\,\varphi\},
\\
\mathcal{G}(\varphi) &:=& \{(x,u)\in \mathbb{E}\times \mathbb{F}:u\in\varphi(x)\}.
\end{array}

On notera bien que l'on a choisi de définir le graphe comme une partie de \mathbb{E}\times \mathbb{F} et pas de \mathbb{E}\times\mathcal{P}(\mathbb{F}). La multifonction réciproque \varphi^{-1}:\mathbb{F}\multimap \mathbb{E} de la multifonction \varphi:\mathbb{E}\multimap \mathbb{F} est définie en u\in \mathbb{F} par


\varphi^{-1}(u)=\{x\in \mathbb{E}:u\in \varphi(x)\}.

Lorsque \mathbb{E} est un espace euclidien dont le produit scalaire est noté \langle \cdot,\cdot\rangle et que \mathbb{F}=\mathbb{E}, on dit que \varphi est monotone si


\forall\,(x,u)\in\mathcal{G}(\varphi),~~
\forall\,(y,v)\in\mathcal{G}(\varphi):\qquad
\langle v-u,y-x\rangle\geqslant 0.

On dit que \varphi est monotone maximale si \varphi est monotone et si son graphe n'est pas strictement contenu dans le graphe d'un opérateur monotone. On vérifie facilement que cette dernière propriété s'écrit aussi


\Bigl[\langle v-u,y-x\rangle\geqslant 0,\quad\forall\,(x,u)\in\mathcal{G}(\varphi)\Bigr]
\quad\Longrightarrow\quad
(y,v)\in\mathcal{G}(\varphi).

Dans le résultat ci-dessous, on note f^* la conjuguée de f.

La multifonction sous-différentiel — Si f\in\operatorname{Conv}(\mathbb{E}), alors

  1. \operatorname{intr}\,(\operatorname{dom}\,f)\subset\operatorname{dom}\,\partial f\subset\operatorname{dom}\,f ;
  2. \mathcal{R}(\partial f)\subset\operatorname{dom}\,f^* ;
  3. \mathcal{G}(\partial f) est fermé ;
  4. la multifonction \partial f est monotone.

Si f\in\operatorname{C\overline{onv}}(\mathbb{E}), alors

  1. \operatorname{intr}\,(\operatorname{dom}\,f^*)\subset\mathcal{R}(\partial f) ;
  2. (\partial f)^{-1}=\partial f^* ;
  3. la multifonction \partial f est monotone maximale.

On rappelle que f:\mathbb{E}\to\R\cup\{+\infty\} est fortement convexe, de module \alpha>0, si pour tout x_0 et x_1\in\operatorname{dom}\,f et pour tout t\in[0,1]\subset\R, on a


f((1-t)x_0+tx_1)\leq(1-t)f(x_0)+tf(x_1)-\frac{\alpha}{2}\,t(1-t)\|x_0-x_1\|^2.

Rappelons aussi qu'une multifonction \varphi:\mathbb{E}\multimap \mathbb{F} est dit fortement monotone, de module \alpha>0, si


\forall\,(x,y)\in\mathcal{G}(\varphi),\quad
\forall\,(x',y')\in\mathcal{G}(\varphi):\qquad
\langle y-y',x-x'\rangle\geqslant\alpha\|x-x'\|^2.

La forte convexité de f peut s'exprimer par la forte monotonie de \partial f[2].

Sous-différentiel fortement monotone — Pour une fonction f:\mathbb{E}\to\R\cup\{+\infty\} et un réel \alpha>0, les propriétés suivantes sont équivalentes :

  1. f est fortement convexe de module \alpha,
  2. \partial f est fortement monotone de module \alpha,
  3. \forall\,(x,s)\in\mathcal{G}(\partial f) et \forall\,y\in\mathbb{E}, on a

    f(y)\geqslant f(x)+\langle s,y-x\rangle+\frac{\alpha}{2}\|y-x\|^2.

Lien avec la différentiabilité[modifier | modifier le code]

Rappelons les trois notions de différentiabilité d'une fonction f:\mathbb{E}\to\bar{\R} dont il est question dans cette section. On suppose que f est finie au point x où sont prises ces dérivées.

Ces trois propriétés sont de plus en plus fortes (la Fréchet-différentiabilité implique la Gâteaux-différentiabilité, qui implique elle-même la différentiabilité partielle). Pour une fonction convexe, les trois notions sont équivalentes[3], si bien qu'il n'y a alors pas lieu de faire de distinction entre celles-ci.

Gâteaux et Fréchet différentiabilité — Soient f\in\operatorname{Conv}(\mathbb{E}) et x\in(\operatorname{dom}\,f)^\circ. On note n la dimension de \operatorname{E}. Alors les propriétés suivantes sont équivalentes :

  1. f a des dérivées partielles en x suivant n directions linéairement indépendantes,
  2. f est Gâteaux-différentiable en x,
  3. f est Fréchet-différentiable en x.

Le résultat suivant[4] établit un lien entre la différentiabilité et la sous-différentiabilité : en bref, une fonction est différentiable en un point si, et seulement si, elle est sous-différentiable en ce point et son sous-différentiel est un singleton.

Différentiabilité et sous-différentiabilité — Soient f\in\operatorname{Conv}(\mathbb{E}) et x\in(\operatorname{dom}\,f)^\circ.

  1. Si f est différentiable en x, alors \partial f(x)=\{\nabla f(x)\}.
  2. Si \partial f(x) est le singleton \{D\}, alors f est différentiable en x et \nabla f(x)=D.

Limites des gradients convergents[modifier | modifier le code]

Calcul sous-différentiel[modifier | modifier le code]

Combinaison conique[modifier | modifier le code]

Voici une conséquence immédiate de la définition du sous-différentiel.

Multiplication par un scalaire positif — Soit \alpha\geqslant 0, f\in\operatorname{Conv}(\mathbb{E}) et x\in \mathbb{E}. Alors


\partial(\alpha f)(x)=\alpha\,\partial f(x).

On remarquera bien que le scalaire multiplie une fonction dans le membre de gauche de l'identité ci-dessus et un ensemble dans son membre de droite.

À l'inverse, comme le montrera un exemple ci-dessous, l'égalité entre le sous-différentiel de la somme de fonctions convexes et la somme des sous-différentiels n'est pas nécessairement assurée. On aura certainement l'égalité si toutes les fonctions ne prennent que des valeurs finies. On notera également que la somme se fait sur des fonctions dans le membre de gauche de l'identité et sur des ensembles dans celui de droite.

Sous-différentiel d'une somme — Soient f_1, \ldots, f_p\in\operatorname{Conv}(\mathbb{E}) et x\in \mathbb{E}. Alors


\partial(f_1+\cdots+f_p)(x)\supset
\partial f_1(x)+\cdots+\partial f_p(x),

avec égalité si


\bigcap_{1\leqslant i\leqslant p}\,\operatorname{intr}\,(\operatorname{dom}\, f_i)\ne\varnothing.

Dans cette dernière condition, on peut remplacer \operatorname{intr}\,(\operatorname{dom}\, f_i) par \operatorname{dom}\, f_i si f_i est polyédrique.

Voici un exemple où l'égalité n'est pas assurée dans la formule de la somme (f_2 est la fonction indicatrice de {]-\infty,0]}):


f_1:x\in\R\mapsto
\left\{\begin{array}{ll}
-\sqrt{x} & \mbox{si}~ x\geqslant 0 \\
+\infty & \mbox{sinon}
\end{array}\right.
\qquad\mbox{et}\qquad
f_2=\mathcal{I}_{]-\infty,0]}.

Comme la somme f=f_1+f_2 est l'indicatrice de \{0\}, on a \partial f(0)=\R, alors que \partial f_1(0)+\partial f_2(0)=\varnothing, parce que \partial f_1(0)=\varnothing.

Pré-composition par une fonction affine[modifier | modifier le code]

Le cadre est le suivant. On dispose d'une fonction affine a:\mathbb{E}\to\mathbb{F} entre deux espaces euclidiens \mathbb{E} et \mathbb{F}. Celle-ci est supposée être définie en x\in\mathbb{E} par


a(x)=Ax+b,

A:\mathbb{E}\to\mathbb{F} est linéaire et b\in \mathbb{F}. On note \mathcal{R}(a):=a(\mathbb{E}) l'Image directe de \mathbb{E} par a et A^* l'application linéaire adjointe de A pour les produits scalaires que l'on s'est donné sur \mathbb{E} et \mathbb{F}, défini donc par la relation


\forall\,x\in\mathbb{E},\quad
\forall\,y\in\mathbb{F}:\quad
\langle A^*y,x\rangle=
\langle y,Ax\rangle.

L'application affine a est composée avec une application g:\mathbb{F}\to\bar{\R}.

Sous-différentiel d'une pré-composition par une fonction affine — Dans le cadre défini ci-dessus, si g\in\operatorname{Conv}(\mathbb{F}), alors pour tout x\in \mathbb{E} :


\partial (g\circ a)(x)\supset A^*\Bigl(\partial g(a(x))\Bigr),

avec égalité si l'une des conditions suivantes est vérifiée :

Fonction marginale[modifier | modifier le code]

Soient \mathbb{E} et \mathbb{F} deux espaces euclidiens et \varphi:\mathbb{E}\times \mathbb{F}\to\bar{\R} une fonction. On associe à cette dernière la fonction marginale f:\mathbb{E}\to\bar{\R} définie par :


f(x)=\inf_{y\in \mathbb{F}}\varphi(x,y).

Le sous-différentiel de f dépend de celui de \varphi qui est supposé calculé pour le produit scalaire de \mathbb{E}\times \mathbb{F} suivant : \langle (x,y),(x',y')\rangle= \langle x,x'\rangle+\langle y,y'\rangle.

Sous-différentiel d'une fonction marginale — Dans le cadre défini ci-dessus, supposons que \varphi\in\operatorname{Conv}(\mathbb{E}\times \mathbb{F}) et que f\in\operatorname{Conv}(\mathbb{E}). Si x\in \mathbb{E} et f(x)=\varphi(x,y) (l'infimum est atteint en y\in \mathbb{F}), alors


\partial f(x)=\{s:(s,0)\in\partial \varphi(x,y)\}.

Ce résultat appelle quelques remarques.

  1. Il faut bien noter que, si la borne inférieure \inf\{\varphi(x,y):y\in\mathbb{F}\} est atteinte en plusieurs y, \{s:(s,0)\in\partial \varphi(x,y)\} ne dépend pas du minimiseur y choisi.

    On a un autre éclairage sur cette indépendance par rapport à y en observant que \varphi est constante sur l'ensemble M(x):=\{(x,y): y minimise \varphi(x,\cdot)\}, si bien que \partial\varphi est aussi constant sur l'intérieur relatif de M(x). Cependant \partial\varphi(x,y) peut varier lorsque (x,y) passe de l'intérieur relatif de M(x) à son bord. C'est le cas de la fonction définie par \varphi(x,y)=\max(0,|y|-1), dont la fonction marginale est nulle :

    M(x)=\{x\}\times[-1,1]\quad\mbox{et}\quad\partial \varphi(0,y)=\left\{\begin{array}{ll}\{(0,0)\} & \mbox{si}~-1<y<1\\\{0\}\times[0,1] & \mbox{si}~y=1.\end{array}\right.

  2. D'autre part, si \varphi est différentiable en (x,y), où y est un minimiseur quelconque de \varphi(x,\cdot), alors f est également différentiable en x (car son sous-différentiel est un singleton) et on a

    \nabla f(x)=\nabla_x\varphi(x,y).

    C'est comme s'il y avait un minimiseur unique y(x), fonction différentiable de x, que l'on écrivait f(x)=\varphi(x,y(x)) et que l'on calculait \nabla f(x) par une dérivation en chaîne :

    \nabla f(x)=\nabla_x\varphi(x,y)+y'(x)^*\nabla_y\varphi(x,y).

    On retrouverait le résultat ci-dessus en observant que \nabla_y\varphi(x,y)=0 car y minimise \varphi(x,\cdot).
  3. Le fait que \varphi(x,\cdot) ait un minimum unique n'implique nullement la différentiabilité de la fonction marginale en x. Par exemple, f est la fonction marginale de \varphi définie par \varphi(x,y)=f(x)+y^2. Cette dernière a un minimum y=0 unique en y quel que soit x, alors que f peut ne pas être différentiable.

Enveloppe supérieure[modifier | modifier le code]

Fonctions concave et convexe-concave[modifier | modifier le code]

Certaines constructions conduisent naturellement à des fonctions concaves plutôt que convexes. Il en est ainsi, par exemple, lorsque l'on prend l'enveloppe inférieure d'une famille de fonctions linéaires (la fonction duale d'un problème d'optimisation est construite de cette manière). On peut alors prendre le sous-différentiel de la fonction opposée, qui est convexe, mais il est parfois plus naturel de se passer de la multiplication par moins un. Si f est concave, on définit donc le sous-différentiel concave de cette fonction en un point x où elle est finie, comme l'ensemble noté et défini par


\overset{\frown}{\partial}f(x):=-\partial (-f)(x).

Certains auteurs ne mettent pas le signe \frown au-dessus de \partial ; il faut alors se rappeler que f est concave. Si f est concave différentiable, son sous-différentiel concave se réduit bien au gradient de f. Les propriétés suivantes sont équivalentes :

  • s\in\overset{\frown}{\partial}f(x),
  • \forall\,d\in\mathbb{E},~f'(x;d)\leqslant \langle s,d\rangle,
  • \forall\,y\in\mathbb{E},~f(y)\leqslant f(x) + \langle s, y-x\rangle,
  • x maximise y\in\mathbb{E}\mapsto f(y)-\langle s,y\rangle.

Il est aussi intéressant de définir le sous-différentiel d'une fonction convexe-concave. Si \mathbb{E} et \mathbb{F} sont deux espaces vectoriels, on dit que f:\mathbb{E}\times\mathbb{F}\to\bar{\R} est convexe-concave si

  • pour tout y\in\mathbb{F}, x\mapsto f(x,y) est convexe et
  • pour tout x\in\mathbb{E}, y\mapsto f(x,y) est concave.

Le lagrangien d'un problème d'optimisation convexe avec contraintes a cette propriété. La situation est plus complexe que dans le cas d'une fonction concave, car il ne suffit pas de multiplier (une partie de) la fonction par -1 pour retrouver une fonction convexe et lui appliquer la notion de sous-différentiel convexe que l'on connait.

Sous-gradient d'une fonction convexe-concave — Soient \mathbb{E} et \mathbb{F} deux espaces vectoriels et f:\mathbb{E}\times\mathbb{F}\to\bar{\R} une fonction convexe-concave. On dit que (u,v)\in\mathbb{E} est un sous-gradient (convexe-concave) de f en un point (x,y)f prend une valeur finie si (u,v) vérifie l'une des propriétés équivalentes suivantes :

  1. u\in\partial_xf(x,y) et v\in\overset{\frown}{\partial}_yf(x,y),
  2. \forall\,x'\in\mathbb{E}:~f(x',y)\geqslant f(x,y) + \langle u, x'-x\rangle,
    \forall\,y'\in\mathbb{F}:~f(x,y')\leqslant f(x,y) + \langle v, y'-y\rangle,
  3. (x,y) est un point-selle de (x',y')\in\mathbb{E}\times\mathbb{F}\mapsto f(x',y')-\langle u,x'\rangle-\langle v,y'\rangle.

On note \overset{\backsim}{\partial} f(x,y) l'ensemble des sous-gradients et on le nomme le sous-différentiel (convexe-concave) de f. Par convention, ce sous-différentiel est vide si f(x) n'est pas fini.

De manière synthétique :

\overset{\backsim}{\partial} f(x,y):=\partial_xf(x,y)\times\overset{\frown}{\partial}_yf(x,y).

Dans cette définition, on a noté \partial_xf(x,y) le sous-différentiel ordinaire en x de la fonction convexe x'\mapsto f(x',y) et \overset{\frown}{\partial}_yf(x,y) le sous-différentiel concave en y de la fonction concave y'\mapsto f(x,y'). Certains auteurs ne mettent pas le signe \backsim au-dessus de \partial ; il faut alors se rappeler que f est convexe-concave.

Exemples[modifier | modifier le code]

Voici quelques exemples de sous-différentiels de fonctions convexes classiques.

Fonction indicatrice[modifier | modifier le code]

On suppose ici que \mathbb{E} est un espace euclidien et que C est un convexe de \mathbb{E}.

Le sous-différentiel de la fonction indicatrice \mathcal{I}_C est le cône normal N_C de C :

\partial\,\mathcal{I}_C=N_C.

Norme[modifier | modifier le code]

Soit \|\cdot\| une norme sur un espace euclidien \mathbb{E}, non nécessairement dérivée du produit scalaire \langle\cdot,\cdot\rangle de \mathbb{E}. On introduit la norme duale


\|s\|_{_D}:=\sup_{\|x\|\leqslant 1}\;\langle s,x\rangle

et la boule-unité duale fermée


\bar{B}_{_D}:=\{s\in\mathbb{E}:\|s\|_{_D}\leqslant 1\}.

Une norme est évidemment une fonction convexe (par l'inégalité triangulaire), partout sous-différentiable (elle ne prend que des valeurs finies). Son sous-différentiel est donné par les formules

\partial (\|\cdot\|)(x)=\operatorname{arg\,max}_{s\in\bar{B}_{_D}}\,\langle s,x\rangle = \{s\in\bar{B}_{_D}: \langle s,x\rangle=\|x\|\}.

En particulier :

  • si x\ne0, les sous-gradients s\in\partial(\|\cdot\|)(x) sont sur la frontière de \bar{B}_{_D} : \|s\|_{_D}=1 ;
  • \partial (\|\cdot\|)(0)=\bar{B}_{_D}.


La puissance p>1 d'une norme


f:\mathbb{E}\to\R:x\mapsto f(x):=\frac{1}{p}\,\|x\|^p

est aussi une fonction convexe (composition de fonctions convexes dont la seconde est croissante) propre (elle ne prend que des valeurs finies) fermée (elle est continue) et partout sous-différentiable (elle ne prend que des valeurs finies). Son sous-différentiel est donné par les formules

\partial f(x)=\{s\in\mathbb{E}: \langle s,x\rangle=\|x\|^p=\|s\|_{_D}^{p'}\}=\|x\|^{p-1}\,\Bigl(\partial (\|\cdot\|)(x)\Bigr),

p':=p/(p-1)\in{]0,1[} est le nombre conjugué de p :


\frac{1}{p}+\frac{1}{p'}=1.

La dernière expression du sous-différentiel \partial f(x) rappelle la dérivation en chaîne de la composition de x\in\mathbb{E}\mapsto\|x\| et de t\in\R\mapsto t^p/p.

Distance à un convexe[modifier | modifier le code]

Soit \|\cdot\| une norme sur un espace euclidien \mathbb{E}, non nécessairement dérivée du produit scalaire \langle\cdot,\cdot\rangle de \mathbb{E}. On introduit la norme duale


\|s\|_{_D}:=\sup_{\|x\|\leqslant 1}\;\langle s,x\rangle

et la boule-unité duale fermée


\bar{B}_{_D}:=\{s\in\mathbb{E}:\|s\|_{_D}\leqslant 1\}.

Soit C un ensemble convexe fermé non vide de \mathbb{E}. On considère la fonction \operatorname{dist}_C:\mathbb{E}\to\R, la distance à C, définie par


\operatorname{dist}_C(x)=\inf_{y\in C}\|x-y\|.

C'est une fonction convexe propre et fermée (elle ne prend que des valeurs finies). On note \bar{x} une projection d'un point x sur C : c'est une solution du problème \inf\{\|x-y\|:y\in C\}. Cette dernière n'est pas nécessairement unique car la norme n'est pas nécessairement associée à un produit scalaire.

Le sous-différentiel en x\in\mathbb{E} de la distance à C est donné par la formule

\partial\,\operatorname{dist}_C(x)=\left\{s\in\bar{B}_{_D}\cap N_C(\bar{x}):
\langle s,x-\bar{x}\rangle=\|x-\bar{x}\|\right\}.

N_C(x):=\{d\in\mathbb{E}:\langle d,y-x\rangle\leqslant 0 pour tout y\in C\} est le cône normal à C en x.

Lorsque la norme \|\cdot\| est celle associée au produit scalaire \langle\cdot,\cdot\rangle, les boules-unités primale et duale coïncident (c'est-à-dire, \bar{B}_{_D}=\bar{B}) et on a les propriétés suivantes :

  • si x\notin C, alors \operatorname{dist}_C est différentiable en x et \nabla \operatorname{dist}_C(x)=(x-\bar{x})/{\|x-\bar{x}\|} ;
  • si x\in\operatorname{int}\,C, l'intérieur de C, alors \operatorname{dist}_C est différentiable en x et \nabla \operatorname{dist}_C(x)=0 ;
  • si x\in C\setminus (\operatorname{int}\,C), la frontière de C, alors \partial\,\operatorname{dist}_C(x)=\bar{B}\cap N_C(x).

En l'absence de convexité d'un ensemble P\subset \mathbb{E}, la distance \operatorname{dist}_P n'est pas nécessairement différentiable sur le complémentaire de P.

Valeur propre maximale[modifier | modifier le code]

On note \mathcal{S}^n l'ensemble des matrices réelles d'ordre n symétriques, que l'on munit du produit scalaire canonique (A,B)\in\mathcal{S}^n\times\mathcal{S}^n\mapsto\langle A,B\rangle:=\operatorname{tr}\, AB (\operatorname{tr}\,A désigne la trace de la matrice A). On note aussi \mathcal{S}^n_+ le cône de \mathcal{S}^n formé des matrices semi-définies positives. On note enfin


\lambda_1:\mathcal{S}^n\to\R:A\mapsto\lambda_1(A)

l'application valeur propre maximale, qui à une matrice symétrique A associe sa plus grande valeur propre (on rappelle qu'une matrice symétrique d'ordre n a n valeurs propres réelles). C'est une fonction propre, convexe et continue (donc fermée). Son sous-différentiel en A\in\mathcal{S}^n est donné par la formule

\partial\lambda_1(A)=\operatorname{co}\,\{vv^{\top\!}:\|v\|_2=1,\;Av=\lambda_1(A)v\},

\operatorname{co}\,P désigne l'enveloppe convexe d'un ensemble P. L'enveloppe convexe ci-dessus est compacte (par exemple, parce que le sous-différentiel d'une fonction convexe ne prenant que des valeurs finies, comme \lambda_1, l'est).

On en déduit que :

  • si \lambda_1(A) est simple, \lambda_1(\cdot) est différentiable en A et son gradient s'écrit alors
    \nabla\lambda_1(A)=vv^{\top\!},
    \pm v sont les uniques vecteurs propres unitaires associés à la valeur propre maximale ;
  • \partial\lambda_1(0)=\{S\in\mathcal{S}^n_+:\operatorname{tr}\,S=1\} ;
  • la dérivée directionnelle de \lambda_1 en A\in\mathcal{S}^n dans la direction D\in\mathcal{S}^n s'écrit
     \lambda_1'(A;D)=\lambda_1(V^{\top\!} DV),
    V est une matrice dont les colonnes forment une base orthonormale de l'espace propre associé à \lambda_1(A).

Fonction spectrale[modifier | modifier le code]

La présentation ci-dessous synthétise celles de Lewis (1996), Hiriart-Urruty (1998), Borwein et Lewis (2000).

On note \mathcal{S}^n l'ensemble des matrices réelles d'ordre n symétriques, que l'on munit du produit scalaire canonique (A,B)\in\mathcal{S}^n\times\mathcal{S}^n\mapsto\langle A,B\rangle:=\operatorname{tr}\, AB, la trace de la matrice AB. Par ailleurs, pour x\in\R^n, on note [x]\in\R^n le vecteur formé des composantes de x en ordre décroissant.

On se donne une fonction f:\R^n\to\bar{\R} symétrique, c'est-à-dire qui vérifie


\forall\,x\in\R^n:\qquad f(x)=f([x]),

ce qui revient à dire que l'on ne modifie pas la valeur de f(x) en permutant les composantes de x. On note


\lambda:\mathcal{S}^n\to\R^n:A\mapsto\lambda(A):=(\lambda_1(A),\ldots,\lambda_n(A)),

la fonction donnant les valeurs propres de A en ordre décroissant :


\lambda_1(A)\geqslant \lambda_2(A)\geqslant \cdots\geqslant \lambda_n(A).

On appelle fonction spectrale une fonction de la forme f\circ \lambda, avec f et \lambda comme ci-dessus. Ce sont donc des fonctions définies sur \mathcal{S}^n, mais dont les valeurs ne dépendent que du spectre des matrices.

On peut alors caractériser la convexité-fermeture de (f\circ\lambda) à partir de celle de f[5].

Convexité-fermeture d'une fonction spectrale — Dans le cadre défini ci-dessus, si f est symétrique, alors


(f\circ\lambda)\in\operatorname{C\overline{onv}}(\mathcal{S}^n)
\qquad\Longleftrightarrow\qquad
f\in\operatorname{C\overline{onv}}(\R^n).

On peut aussi calculer le sous-différentiel de (f\circ\lambda) à partir de celui de f.

Sous-différentiel d'une fonction spectrale — Dans le cadre défini ci-dessus, si f\in\operatorname{C\overline{onv}}(\R^n) est symétrique, alors les trois propriétés suivantes, reliant A et S\in\mathcal{S}^n, sont équivalentes :

  1. S\in\partial(f\circ \lambda)(A),
  2. \lambda(S)\in\partial f(\lambda(A)) et \langle S,A\rangle=\lambda(S)^{\top\!}\lambda(A),
  3. il existe une matrice orthogonale V et des vecteurs a, s\in\R^n tels que


V^{\top\!} AV=\operatorname{Diag}(a),\qquad V^{\top\!} SV=\operatorname{Diag}(s)\qquad\mbox{et}\qquad s\in\partial f(a).

On peut enfin caractériser la différentiabilité de (f\circ\lambda) à partir de celle de f.

Différentiabilité d'une fonction spectrale — Dans le cadre défini ci-dessus, si f\in\operatorname{C\overline{onv}}(\R^n) est symétrique, (f\circ\lambda) est différentiable en A si, et seulement si, f est différentiable en \lambda(A). Dans ce cas, si V est une matrice orthogonale telle que A=V\;\operatorname{Diag}(\lambda(A))\;V^{\top\!}, on a


\nabla(f\circ\lambda)(A)=V\;\operatorname{Diag}(\nabla f(\lambda(A)))\;V^{\top\!}.

Les fonctions spectrales sont fréquemment rencontrées. En voici quelques-unes, construites à partir de fonctions f\in\operatorname{C\overline{onv}}(\R^n), donnant donc lieu à des fonctions (f\circ\lambda)\in\operatorname{C\overline{onv}}(\mathcal{S}^n). Dans le tableau ci-dessous, les entiers p et q peuvent être choisis arbitrairement dans \{0,\ldots,n\}, un vecteur de x\in\R^n dont toutes les composantes sont strictement positives est signalé par x>0, une matrice A définie positive est signalée par A\succ0.

f(x) (f\circ\lambda)(A)
[x]_1=\max(x_1,\ldots,x_n) \lambda_1(A)
-[x]_n=-\min(x_1,\ldots,x_n) -\lambda_n(A)
\sum_{i=1}^p[x]_i-\sum_{i=n-q+1}^n[x]_i \sum_{i=1}^p\lambda_i(A)-\sum_{i=n-q+1}^n\lambda_i(A)
\operatorname{l\!b}(x)=\left\{\begin{array}{ll}-\sum_{i=1}^n\log\,x_i & \mbox{si}~x>0\\+\infty & \mbox{sinon}\end{array}\right. \operatorname{l\!d}(A)=\left\{\begin{array}{ll}-\log\,\det\,A & \mbox{si}~A\succ0\\+\infty & \mbox{sinon}\end{array}\right.
\left\{\begin{array}{ll}-\left(\sum_{i=1}^n\,x_i^{-1}\right)^{-1} & \mbox{si}~x>0\\+\infty & \mbox{sinon}\end{array}\right. \left\{\begin{array}{ll}-\left(\operatorname{tr}\,A^{-1}\right)^{-1} & \mbox{si}~A\succ0\\+\infty & \mbox{sinon}\end{array}\right.


Fonction définie sur un espace localement convexe[modifier | modifier le code]

La présentation ci-dessous synthétise celle de Bonnans et Shapiro (2000).

Cadre[modifier | modifier le code]

On suppose donnés deux espaces espaces vectoriels topologiques localement convexes \mathbb{E} et \mathbb{E}^* sur \R couplés, dans le sens où il existe une application bilinéaire continue


\langle\cdot,\cdot\rangle:\mathbb{E}\times\mathbb{E}^*\to\R

telle que

Comme exemples de tels couples d'espaces vectoriels topologiques localement convexes, citons

Définitions[modifier | modifier le code]

Les définitions de sous-gradient, de sous-différentiel et de sous-différentiabilité sont essentiellement les mêmes que celles introduites en dimension finie.

Sous-gradient, sous-différentiel, sous-différentiabilité — Soit f : \mathbb{E}\to\R\cup\{+\infty\}, une fonction convexe et propre. On dit que x^*\in\mathbb{E}^* est un sous-gradient de f en x\in\operatorname{dom}\,f si l'une des propriétés équivalentes suivantes est vérifiée :

  1. \forall\,y\in\mathbb{E},~f(y)\geqslant f(x) + \langle x^*, y-x\rangle,
  2. x minimise y\in\mathbb{E}\mapsto f(y)-\langle x^*,y\rangle,
  3. f^*(x^*) + f(x) \leqslant \langle x^*, x\rangle,
  4. f^*(x^*) + f(x) = \langle x^*, x\rangle.

L'ensemble des sous-gradients de f en x est appelé le sous-différentiel de f en x ; il est noté


\partial f(x).

On dit que f est sous-différentiable en x si \partial f(x)\ne\varnothing. Par convention, \partial f(x)=\varnothing si x\notin\operatorname{dom}\,f.

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Voir Clarke (1983).
  2. Proposition 6 chez Rockafellar (1976).
  3. Proposition IV.4.2.1 chez Hiriart-Urruty et Lemaréchal (2001).
  4. Théorème 25.1 chez Rockafellar (1970).
  5. Voir Davis (1957) et la section 5.2 chez Borwein et Lewis (2000).

Bibliographie[modifier | modifier le code]

  • (en) A. Auslender, M. Teboulle (2003). Asymptotic Cones and Functions in Optimization and Variational Inequalitites. Springer Monographs in Mathematics. Springer, New York.
  • (en) J. F. Bonnans, A. Shapiro (2000). Perturbation Analysis of Optimization Problems. Springer Verlag, New York.
  • (en) J.M. Borwein, A.S. Lewis (2000). Convex Analysis and Nonlinear Optimization. Springer, New York.
  • H. Brézis (1973). Opérateurs Maximaux Monotones et Semi-groupes de Contractions Dans les Espaces de Hilbert. Mathematics Studies 5. North-Holland, Amsterdam. ISBN 978-0-7204-2705-9.
  • (en) C. Davis (1957). All convex invariant functions of Hermitian matrices. Archiv der Mathematik, 8, 26-278.
  • (en) F.H. Clarke (1983). Optimization and Nonsmooth Analysis. John Wiley & Sons, New York.
  • J.-B. Hiriart-Urruty (1998). Optimisation et Analyse Convexe. Presses Universitaires de France, Paris.
  • (en) J.-B. Hiriart-Urruty, Cl. Lemaréchal (2001). Fundamentals of Convex Analysis. Springer. ISBN 978-3-540-42205-1.
  • (en) A.S. Lewis (1996). Convex analysis on the Hermitian matrices. SIAM Journal on Optimization, 6, 164-177.
  • (en) R.T. Rockafellar (1970). Convex Analysis. Princeton Mathematics Ser. 28. Princeton University Press, Princeton, New Jersey.
  • (en) R.T. Rockafellar (1976). Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14, 877–898.
  • (en) R.E. Showalter (1997). Monotone Operators in Banach Space and Nonlinear Partial Differential Equations. American Mathematical Society. ISBN 978-0-8218-0500-8.