Chapitre 1 : dérivation et convexité

1. Dérivation

soit f : {\mathbb R}^n \mapsto {\mathbb R} une fonction

On dit que f est différentiable en a s’il existe un vecteur \nabla f(a)

appelé gradient de f en a vérifiant

f(a+h)=f(a) + <\nabla f(a),h> + \|h\|\epsilon(h)

\lim_{\|h\| \mapsto 0} \epsilon(h) = 0

On dit qu’elle est deux fois différentiable en a s’il existe aussi une matrice symétrique

notée \nabla^2 f(a) appelée matrice hessienne de f en a vérifiant

f(a+h)=f(a) + <\nabla f(a),h> + \frac{1}{2}<\nabla^2 f(a)h,h> \|h\|^2\epsilon(h)

PROPOSITION

Si f est différentiable en a

\nabla f(a) =\begin{pmatrix} \frac{\partial f}{\partial x_1}\\ \vdots \\ \frac{\partial f}{\partial x_n}\end{pmatrix}

Si f est 2 fois différentiable en a

\nabla^2 f(a)_{ij} = \frac{\partial^2 f}{\partial x_i\partial x_j}

2. Convexité

Soit C \subset {\mathbb R}^n

Définition

On dit que C est convexe si

\forall x,y \in {\mathbb R}^n \forall t \in [0;1]\text{ on a } tx+(1-t)y \in C

PROPRIETES

– l’intersection d’ensembles convexes est convexe

– la multiplication d’un convexe par un scalaire est convexe

– l’addition ou la différence d’un convexe avec un élément {\mathbb R}^nde est convexe

– Attention l’union de deux ensembles convexes n’est pas un convexe

PROPOSITION

Soit C \subset {\mathbb R}^n

C est convexe ssi

\forall \lambda_{1},\cdots,\lambda_{k} \geqslant 0 \text{ tq } \Sigma{\lambda_{k}} = 1 \text{ on a } \forall x_1,\cdots,x_k \in C\text{ } \Sigma{\lambda_{k}x_k} \in C

Démonstration simple par récurrence.

Définition

soit C \subset {\mathbb R}^n on appelle enveloppe convexe de C notée coC le plus petit ensemble convexe contenant C. C’est aussi l’intersection de tous les convexes contenant C.

PROPOSITION

Soit C \subset {\mathbb R}^n et C \neq \varnothing

Si C est un ouvert alors coC est un ouvert.

THEOREME DE CARATHÉODORY

Soit C \subset {\mathbb R}^n et C \neq \varnothing

alors

\forall x \in CoC \text{ } \exists \lambda_1,\cdots,\lambda_{n+1} \geqslant 0 \text{ tq } \sum_{i=1}^{n+1}{\lambda_{1}} = 1 \text{ } \exists x_1,\cdots,x_{n+1} \in C\text{ tq } x= \sum_{i=1}^{n+1}{\lambda_{i}x_i}

Démonstration :

A mettre

COROLLAIRE

Soit C \subset {\mathbb R}^n et C \neq \varnothing

Si C est un compact alors coC est un compact

Démonstration :

On a \phi : C\text{x}C\text{x}\cdots\text{x}C\text{x}\Delta \mapsto \text{coC}
\phi : (x_1,\cdots,x_{n+1}),(\lambda_1,\cdots,\lambda_{n+1}) \mapsto \sum_{i=1}^{n+1}\lambda_{i}x_i

avec \Delta=\{((\lambda_1,\cdots,\lambda_{n+1}); \sum_{i=1}^{n+1}\lambda_{i}=1\}

Cette fonction est bien définie, elle est surjective d’après Carathéodory, elle est continue. CxC…..CxDelta est un compact comme produit de compact.
Or l’image d’un compact est un compact dans ces conditions. CQFD

Ceci n’est plus vrai en dimension infinie.

3. Fonctions convexes

{\mathbb R}^n est muni du produit scalaire usuel et de la norme associée

Soit K \subset {\mathbb R}^n et et K \neq \varnothing
F de K dans {\mathbb R}^n une fonction et K convexe.

Définitions

L’épigraphe de f noté epi f = \{(x,r) \in K\text{x}{\mathbb R}^n; f(x) \leqslant r\}

La section inférieur de niveau lambda est

S_f(\lambda)=\{x \in K; f(x) \leqslant \lambda\}

On appelle courbe de f de niveau lambda

S_f(\lambda)=\{x \in K; f(x) = \lambda\}

Définition d’une fonction convexe :

On dit que f est convexe si :

\forall x,y \in K \text{ }\forall t \in [0;1]\text{ } f(tx+(1-t)y) \leqslant tf(x) + (1-t)f(y)

On dit que f est strictement convexe si :

\forall x,y \in K \text{ }x \neq y\text{ }\forall t \in ]0;1[\text{ } f(tx+(1-t)y) < tf(x) + (1-t)f(y)[/latex]  On dit que f est fortement convexe si :  [latex]\exists c>0\text{ }\forall x,y \in K \text{ }\forall t \in [0;1]\text{ } f(tx+(1-t)y) \leqslant tf(x) + (1-t)f(y) - ct(1-t)\|x-y\|^2

On dit que f est quasi convexe si :

\forall x,y \in K \text{ }x \neq y\text{ }\forall t \in ]0;1[\text{ } f(tx+(1-t)y) \leqslant max(f(x),f(y))

PROPOSITION

f est convexe ssi epi(f) est un ensemble convexe

Fortement convexe implique strictement implique convexe, implique quasi convexe

Exemple :

f(x) = x^2 fortement convexe
f(x) = -ln(x) est strictement convexe
Fonction affine par morceau est convexe

Une fonction strictement convexe est est enveloppable par une fonction quadratique.

PROPOSITION

f est convexe ssi :

\forall \lambda_1,\cdots,\lambda_{k} \geqslant 0 ; \sum_{i=1}^{k}\lambda_{i}=1

\forall x_1,\cdots,x_{k} \in K \text{ } f(\sum_{i=1}^{k}\lambda_{i}x_i) \leqslant \sum_{i=1}^{k}\lambda_{i}f(x_i)

f strictement convexe ssi :

\forall \lambda_1,\cdots,\lambda_{k} \geqslant 0 ; \sum_{i=1}^{k}\lambda_{i}=1

\forall x_1,\cdots,x_{k} \in K \text{ } f(\sum_{i=1}^{k}\lambda_{i}x_i) < \sum_{i=1}^{k}\lambda_{i}f(x_i) [/latex]  f affine ssi égalité à la place des inégalités ci dessus  <strong>PROPOSITION</strong></p> <p>Caractérisation des fonctions fortement convexe.</p> <p>f fortement convexe ssi il existe c>0 tel que g définie par<br /> [latex]g(x) = f(x) -c\|x\|^2 est convexe

ceci n'est vrai que si la norme est issue d'un produit scalaire.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *


*