Fonctions convexes 1 Dimension 1 PDF

VARIATIONS DUNE FONCTION

On dit qu'une fonction croissante conserve l'ordre et qu'une fonction décroissante Définitions : Une fonction affine est définie sur ? par ...

GEOMETRIE AFFINE Document de travail pour la préparation au

Dec 8 2003 peut toujours définir une fonction vectorielle fa par la formule ... c) Lorsque ? n'est pas nul

Chapitre 3 Dérivabilité des fonctions réelles

mettent cependant de vérifier qu'une fonction est (ou n'est pas) dérivable en un point. une fonction affine f : x ?? ax + b est partout dérivable ...

SECOND DEGRÉ (Partie 1)

est une fonction polynôme de degré 1 (fonction affine). Méthode : Démontrer qu'une expression est la forme canonique d'une fonction polynôme de degré 2.

326 - Fonction - Quest-ce quune fonction affine-1

Une fonction affine de coefficient directeur et d'ordonnée à l'origine est la fonction qui a un nombre associe la somme du produit de par et de . Exemples :.

Fonctions convexes 1 Dimension 1

Soit I un intervalle ouvert de R. On note Aff(I) l'ensemble des fonctions affines définies sur I. 1. Montrer qu'une fonction ? : I ? R est convexe si et

Isométries du plan

notations de 2.2 A C = A B + B C ce qui montre que B est aligné avec Une façon plus intuitive de comprendre ce qu'est une application affine.

LES FONCTIONS DE RÉFÉRENCE

Remarque : Pour une fonction paire on a : (? ) = ( ). C'est ce résultat qu'il faudra vérifier pour prouver qu'une fonction est paire. Méthode :

Comment montrer quune fonction est convexe ou concave: la

Comment montrer qu'une fonction est convexe ou concave: la méthode. On va voir sur cette fiche

Agrégation Interne Fonctions convexes Ce probl`eme est en relation

Montrer qu'une fonction f de R dans R est affine si et seulement si

Agrégation Externe de Mathématiques F. Boyer Aix-Marseille Université - 2013/2014

Fonctions convexes

Tout ce que vous avez toujours voulu savoir sans jamais oser le demander

1 Dimension 1

Définition 1SoitIun intervalle deRetf:I!R. On dit quefest convexe si f(x+ (1)y)f(x) + (1)f(y);8x;y2I;82[0;1]:(1) Elle est strictement convexe si on peut mettre l"inégalité stricte pour2]0;1[etx6=y.

Une fonctionfest dite (strictement) concave sifest (strictement) convexe.-Le nombre x+ (1)y,2[0;1]est unecombinaison convexedexety, c"est-à-dire un barycentre à

coefficients positifs (voir Exercice 1).

-Interprétation géométrique :SoitCfla courbe représentative defdans le repère orthonormé usuel deR2.

On fixe deux pointsxy2I.

Tout pointz2[x;y]s"écrit de manière unique sous la formez=x+ (1)y, avec2[0;1]. Le point de la courbe Cfd"abscisseza pour coordonées(z;f(z)). Le point de la corde issue des points (x;f(x))et(y;f(y))d"abscisseza pour coordonnées(z;f(x) + (1)f(y)).(x;f(x))(y;f(y))C

f(z;f(z))Ainsi, une fonction est convexe si et seulement si la courbeCfest situéeen-dessousde n"importe laquelle

de ses cordes, entre les deux extrémités de la corde en question. Exercice 1Une fonctionf:I!Rest convexe si et seulement si, pour toutn2, pour tout choix de points x

1;:::;xn2Iet de coefficients1;:::;n2Rtels que

i0;8i2 f1;:::;ng; n X i=1 i= 1; on a f nX i=1 ixi! nX i=1 if(xi):Page 1/7 Agrégation Externe de Mathématiques F. Boyer Aix-Marseille Université - 2013/2014

Proposition 2 (Inégalité des pentes)

Soitf:I!Rune fonction convexe etx < y < ztrois points deI. Alors on a la double inégalitéf(y)f(x)yxf(z)f(x)zxf(z)f(y)zy:

C f(x;f(x))(z;f(z))(y;f(y))Preuve : Pour tout x2Iety2I,y6=x, on définit les taux d"accroissements g x(y) =f(y)f(x)yx:

On remarque quegx(y) =gy(x).

Si on montre que les fonctions gasont toutes croissantes sur]1;a[\Iet sur]a;+1[\I, nous aurons bien le résultat attendu en écrivant g x(y)gx(z) =gz(x)gz(y): On fix edonc a2Iet on veut montrer quegaest croissante sur chacun des deux intervalles] 1;a[\Iet ]a;+1[\I. Soient doncx;y2Itels quea < x < y. On veut montrer quega(x)ga(y)soit encore f(x)f(a)xaf(y)f(a)ya: Commexaetyasont strictement positifs, cette inégalité est équivalente à (f(x)f(a))(ya)(f(y)f(a))(xa); ou encore f(x)(ya)(xa)f(y) +f(a)(yx); et finalement f(x)xayaf(y) +yxyaf(a): Si on pose=xaya2]0;1[, cette inégalité s"écrit f(x)f(y) + (1)f(a); et comme par ailleurs, on a x=y+ (1)a;

on voit que l"inégalité attendue est bien exactement de la forme (1), ce qui conclut la preuve dans le cas

a < x < y.

Le casx < y < ase traite de façon similaire (en prenant garde éventuellement aux changements de sens

dans les inégalités quand on multiplie par des quantités négatives).

Page 2/7

Agrégation Externe de Mathématiques F. Boyer Aix-Marseille Université - 2013/2014

Théorème 3

On suppose queIest ouvert. Soitf:I!Rune fonction.

Si fest convexe, alors on a

-fest continue surI. -fadmet des dérivées à gauche et à droite en tout point deIet on a f

0(x)f0(x+)f0(y);8x;y2I;tqx < y:

2. Réciproquement, si fest dérivable dansIet quef0est croissante alorsfest convexe.Preuve : 1. Soit x2Ietr >0tel que[xr;x+r]I. D"après l"inégalité des pentes, on a pour tout" >0, f(x)f(xr)r f(x+")f(x)" f(x+r)f(x)r et donc, en particulier les quotients g x(x+") =f(x+")f(x)"

restent bornés quand"tend vers0, ce qui montre la continuité à droite def. Par ailleurs, l"inégalité des

pentes permet de montrer que"7!gx(x+")est une fonction croissante (et minorée) de". Ainsi la limite

lim "!0+f(x+")f(x)" existe.

Le même raisonnement montre la continuité à gauche defainsi que l"existence de la dérivée à gauche.

Enfin, on utilise à nouveau l"inégalité des pentes pour obtenir f(x)f(x")" f(x+")f(x)" ;8" >0; et donc par passage à la limite f

0(x)f0(x+):

2. On fix ex < ydansIet2]0;1[. On applique le théorème des accroissements finis entrexetx+(1)y d"une part et entrex+(1)yetyd"autre part, ce qui nous donne l"existence d"un1et d"un2vérifiant

12]x;x+ (1)y[;etf(x+ (1)y)f(x) =f0(1)(1)(yx);

22]x+ (1)y;y[;etf(y)f(x+ (1)y) =f0(2)(yx):

Ainsi, nous avons

f(x) + (1)f(y)f(x+ (1)y) =(1)(yx)f0(2)f0(1):

Comme par construction nous avons1< 2et quef0est croissante, nous avons bien prouvé la convexité

def. Sif0est strictement croissante, le même calcul montre quefest strictement convexe.Remarque 4

Si In"est pas ouvert, la continuité au bord n"est pas assurée (par exemple si on prendI= [0;1]et la

fonctionfnulle sur]0;1]et qui vaut1en0, on a bien une fonction convexe non continue en0.

Une fonction con vexen"est pas nécessairement déri vable.On peut penser à l afonction f(x) =jxjsur

Rpar exemple.

Si fest deux fois dérivable surI, alors elle est convexe (resp. strictement convexe) si et seulement si

000(resp.f00>0) surI.Page 3/7

Agrégation Externe de Mathématiques F. Boyer Aix-Marseille Université - 2013/2014

Exemple 5

-x7!x2etx7!exsont convexes surR. -x7!log(x)est concave surR+.

Applications : inégalités arithmético-géométriques, inégalité de Young, etc ...Proposition 6 (Deuxième caractérisation géométrique)

SoitIun intervalle ouvert deR,f:I!Rune fonction convexe eta2I. Alors, pour tout

2[f0(a);f0(a+)], la droite de pentepassant par le point(a;f(a))est située sous la courbe

représentativeCf.C

f(a;f(a))pentef0(a+)pentef0(a)pente2]f0(a);f0(a+)[En particulier, sifest dérivableCfest située au-dessus de n"importe laquelle de ses tangentes.

Réciproquement, sifest dérivable et siCfest au-dessus de toutes ses tangentes, alorsfest convexe.Preuve :

La première partie de la proposition découle immédiatement de l"inégalité des pentes.

Il ne nous reste qu"à montrer le dernier point. Supposons quefest dérivable et queCfest au-dessus de toutes

ses tangentes. On fixex < ydansI. En écrivant l"équation de la tangente àCfen(x;f(x))puis en(y;f(y))nous

obtenons les inégalités f(y)f(x) + (yx)f0(x); f(x)f(y) + (xy)f0(y): Ceci s"écrit encore (attention on ayx >0etxy <0) f(y)f(x)yxf0(x); f(y)f(x)yxf0(y);

et implique donc quef0(x)f0(y). Ceci montre quef0est croissante et donne donc bien le résutat.Exercice 2 (Fonctions convexes et fonctions affines)

SoitIun intervalle ouvert deR. On noteA(I)l"ensemble des fonctionsaffinesdéfinies surI. 1. Montrer qu"une fonction ':I!Rest convexe si et seulement si pour toutx2I, on a '(x) = sup h2A(I) h'h(x):

2.Application : Inégalité de Jensen. Soit':I!Rune fonction convexe etune mesure de

probabilité surI, alors pour toute fonctionf2L1(I;)nous avons Z I fd Z I 'f d; cette dernière intégrale étant éventuellement égale à+1.Page 4/7 Agrégation Externe de Mathématiques F. Boyer Aix-Marseille Université - 2013/2014

Il est bon de remarquer que, siest une mesure de probas discrète, l"inégalité de Jensen donne exactement le

résultat de l"exercice 1.

Corrigé :

1. Pour n"importe quelle fonction ':I!R, on définit ~'(x) = sup h2A(I) h'h(x);8x2I:

Si 'est convexe, on a vu qu"il existe des droites sous la courbeCf, c"est-à-dire que l"ensemble des

fonctions affineshinférieures à'est non vide et en particulier~'est bien définie et vérifie~''.

Pour tout pointx2I, on a même vu qu"on peut trouver une fonction affinehtelle queh(x) ='(x) eth'(en choisissant sa pente dans l"intervalle['0(x);'0(x+)]). Ceci prouve bien finalement que Supposons maintenant que ~'='. En particulier, cela implique que l"ensembleHdes fonctions affinesh telles queh'est non vide. On fixe une telle fonction affineh2Hetx;y2I,2[0;1]. Commehest affine, on a l"égalité h(x+ (1)y) =h(x) + (1)h(y):

Commeh'nous en déduisons

h(x+ (1y)'(x) + (1)'(y):

Cette inégalité étant vraie pour touth2H, on peut prendre le supremum par rapport àhet obtenir

~'(x+ (1)y)'(x) + (1)'(y): Comme~'=', on a bien l"inégalité de convexité pour'. 2.

On reprend les notations précédentes. Pour t outefonction af fineh, que l"on écrith(t) =t+, nous avons

h Z I f d =Z I f d+; et donc, comme R

Id= 1, nous avons

h Z I f d =Z I hf dZ I 'f d la dernière intégrale étant éventuellement infinie.

On prend maintenant le supremum par rapport àh2Het on obtient le résultat, grâce à la question précé-

dente.2 Dimension supérieure (finie)

La définition de la convexité est inchangée si ce n"est que l"on doit se placer sur un ensemble qui est lui-même

convexe pour qu"elle ait un sens (les intervalles sont les convexes deR!) Définition 7SoitCune partie convexe deRd. Une fonctionf:C!Rest dite convexe si

f(x+ (1)y)f(x) + (1)f(y);8x;y2C;82[0;1]:Comme en dimension1, on peut montrer que les fonctions convexes définies sur des ouverts convexes deRd

sont continues, mais on ne peut pas directement utiliser l"inégalité des pentes bien sûr.

Page 5/7

Agrégation Externe de Mathématiques F. Boyer Aix-Marseille Université - 2013/2014

Théorème 8

SoitUun ouvert convexe non vide deRdetf:U!Rune fonction différentiable surU.

La fonction fest convexe si et seulement si le graphe defest situé au-dessus de tous ses hyperplans

tangents.

La fonction fest convexe si et seulement si sa différentielle est croissante (on dit aussi monotone) au

sens suivant

8x;y2U;(Df(x)Df(y)):(xy)0:

Si on utilise le produit scalaire euclidien surRdet la notion de gradient, cela s"écrit hrf(x) rf(y);xyi 0:

Si de plusfest de classeC2surU, nous avons

fest convexe()D2f(x)est symétrique positive pour toutx2U.Exemple 9 1. Soit A2Md(R)une matrice symétrique etb2Rd. Alors la fonctionfdéfinie par f(x) =12 hAx;xi hb;xi;8x2Rd; est convexe si et seulement siAest une matrice positive. Elle est strictement convexe si et seule- ment siAest définie positive. 2. Si M2Md;p(R)est une matrice rectangle quelconque etb2Rp, la fonction définie par f(x) =kMxbk22;8x2Rd; est convexe.

Elle est strictement convexe si et seulement si KerM=f0g.La notion de convexité apparaît assez naturellement en optimisation essentiellement pour la raison suivante :

Théorème 10 (Convexité et extremums)Soitf:C!Rune fonction convexe. Nous avons les propriétés suivantes.

1. Si x02Cest un minimiseur local def, alors c"est un minimiseur global. De plus, l"ensemble des minimiseurs (locaux et donc globaux) defest un convexe (non vide) de C. Enfin, sifest strictement convexe, ce minimum est atteint en un unique point. 2. Si fest différentiable en un pointx02Cet que ce point est un point critique def(i.e. tel que

Df(x0) = 0), alorsx0est un minimiseur (local et donc global) def.Attention :Ce théorème ne dit pas qu"une fonction convexe admet nécessairement un minimiseur! Une condi-

tion supplémentaire est nécessaire pour en montrer l"existence. En général, on ajoute une condition ditede coerci-

vitédu typelimkxk!1f(x) = +1.

Par exemple, les fonctions affines non constantes sont convexes mais ne sont pas minorées (et a fortiori n"ad-

mettent pas de minimiseur!) quand à la fonctionx2R7!ex, elle est strictement convexe surR, minorée, mais

n"admet pas de minimiseur.

Preuve :

Soit x2C. La fonction réelle définie par

':t2[0;1]7!f((1t)x0+tx);

Page 6/7

Agrégation Externe de Mathématiques F. Boyer Aix-Marseille Université - 2013/2014

est bien définie (ici on utilise la convexité deC) et convexe carfl"est (je vous laisse vous en convaincre).

De plus, par hypothèse0est un minimum local de'et donc par l"inégalité des pentes nous avons pour tout

0< <1'()'(0)

'(1)'(0)10; ce qui s"écrit f(x0+(xx0))f(x0) f(x)f(x0):(2)

Le membre de gauche est positif pourassez petit (carx0est un minimiseur local def) et donc nous avons

f(x)f(x0); pour toutx2C. On a bien obtenu quex0est un minimiseur global. SoitMl"ensemble des minimiseurs def. Soientx;y2Met2[0;1]. Par définition de la convexité nous avons f(x+ (1)y) f(x)|{z} =inf

Cf+(1)f(y)|{z}

=inf

Cf= inf

Cf; et donc finalementf(x+(1)y) = infCf, ce qui prouve quex+(1)y2Met donc la convexité deM.

Sifest strictement convexe et queMcontient au moins deux éléments distinctsxety, alors le calcul

précédent devient fx+y2 <12 f(x) +12 f(y) = infCf; ce qui est une contradiction manifeste. 2.

On reprend les notations du point précédent et on observ equ"on peut passer à la limite quand !0dans

(2), ce qui donne

Df(x0):(xx0)f(x)f(x0);

et commeDf(x0) = 0, on obtient bien quef(x)f(x0)pour toutx2C.3 Un (petit) mot sur la dimension infinie

Encore une fois les définitions ne changent pas, mais la topologie se complique un peu. En particulier, il n"est

plus vrai que toute fonction convexe est continue, c"est pourquoi tous les théorèmes d"optimisation convexe en

dimension infinie font intervenir des hypothèses de continuité def.

C"est un sujet plus délicat et, au niveau de l"agrégation, il convient d"être très prudent sur ce terrain. Mon

conseil est de n"aborder ces questions que si c"est absolument indispensable et si vous vous sentez très à l"aise.

Page 7/7

quotesdbs_dbs47.pdfusesText_47

[PDF] Fonctions convexes 1 Dimension 1

Fonctions convexes

1 Dimension 1

On fixe deux pointsxy2I.

1;:::;xn2Iet de coefficients1;:::;n2Rtels que

Proposition 2 (Inégalité des pentes)

On remarque quegx(y) =gy(x).

Page 2/7

Théorème 3

On suppose queIest ouvert. Soitf:I!Rune fonction.

Si fest convexe, alors on a

0(x)f0(x+)f0(y);8x;y2I;tqx < y:

0(x)f0(x+):

12]x;x+ (1)y[;etf(x+ (1)y)f(x) =f0(1)(1)(yx);

22]x+ (1)y;y[;etf(y)f(x+ (1)y) =f0(2)(yx):

Ainsi, nous avons

Rpar exemple.

000(resp.f00>0) surI.Page 3/7

Exemple 5

2[f0(a);f0(a+)], la droite de pentepassant par le point(a;f(a))est située sous la courbe

2.Application : Inégalité de Jensen. Soit':I!Rune fonction convexe etune mesure de

Corrigé :

Commeh'nous en déduisons

Id= 1, nous avons

Page 5/7

Théorème 8

8x;y2U;(Df(x)Df(y)):(xy)0:

Si de plusfest de classeC2surU, nous avons

Preuve :

Soit x2C. La fonction réelle définie par

Page 6/7

0< <1'()'(0)

Cf+(1)f(y)|{z}

Cf= inf

Df(x0):(xx0)f(x)f(x0);

Page 7/7