[PDF] [PDF] Convexité en optimisation, convexité forte

[PDF] pdf 173k

On peut déterminer si une fonction est convexe ou concave grâce au comportement de la forme quadratique associée à sa matrice hessienne (la matrice des 

[PDF] Fonctions homogènes, concaves et convexes - LaBRI

Fonctions homog`enes, concaves et convexes Hervé Hocquard matrice hessienne de f a toutes ses valeurs propres négatives ou nulles La fonction f est  

[PDF] COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

2 2 2 Exemples des fonctions convexes, strictement convexes et fortement (la matrice Hessienne de f est le Jacobien du gradient de f ou le gradient de la

[PDF] Cours doptimisation ENSAI Rennes

15 mar 2019 · Lorsque f est de classe C2, la convexité se traduit par une propriété de la matrice hessienne Théor`eme 4 4 2 Si K est convexe et si f est de 

[PDF] Convexité en optimisation, convexité forte

fonction convexe définie sur Ω ⊂ V est différentiable presque partout (au sens de la différentielle seconde s'identifie à la matrice hessienne lorsque f est deux

[PDF] OptiAlgo cours

(a) Comme pour tout x ∈ Rn, la matrice hessienne ∇2f(x) est définie positive, f est strictement convexe d'après le Théorème 2 15 sur les fonctions convexes deux 

[PDF] Analyse du problème

Une fonction f : R n −→ R est dite convexe si, pour tout x, y ∈ R n Fonction strictement convexe La matrice hessienne est toujours symétrique Analyse du  

[PDF] Régime Aménagé - UFR 02 Mathématique 2 Cours d - SAMM

Une fonction f de classe C2 sur I ∈ R est dite convexe (resp concave) si pour tout X D'après le théorème de Schwartz, la matrice hessienne est symétrique

[PDF] Optimisation statique Lagrangien et conditions de Kuhn et Tucker

La matrice hessienne bordée de f est une matrice symétrique carrée d'ordre n + Soit f une fonction de plusieurs variables définie sur un ensemble convexe S

[PDF] Chapitre Concavité et convexité des fonctions de plusieurs variables

Ainsi, l'étude de la concavité et de convexité de ces fonctions repose pleinement sur la détermination de la matrice Hessienne Par ailleurs, ce chapitre se veut 

[PDF] convocation bac 2017 cote d'ivoire

[PDF] convocation bac 2017 en ci

[PDF] convocation bac 2017 ivoirien

[PDF] convocation bepc

[PDF] convocation bepc 2017

[PDF] convocation bepc 2017 ci

[PDF] convocation categorie 3 police

[PDF] convocation ccf cap

[PDF] convocation ccf eps

[PDF] convocation ccf word

[PDF] convocation cnc 2017

[PDF] convocation cns luxembourg

[PDF] convocation dscg 2017

[PDF] convocation examen prof

[PDF] convocation jury examen

Master MF - CSMI

Convexité en optimisation, convexité forteDans ce qui suit, on se place dans un espace de HilbertVmuni d"un produit scalaireh;i.

Dans ce qui suit, on suppose quef:KV!Rest continue,Kdésignant une partie quelconque deV. On considère le problème d"optimisation inf x2Kf(x)(1)Définition 1 : Ensembles et fonctions convexes 1. On dit qu"un ensemble KVest convexe si, et seulement si pour tous(x1;x2)2 K

2ett2[0;1],tx1+ (1t)x22K.

2. Soit K, un convexe inclus dansV. La fonctionf:K!Rest diteconvexesi, et seulement si

8(x1;x2)2K2;8t2[0;1]; f(tx1+ (1t)x2)tf(x1) + (1t)f(x2):

On dit quefeststrictement convexesi l"inégalité ci-dessus est stricte pour x6=y,t2]0;1[. Rappelons que toute fonction convexe possède une régularité minimale en dimension finie. Sifest une fonction convexe définie sur un ouvert convexe deV, alorsfest continue sur et lipschitzienne sur tout compact de . (voir par exemple [2] pour la preuve dans

Vet [3] pour le casn= 1)

De la propriété de Lipschitz découle, en utilisant le théorème de Rademacher, que toute

fonction convexe définie sur Vest différentiable presque partout (au sens de la mesure de Lebesgue) sur son domaine.

À présent, nous allons rappeler un fait bien connu mais néanmoins fort utile en pratique. On

peut caractériser assez facilement une fonction convexe dans le cas où celle-ci est régulière (dif-

férentiable partout ou deux fois différentiable partout). Rappelons en préliminaire que sifest différentiable surV, alors sa différentielleV3h7! Df(x)hest linéaire continue. De plus, en vertu du théorème de Riesz, il existe un unique élément deVappelégradient defenxet notérf(x)tel que

8h2V; dfx(h) =hrf(x);hi:

Dire quefest deux fois différentiable signifie qu"il existe une application linéaireL(x0) :V!V0

telle que df x0+=dfx0+L(x0)+o!0(kkV)2V0: La différentielle seconde def, notéed2fx0est alors l"applicationL(x0) :V!V0. Elle est

difficile à évaluer en pratique carL(x0)est un élément deV0. En la faisant agir sur un élément

1 h2V, on obtient une forme bilinéaire continue surVV, que l"on noterahd2fx0;hi. Il est alors aisé de montrer que f(x0+h)f(x0) =dfx0(h) +12 hd2fx0h;hi+oh!0(khk2): Si de plus, l"applicationx07!d2fx0est continue enx0, on dira quefest de classeC2enx0. Dans le cas de la dimension finie (V=Rn), ces formules revêtent un aspect particulièrement

sympathique puisque la différentielle seconde s"identifie à la matrice hessienne lorsquefest deux

fois différentiable.Théorème 2 : Caractérisation des fonctions convexes dans le cas régulier

1. Si f:V!Rest différentiable, on a les équivalences entre (i)fest convexe; (ii)f(y)f(x) +hrf(x);yxi,8(x;y)2V2; (iii)hrf(y) rf(x);yxi 0,8(x;y)2V2. 2. On a équivalence entre convexité stricte et les inégalités (ii)et(iii)précédentes rendues strictes, pourx6=y. 3. Si f:V!Rest deux fois différentiable, on a les équivalences entre (i)fest convexe;

(ii)pour touth2V,hd2fx0h;hi 0.Démonstration.1.(i) =)(ii). Soitt2[0;1],(x;y)2V2. Alors, par convexité def,f(tx+(1

t)y)(1t)f(x) +tf(y), d"oùf(x+t(yx))t[f(y)f(x)], puis on divise partet on fait tendretvers 0. (ii) =)(iii). On écrit(ii)avec(x;y), puis(y;x)et on somme.

(iii) =)(ii). On utilise la formule de Taylor Mac-Laurin à l"ordre 11, appliquée à la fonction

t2[0;1]7!f(x+t(yx)). Il existet2[0;1]tel que f(y) =f(x) +hrf(x+t(yx));yxi =f(x) +hrf(x);yxi+hrf(x+t(yx)) rf(x);yxi; et ce dernier terme est positif par(iii), donc on a(ii). (ii) =)(i). On posext= (1t)x+ty=x+t(yx)et on écrit(ii)avecx=xt,y=xou y. On a : f(x)f(xt) +hrf(xt);xxti f(y)f(xt) +hrf(xt);yxti; sachant quexxt=t(yx),yxt= (1t)(yx). On multiplie alors les deux inégalités respectivement par1tett, puis on les somme :

(1t)f(x) +tf(y)(1t+t)f(xt) =f(xt):1. Rappelons la formule de Taylor Mac-Laurin : soitf: [;]!Rune fonctionN+ 1fois dérivable. Alors,

il existe

2];[tel que

f() =f() +NX k=1()kk!f(k)() +()N+1(N+ 1)!f(N+1)(

Remarquons que lorsqueN= 1, la formule de Taylor Mac-Laurin coïncide avec la formule des accroissements

finis. 2

2.Il s" agitd"adapter a vecb eaucoupde pré cautionla démonstration précéde nte.Cet exercice est laissé

au lecteur. Attention cependant à être prudent lors des passages à la limite afin de conserver des

inégalités strictes.

3.(i) =)(ii). On applique la propriété(iii)précédente avecxety=x+th. On obtient

hrf(x+th) rf(x);thi 0. On divise alors cette inégalité part2puis on fait tendretvers

0, ce qui fournit :hd2fxh;hi 0,8(x;h)2V2.

(ii) =)(i). On applique la formule de Taylor-Mac Laurin à l"ordre deux : f(y) =f(x) +hrf(x);yxi+12 hd2fx+t(yx)(yx);yxi f(x) +hrf(x);yxi;8(x;y)2V2;

qui est une condition équivalente à la convexité d"après la première partie du théorème.Exemple 3Convexité d"une fonction quadratique

On considère la fonction

f:Rn!R x7!f(x) =12 hAx;xi hb;xi+c; avecAune matrice réelle symétrique,bun vecteur deRnetcune constante donnée. On peut montrer que pour toutx2Rn,rf(x) =AxbetHessf(x) =A. En particulier, on déduit immédiatement

de ce calcul et du théorème quefest convexe si, et seulement siAest semi-définie positive, et

strictement convexe si, et seulement siAest définie positive. La convexité est en général un outil précieux en optimisation.Théorème 4 : Soit le problème(1)avecfconvexe etKconvexe (éventuellement de dimension infinie).

Alors,

1. tout minimum lo calest un minimum global. 2.

si fest strictement convexe, il y a au plus un minimum.Démonstration.1.S oitx, un minimum local pour le problème (1). Par l"absurde, supposons qu"il

existey2Ktel quef(y)< f(x). Soityt=ty+ (1t)x, avect2]0;1[. Alors,f(yt)f(x)si test suffisamment petit (en effet, sitest petit,kytxk=tkyxkl"est aussi...). La convexité defimplique quef(x)f(yt)tf(y) + (1t)f(x), ce qui montre quef(y)< f(x)f(y).

C"est absurde et il s"ensuit quexminimisefsurK.

2. Si x1etx2sont deux solutions globales de (1), alors six16=x2, f x1+x22 <12 f(x1) +12 f(x2) =f(x1); ce qui est absurde. Cela implique donc l"unicité.3

Définition 5 : Fonction-elliptique

SoitKV, un convexe. Une fonctionf:K!Rest ditefortement convexeou uniformément convexeou-convexeou-elliptiques"il existe >0tel que, pour tous(x;y)2K2,t2[0;1], f(tx+ (1t)y)tf(x) + (1t)f(y)2 t(1t)kxyk2:

Il est tout à fait clair que l"ellipticité implique la stricte convexité qui implique elle-même la

convexité. On notera que la convexité correspond formellement au cas= 0. Bien sûr, les réci-

proques sont fausses. Exemple 6Liens entre les différentes notions de convexité

Nous donnons ici quelques exemples et contre-exemples élémentaires, qui seront complétés par la suite

(en particulier, on étudiera de près la convexité des fonctionnelles quadratiques en dimension finie).

1. T outefonction affine de RdansRest convexe mais non strictement convexe. 2.

D"ap rèsla définition, il est clair qu"une fonction -elliptique est strictement convexe, et donc

convexe. 3. La fonction x7! lnxest strictement convexe sur]0;+1[, mais non elliptique. Prouvons-le!

Cette fonction est strictement convexe (on peut utiliser le critère sur les dérivées secondes par

exemple, que nous rappellerons ultérieurement). Reste à montrer que cette fonction n"est pas elliptique. Raisonnons par l"absurde, en supposant l"existence de >0tel que, pour tous (x;y)2]0;+1[2,x6=y, ett2[0;1], ln(tx+ (1t)y)La proposition ci-dessous examine plus précisément le lien entre "convexité" et "uniforme convexi-

té". Elle fournit également un critère permettant de vérifier l"uniforme convexité d"une fonction.Propriété 7 :

Comme précédemment,fdésigne une fonction deVdansR. 1. La fonction fest-elliptique si et seulement si la fonctionf2 kk2est convexe. 2. On supp oseque fest continue. Alors, la fonctionfest-elliptique si, et seulement si il existe >0tel que, pour tout(x;y)2V2, f x+y2 f(x) +f(y)2 8 kxyk2:Démonstration.1.P osonsg(x) =f(x)2 kxk2. En développantktx+(1t)yk2et en regroupant les termes correctement, on trouve tg(x)+(1t)g(y)g(tx+(1t)y) =tf(x)+(1t)f(y)f(tx+(1t)y)2 t(1t)kxyk2; ce qui prouve l"équivalence annoncée. 4

2.Le sens direct est immédiat et s"obtien ten c hoisissantt=12

Le sens réciproque est un peu plus délicat. Nous allons procéder par récurrence. Pour toutn2N,

on noteKn=f2[0;1];2n2Ng. FixonsxetydansV. On appellePnla propriété : "Pour toutt2Kn, l"inégalité f(tx+ (1t)y)tf(x) + (1t)f(y)2 t(1t)kxyk2;

est vérifiée". L"initialisation de cette propriété est immédiate. Montrons son hérédité.

Soitt2Kn+1nKn, alors2t2Kn. Il existe(t1;t2)2K2ntels quet1< t2ett=t1+t22 . Puisquef vérifie l"inégalité particulière de-convexité énoncée dans la proposition, f(tx+ (1t)y) =f(t1x+ (1t1)y) + (t2x+ (1t2)y)2 12 (f(t1x+ (1t1)y) +f(t2x+ (1t2)y)) 8 (t2t1)2kxyk2:

Or, puisque l"inégalité de "-ellipticité" a été supposée vraie surKn, on en déduit

f(tx+ (1t)y)t1f(x) + (1t1)f(y) +t2f(x) + (1t2)f(y)2 4 (t1(1t1) +t2(1t2))kxyk28 (t2t1)2kxyk2 =tf(x) + (1t)f(y)4 (t1(1t1) +t2(1t2) 12 (t2t1)2)kxyk2 =tf(x) + (1t)f(y)2 t(1t)kxyk2;

ce qui prouve que l"inégalité de "-ellipticité" est alors valable pour tout élément deKn+1. On

en déduit par récurrence que l"inégalité est valable pourt2S n2NKn. Commefest continue,

l"inégalité reste valable sur l"adhérence de l"union desKn, c"est-à-dire sur[0;1].Dans le cas où la fonctionfest régulière, comme pour la convexité, il existe des caractérisations

de la convexité uniforme. On peut voir ces caractérisations comme des corollaires du théorème .Corollaire 8 : Caractérisation des fonctions uniformément convexes dans

le cas régulier 1. Si f:V!Rest différentiable, on a les équivalences (i)fest-elliptique; (ii)f(y)f(x) +hrf(x);yxi+2 kyxk2,8(x;y)2V2; (iii)hrf(y) rf(x);yxi kyxk2,8(x;y)2V2. 2. Si f:V!Rest deux fois différentiable, on a les équivalences (i)fest-elliptique;

(ii)hHessf(x)h;hi khk2,8x2V,8h2V.Démonstration.1.Grâce à la prop osition, (i)équivaut à dire queg(x) =f(x)2

kxk2est convexe. or,rg(x) =rf(x)x. En écrivant alors les conditions(i),(ii)et(iii)du théorème , on obtient exactement les conditions(ii)et(iii)du corollaire pourf. 2. La preuv edécou leimmédia tementdu théorème , en p osantcomme précédemmen tg(x) = f(x)2 kxk2et en remarquant que Hessg(x) =Hessf(x)I.5

Exemple 9-convexité d"une fonction quadratique

Revenons sur l"exemple de la fonctionfdéfinie par f:V!R x7!f(x) =12 hAx;xi hb;xi+c;

avecAune matrice réelle symétrique,bun vecteur deVetcune constante donnée. On a déjà prouvé

dans l"exemple 3 quefest strictement convexe surVsi, et seulement siAest définie positive, et que de plusHessf(x) =Apour toutx2V. Étant donné queAest symétrique réelle, on peut la

diagonaliser dans une base orthonormée réelle de vecteurs propres notéefeig1in. Le spectre deA

rangé par ordre croissant est : 1 n: On peut alors écrire queA=P>DP, avecP2On(R), la matrice telle queP>=P1= [e1en], où les vecteurse1,,en, sont écrits en colonne, etD=diag(1;;n). Posonsu=Ph. Alors, hAh;hi=nX i=1 iu2i1n X i=1u

2i=1juk2=1khk2:

On en déduit quefest1-elliptique. On peut d"ailleurs montrer facilement que1est la meilleurequotesdbs_dbs18.pdfusesText_24