2 Fonctions convexes

Il est pratique de considérer des fonctions $f:E\to]-\infty,+\infty]=\mathbb{R}\cup\{+\infty\}.$ Dans ce cas on parle de domaine de $f$ :

D(f)=\{x\in E:f(x)<\infty\}.

Les propriétés que l’on considère dans cette section vont être déterminées par l’ensemble des valeurs au dessus du graphe de $f$ , que l’on appelle épigraphe de f:

\text{Epi}(f)=\{(x,\lambda)\in E\times\mathbb{R}:f(x)\leq\lambda\}.

On utilise les conventions $\infty+\infty=\infty$ et $\lambda.\infty=\infty$ si $\lambda>0$ , $0.\infty=0$ .

$\bigstar$ Définition 3.3.

Soit $C$ un ensemble convexe.

1.

Une fonction $f:C\to]-\infty,+\infty]$ est dite convexe si pour tout $\lambda\in]0,1[,x,y,\in C$ ,

$f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y).$
2.

Une fonction $f:C\to]-\infty,+\infty]$ est dite strictement convexe si pour tout $\lambda\in]0,1[,x,y,\in C$ , avec $x\neq y$

$f(\lambda x+(1-\lambda)y)<\lambda f(x)+(1-\lambda)f(y).$
3.

Une fonction $f:C\to[-\infty,+\infty[$ est dite concave si $-f$ est convexe.

Exemple 3.2.

Une fonction affine $f(x_{1},...,x_{n})=\displaystyle\sum_{i=1}^{n}a_{i}x_{i}+b$ est convexe et concave mais pas strictement convexe ! Une norme sur $E$ est convexe.

Remarque 3.1.

Si $f$ est convexe, alors $C\cap D(f)$ est convexe car si $f(x)<+\infty,f(y)<\infty$ alors

f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)<\infty.

On peut donc toujours remplacer soit $C$ par $E$ soit $C$ par $C\cap D(f)$ selon votre goût (pour les fonctions infinies ou les ensembles convexes).

Proposition 3.3.

Soit $E$ un e.v. et $f:C\to]-\infty,\infty]$ .

1.

$f$ est convexe si et seulement si $Epi(f)$ est convexe
1’.

Si $f$ est convexe alors pour tout $t\in\mathbb{R}$ , $f^{-1}(]-\infty,t])$ est convexe. La réciproque est fausse.
2.

Si $\mu>0$ , $f, g$ convexes alors $\mu f+g$ est convexe. De plus, elle est aussi strictement convexe si $f$ ou $g$ l’est.
3.

Si $f_{i},i\in I$ sont convexes alors l’enveloppe supérieure $f(x)=\sup_{i\in I}f_{i}(x)$ est convexe.
4.

(facultatif) $f$ est convexe ssi $g:E\to]-\infty,+\infty]$ , définie par $g(x)=f(x)$ si $x\in C$ et $g(x)=+\infty$ sinon, est convexe.
5.

Si $f$ est strictement convexe, alors $f$ a au plus un minimum sur $C$ .

Le dernier point donne la première relation simple des fonctions convexes à l’optimisation.

Démonstration :

Pour (1), l’énoncé est vide si $f(x)$ ou $f(y)=\infty$ . Soit donc $(x,t_{1}),(y,t_{2})\in Epi(f)$ (comme on veut $t_{i}<\infty$ cela utilise la réduction précédente). On remarque que $(\lambda x+(1-\lambda)y,\lambda t_{1}+(1-\lambda)t_{2})\in Epi(f)$ ssi $f(\lambda x+(1-\lambda)y)\leq\lambda t_{1}+(1-\lambda)t_{2}.$

Si les épigraphes sont convexes, cette propriété est vérifiée et donc en prenant l’infimum sur $t_{1},t_{2}$ (qui donne $f(x),f(y)$ ) on a le résultat. Si $f$ vérifie l’inégalité, on utilise $f(x)\leq t_{1},f(y)\leq t_{2}$ pour conclure:

f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)\leq\lambda t_{1}+(1-% \lambda)t_{2}.

(1)’ On montre la convexité de $D=\{x:f(x)\leq t\}$ comme ci-dessus. Soit $x,y\in D$ alors pour $\lambda\in[0,1]$ : $f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)\leq\lambda t+(1-% \lambda)t=t.$ Donc $\lambda x+(1-\lambda)y\in D$ . Par contre si $g=1_{[0,\infty[}$ alors si $t<0$ , $g^{-1}(]-\infty,t])=\emptyset$ , si $0\leq t<1$ , $g^{-1}(]-\infty,t])=]-\infty,0[$ et sinon pour $t\geq 1$ , $g^{-1}(]-\infty,t])=\mathbb{R}$ et ce sont 3 intervalles donc 3 ensembles convexes. Mais $g$ n’est pas convexe $g(0)=1>1/2g(-1)+1/2g(1)=1/2$ .

(2) est évident en utilisant l’inégalité:

\mu f(\lambda x+(1-\lambda)y)+g(\lambda x+(1-\lambda)y)\leq\mu(\lambda f(x)+(1% -\lambda)f(y))+(\lambda g(x)+(1-\lambda)g(y))=(\lambda(\mu f+g)(x)+(1-\lambda)% (\mu f+g)(y)).

(3) vient de la stabilité des convexes par intersection et de $Epi(f)=\cap_{i\in I}Epi(f_{i}).$

(4) est évident car $Epi(f)=Epi(g).$

(5) si $x\neq y$ sont deux points atteignant le minima, $f((x+y)/2)<(f(x)+f(y))/2$ contredisant la minimalité. □

Une propriété importante des fonctions convexes est le fait qu’on peut les caractériser en terme d’accroissements:

Proposition 3.4.

Soit $f:E\to]-\infty,+\infty]$ une fonction. $f$ est convexe si et seulement si pour tout $x,h\in E$ la fonction $\Delta_{x,h}f(t):=\frac{f(x+th)-f(x)}{t}$ est croissante sur $\mathbb{R}_{+}^{*}.$

Démonstration :

Il suffit de noter que $g(t)=\Delta_{x,h}f(t)=\frac{f(x+th)-f(x)}{t}$ est croissante si et seulement si $g(t)\leq g(s)$ pour $0<t<s$ si et seulement si on a l’inégalité de convexité :

f(x+th)=f(\frac{t}{s}(x+sh)+x(1-\frac{t}{s}))\leq f(x+sh)\frac{t}{s}+f(x)(1-% \frac{t}{s}).

Donc la convexité de $f$ implique la croissance énoncée et réciproquement en prenant $s=1$ on écrit toute paire $x, y$ sous la forme $y=x+h$ et l’inégalité ci-dessus se réécrit en l’inégalité définissant la convexité de $f$ :

f((1-t)x+ty)=f(x+th)\leq f(x+h)t+f(x)(1-t)=f(y)t+f(x)(1-t).

□

Cela implique une régularité minimale des fonctions convexes:

Corollaire 3.5.

Si $f:E\to]-\infty,\infty]$ est convexe, pour tout $x\in D(f)$ et tout $h\in E$ , la dérivée directionnelle $D_{h}^{\prime}f(x)$ existe dans $[-\infty,\infty]$ au sens où la limite suivante existe et vaut:

D_{h}^{\prime}f(x):=\lim_{t\to 0^{+}}\frac{f(x+th)-f(x)}{t}=\inf_{t>0}\frac{f(% x+th)-f(x)}{t}.

Démonstration :

Par la proposition précédente $g(t)=\frac{f(x+th)-f(x)}{t}$ est croissante donc admet une limite pour $t\to 0^{+}$ qui coïncide avec l’infimum. □

2.1 Calcul des cônes normaux courants

Soient $g_{1},...,g_{n}$ des fonctions convexes $C^{1}$ définies $U\to\mathbb{R}$ avec $U$ ouvert convexe tel qu’il existe $x_{0}\in U$ avec $g_{i}(x_{0})<0$ pour tout $i$ .

Soit la contrainte :

C=\{x\in U:\forall i\in\{1,...,n\},g_{i}(x)\leq 0\}.

On sait que chaque $g_{i}^{-1}(]-\infty,0])$ est convexe comme image réciproque d’un intervalle borné supérieurement par une application convexe. Par intersection, on sait donc que $C=\cap_{i=1}^{n}g_{i}^{-1}(]-\infty,0])\subset U$ est aussi convexe.

$\bigstar$ Théorème 3.6 (admis, cf Section B.1).

Soit $x\in C$ tel que:

1.

les $l$ premières contraintes sont actives, c’est à dire: $g_{1}(x)=...=g_{l}(x)=0$
2.

les autres contraintes ne sont pas actives, c’est à dire $g_{l+1}(x)<0,...g_{n}(x)<0$

Si $l=0$ , on a $N_{C}(x)=\{0\}$ et sinon, le cône normal à $C$ en $x$ est donné par

N_{C}(x)=\left\{\displaystyle\sum_{i=1}^{l}\lambda_{i}\nabla g_{i}(x),\lambda_% {i}\geq 0\right\}.

Exemple 3.3.

Soit $A=\{(x,y)\in\mathbb{R}^{2}:x\geq y\geq 0,\}$ . Si on pose $g_{1}(x,y)=y-x,g_{2}(x,y)=-y$ qui sont linéaires donc convexes et $C^{1}$ , on a:

A=\{(x,y)\in\mathbb{R}^{2}:g_{1}(x,y)\leq 0,g_{2}(x,y)\leq 0\}

Calculons $N_{A}(0)$ le cône normal en $0=(0,0)$ .

On a $g_{1}(0,0)=0=g_{2}(0,0)$ donc toutes les contraintes sont actives.

On calcule donc $\nabla g_{1}(0,0)=(-1,1),\nabla g_{2}(0,0)=(0,-1)$ . D’après le théorème, on a :

N_{A}(0)=\mathbb{R}_{+}(-1,1)+\mathbb{R}_{+}(0,-1).

Exercice 3.4.

1.

Pour $A$ de l’exemple précédent, si $a=(x,x)$ pour $x>0$ . Montrer que $N_{A}(a)=\mathbb{R}_{+}(-1,1).$
2.

Pour $b=(x,0)$ , $x>0$ . Montrer que $N_{A}(b)=\mathbb{R}_{+}(0,-1).$
3.

Y-a-t-il d’autres valeurs de $N_{A}(c)$ et si oui, pour quels points $c\in A$ ?

2.2 Fonctions convexes sur $\mathbb{R}$

Soit $I$ un intervalle de $\mathbb{R}$ . Pour une fonction $f:I\to\mathbb{R}$ et $a\in I$ , on considère la fonction (taux d’accroissement de $f$ en $a$ ) $\Delta_{a}f$ définie par $\Delta_{a}f(x)=\cfrac{f(x)-f(a)}{x-a}$ pour tout $x\in I\setminus\{a\}$ . La proposition 3.4 se reformule sous la forme:

Proposition 3.7.

Une fonction $f:I\to\mathbb{R}$ est convexe si et seulement si pour tout $a\in I$ , la fonction $\Delta_{a}f$ est croissante sur $I\setminus\{a\}$ .

On en déduit les inégalités suivantes (inégalité des pentes, cf dessin en cours) sur une fonction $f$ :

$\bigstar$ Proposition 3.8.

Une fonction convexe $f:I\to\mathbb{R}$ vérifie l’ inégalité des pentes :

\forall a,\,b,\,c\in I,\,\,a<b<c\Rightarrow\frac{f(b)-f(a)}{b-a}\leq\frac{f(c)% -f(a)}{c-a}\leq\frac{f(c)-f(b)}{c-b}.

$\bigstar$ Théorème 3.9.

Soit $I$ un intervalle ouvert de $\mathbb{R}$ , et $f\colon I\to\mathbb{R}$ une fonction convexe. Alors pour tout $a\in I$ , $f$ admet des dérivées à droite et à gauche en $a$ . On a pour tout $x\in I$ : $f(x)\geq f^{\prime}_{d}(a)(x-a)+f(a)$ et $f(x)\geq f^{\prime}_{g}(a)(x-a)+f(a)$ . En particulier, il existe une fonction affine $g$ telle que $g(a)=f(a)$ et $g(x)\leq f(x)$ pour tout $x\in I$ . De plus, si $a<b$ sont dans $I$ , on a $f^{\prime}_{g}(a)\leq f^{\prime}_{d}(a)\leq f^{\prime}_{g}(b)$ .

Démonstration :

Soit $a\in I$ . Dans le cas d’une fonction à une variable, le corollaire 3.5 implique l’existence de dérivées à droites et à gauches (pour l’instant peut-être infinies). Dans l’inégalité des pentes en faisant $c\to b^{+}$ ou $a\to b^{-}$ , on obtient:

-\infty<\frac{f(b)-f(a)}{b-a}\leq f^{\prime}_{d}(b),

f^{\prime}_{g}(b)\leq\frac{f(c)-f(b)}{c-b}<+\infty.

Pour $a<b$ , $0<\epsilon_{i}<(b-a)/2$ , l’inégalité des pentes appliquée aux points $a\leq a+\epsilon_{1}<b-\epsilon_{2}<b$ donne:

\frac{f(a+\epsilon_{1})-f(a)}{\epsilon_{1}}\leq\frac{f(b-\epsilon_{2})-f(a+% \epsilon_{1})}{(b-a-\epsilon_{1}-\epsilon_{2})}\leq\frac{f(b-\epsilon_{2})-f(b% )}{-\epsilon_{2}}

et en passant à la limite $\epsilon_{1}\to 0^{+}$ ou $\epsilon_{2}\to 0^{+}$ puis les deux, on obtient:

f^{\prime}_{d}(a)\leq\frac{f(b-\epsilon_{2})-f(b)}{-\epsilon_{2}},

\frac{f(a+\epsilon_{1})-f(a)}{\epsilon_{1}}\leq f^{\prime}_{g}(b),

f^{\prime}_{d}(a)\leq f^{\prime}_{g}(b).

Donc $f^{\prime}_{d}(a)<+\infty$ , $f^{\prime}_{g}(a)>-\infty$ , ce qui termine la preuve des dérivabilités à droite et à gauche, et on a l’inégalité attendue.

De plus, la formulation comme infimum, dans le corollaire 3.5, montre que pour tout $x>a$ que $\displaystyle\frac{f(x)-f(a)}{x-a}\geq f^{\prime}_{d}(a)$ et donc $f(x)\geq f^{\prime}_{d}(a)(x-a)+f(a)$ . De même, pour tout $x<a$ on a $\displaystyle\frac{f(x)-f(a)}{x-a}\leq f^{\prime}_{g}(a)$ ; en multipliant par $x-a$ (qui est négatif!) on a donc que pour tout $x<a$ $f(x)\geq f(a)+f^{\prime}_{g}(a)(x-a)$ .

De plus, $f^{\prime}_{g}(b)\leq f^{\prime}_{d}(b)$ (en passant aux limites $a\to b^{-},c\to b^{+}$ dans l’inégalité des pentes); par conséquent, pour $x<a$ $f^{\prime}_{g}(a)(x-a)\geq f^{\prime}_{d}(a)(x-a)$ , et on voit finalement que l’inégalité $f(x)\geq f^{\prime}_{d}(a)(x-a)+f(a)$ est valide pour tout $x\in\mathbb{R}$ . Le même raisonnement s’applique pour montrer que l’autre inégalité est vraie pour tout $x\in\mathbb{R}$ . □

Corollaire 3.10.

Soit $I$ un intervalle ouvert de $\mathbb{R}$ , alors une fonction convexe $f\colon I\to\mathbb{R}$ est continue.

Exercice 3.5.

Trouver une fonction convexe $f:[0,1[\to\mathbb{R}$ qui n’est pas continue en $\{0\}$ .

Proposition 3.11.

Si $E=\mathbb{R}$ et $f$ est dérivable sur un ouvert convexe $U\subset E$ (donc un intervalle ouvert) alors $f$ est convexe si et seulement si $f^{\prime}$ est croissante.

Démonstration :

$\Rightarrow$ ) Supposons $f$ convexe, l’inégalité qu’on a montrée au (2) du théorème précédent s’écrit $(f^{\prime}(u)-f^{\prime}(v))(u-v)\geq 0$ donc $(f^{\prime}(u)-f^{\prime}(v)),(u-v)$ ont même signe et $f^{\prime}$ est croissante. On peut alternativement utilisé pour $a<b$ , $f^{\prime}(a)=f^{\prime}_{d}(a)\leq f^{\prime}_{g}(b)=f^{\prime}(b)$ grâce à l’inégalité vue au théorème 3.9.

$\Leftarrow$ ) Réciproquement si $f^{\prime}$ croissante, montrons que $f$ convexe, on veut voir $f(\lambda a+(1-\lambda)b)\leq\lambda f(a)+(1-\lambda)f(b)$ pour $a<b,\lambda\in]0,1[$ . Par l’égalité des accroissements finis, la pente $\frac{f(\lambda a+(1-\lambda)b)-f(a)}{(1-\lambda)(b-a)}$ est atteinte par $f^{\prime}$ en un point de $]a,\lambda a+(1-\lambda)b[$ , et de même $\frac{f(b)-f(\lambda a+(1-\lambda)b)}{(\lambda(b-a)}$ est atteinte par $f^{\prime}$ en un point de $]\lambda a+(1-\lambda)b,b[$ donc par croissance de la dérivée :

\frac{f(\lambda a+(1-\lambda)b)-f(a)}{(1-\lambda)(b-a)}\leq\frac{f(b)-f(% \lambda a+(1-\lambda)b)}{\lambda(b-a)}

\Longleftrightarrow f(\lambda a+(1-\lambda)b)(\frac{1}{(1-\lambda)(b-a)}+\frac% {1}{\lambda(b-a)})\leq\frac{f(a)}{(1-\lambda)(b-a)}+\frac{f(b)}{\lambda(b-a)}

\Longleftrightarrow f(\lambda a+(1-\lambda)b)(\frac{1}{\lambda(1-\lambda)})% \leq\frac{f(a)}{(1-\lambda)}+\frac{f(b)}{\lambda}.

Ceci conclut. □

2 Fonctions convexes

★ Définition 3.3.

Exemple 3.2.

Remarque 3.1.

Proposition 3.3.

Proposition 3.4.

Corollaire 3.5.

2.1 Calcul des cônes normaux courants

★ Théorème 3.6 (admis, cf Section B.1).

Exemple 3.3.

Exercice 3.4.

2.2 Fonctions convexes sur ℝ

Proposition 3.7.

★ Proposition 3.8.

★ Théorème 3.9.

Corollaire 3.10.

Exercice 3.5.

Proposition 3.11.

$\bigstar$ Définition 3.3.

$\bigstar$ Théorème 3.6 (admis, cf Section B.1).

2.2 Fonctions convexes sur $\mathbb{R}$

$\bigstar$ Proposition 3.8.

$\bigstar$ Théorème 3.9.