[PDF] Notes doptimisation différentiable

View - Download Notes doptimisation différentiable

Previous PDF

Next PDF

Optimisation dierentiable ENSAE 2020

Notes d'optimisation dierentiable

Hicham Janati

hicham.janati@inria.fr

Janvier 2020Disclaimer : ces notes constituent un resume et non un substitut du cours d'Optimisation dierentiable.

1 Calcul dierentielObjectifs :

1.

Di erentielleet gradien t

2.

D eriveespartielles et leur con tinuite

3.

Chain rule

4. Hessienne e tappro ximationde second ordre notations

On notehx;yi=Pn

i=1xiyi=x>yle produit scalaire Euclidien dex;y2Rn

La transposee d'une matriceAest noteeA>.

La notationx=o(hp) est equivalente ax=khkp"(h) ou"est une fonctionRn!Rcontinue en 0 et"(0) = 0. k :kdenote la norme Euclidienne :kxk=pP ix2i. Pour une matrice symmetrique,H0 signie queHest denie-positive, cadx>Hx >0 pour toutxnon nul (ou encore toutes ses valeurs propres sont strictement positives).

Denition 1

(Dierentielle et Jacobienne).Soitf:Rn!Rmetx2R. On dit quefest dierentiable enxsi et seulement s'il existe une application lineaireJx:Rn!Rmtel que pour touth2Rn: f(x+h) =f(x) +Jx(h) +o(h) (1)

L'applicationJxest dite dierentielle defenx.

CommeJxest lineaire, elle peut ^etre representee par une matriceJf(x)2Rmnappelee Jacobienne defet on aJf(x)ij=@fi@x j(x).

Exemple 1.

SoitA2Rm;n. La fonction lineairef:x7!Axest dierentiable et sa hessienne est donnee parJf(x) =Apour toutx2Rn. En eet,f(x+h) =A(x+h) =Ax+Ah=f(x) +Ah.

Denition 2

(Gradient d'une fonction scalaire).Soitf:Rn!Retx2Rune fonction dierentiable. La dierentielle defenxest une application lineaire donc il existeax2Rntel que pour touth2Rn: f(x+h) =f(x) +hax;hi+o(h) (2) Le vecteuraxest dit gradient defenxet on note, pour toutxoufest dierentiable :rf(x) =ax. En plus, les coordonnees derf(x)sont donnees par les derivees partielles def:rf(x)i=@f@x i(x).

Reciproque : si les derivees partiellesx!@f@x

i(x)existent et sontcontinues, alorsfest dierentiable et son gradient est donne parrf(x) =@f@x i(x) hicham.janati@inria.fr 1

Optimisation dierentiable ENSAE 2020

Exemple 2.La fonctionf:x7!12

kxk2est dierentiable etrf(x) =x. En eet,12 kx+hk2= 12 kxk2+hx;hi+12 khk2=f(x) +hx;hi+o(h). Pour chercher la derivee partielle d'une fonctionfenx0suivant une directionu6= 0, il sut de calculer la limite : lim h!0f(x0+hu)f(x0)h (3)

L'exercice suivant montre que l'existence des derivees partielles (sans leur continuite) ne garantit pas la

continuite def{ et donc sa dierentiabilite.

Exercice 1

(Mi-parcours 2018).Montrer que les deux fonctions suivantes admettent des derivees partielles en (0, 0) dans toutes les directions deR2sans pour autant ^etre continues en (0, 0).

1.f(x;y) =y2log(jxj)ifx6= 0

0ifx= 0

2.f(x;y) =(

x2yx

4+y2if(x;y)6= (0;0)

0if(x;y) = (0;0)

L'existence des derivees partielles sans leur continuite est donc en general insusante pour avoir

la dierentiabilite def. De m^eme, si une fonction est dierentiable, ses derivees partielles ne sont pas

forcement continues. Lorsque c'est le cas, il s'agit du cas (plus fort) d'une fonction de classeC1:

Denition 3

(Fonction de classeC1).Soitf:Rn!R. On dit quefest de ClasseC1sifest dierentiable et ses derivees partielles sont continues.

Proposition 1

(Chain rule).Soitf:Rn!Rmetg:Rm!Rpdeux applications dierentiables. Leur composeeh=gofest dierentiable et sa Jacobienne est donnee par le produit matriciel des Jacobiennes :

Jgof(x) =Jg(f(x))Jf(x) (4)

Remark1.Pour une fonction scalaire dierentiable (cad a valeurs dansR), la Jacobienne est la transposee

du gradient. Dans la proposition ci-dessus, sigest scalaire (p= 1) alorshl'est aussi est on a : rh(x) =Jf(x)>rg(f(x)) (5)

Exemple 3

(Changement de variable lineaire).Dans la remarque ci-dessus, sif:x7!AxavecA2Rm;n alors :rh(x) =A>rg(Ax).

Exercice 2

(Les classiques).On dit quexest un point stationnaire (ou point critique) d'une fonctionf dierentiable enxsi et seulement sirf(x) = 0. Soita2Rn,b2RmetA2Rmn. Soit une fonction dierentableg:Rm!R. Les fonctions suivantes sont-elles dierentiables? Donnez le gradient (La ou il existe) et les points critiques eventuels des fonctions deRndansRsuivantes en fonction dea;b;Aetrg.

1.x7! ha;xi=a>x

2.x7! kxk2

3.x7! kAxbk2

4.x7!g(Ax)

5.x7! kxk

Denition 4

(Hessienne d'une fonction scalaire).Soitf:Rn!Retx2Rune fonction dierentiable. On dit quefest deux fois dierentiable enxsi et seulement s'il existe une forme bilineaire symetrique

S:RnRn!Rtel que pour touth2Rn:

f(x+h) =f(x) +hrf(x);hi+12

Sx(h;h) +o(h2) (6)

CommeSxest bilineaire symetrique, elle admet une representation matricielle donnee par :Hf(x)ij= @2f@x i@xj(x).Hf(x)est la Hessienne defenxet(6)devient : f(x+h) =f(x) +rf(x)>h+12 h>Hf(x)h+o(h2) (7) hicham.janati@inria.fr 2

Optimisation dierentiable ENSAE 2020Remark2 (Hessienne comme Jacobienne).L'ecriture matricielle permet de voir la Hessienne comme la

Jacobienne derf. Souvent, il est plus facile de retrouver la Hessienne a partir du gradient. S'il existe

une application lineaireJxtelle que : rf(x+h) =rf(x) +Jx(h) +o(h) (8)

AlorsHf(x) =Jx.

Exercice 3.Calculez la Hessienne des fonctions 1 - 2 - 3 de l'exercice2 .

2 Optimisation sans contraintesObjectifs :

1. Utiliser la co ercivitep ourmon trel'existence de solution 2. Etude de points critiques avec les criteres de premier et second ordre 3. Con vexiteet courbure d'une fonction 2.1 Existence Soitf:Rn!Rune fonction deux fois dierentiable surRn. On s'interesse aux probleme : min x2Rnf(x) (9) Le probleme(9)peut eventuellement ne pas admettre de solution, si par exemplefn'est pas minoree. Une condition susante pour qu'une solution existe est la coercivite Denition 5(Coercivite).On dit quefest coercive si et seulement si :limkxk!+1f(x) = +1 Proposition 2.Si une fonction continuefest coercive, alors le probleme(9)admet une solution.

Exemple 4.

Soita2RnLa fonctionf:x7! kxk2 hx;aiest coercive. Par l'inegalite de Cauchy-

Schwartz :f(x) kxk2 kxkkak !+1whenkxk !+1.

2.2

Etude de points critiques

Souvent, on se contente de trouver des solutions locales au probleme. S'il existex?tel quef(x?) f (x)8xalorsx?est un minimiseur global def, solution de(9). S'il existex?etr >0 tel que f(x?)f(x)8xkxx?k ralorsx?est un minimiseur local def. Proposition 3.Soitx?un minimiseur local defalorsrf(x?)= 0. proof.Il existe un voisinageNdex?tel que8x2 Nf(x?)f(x). Soita2Rnett >0, on denit l'interpolation :xt=ta+x?. On voit que sitest assez petit,xt2 Net donc, pourtassez petit on peut ecrire l'equation de premier ordre defenxtautour dex?: f(x?)f(xt) )f(x?)f(x?+ta) )f(x?)f(x?) +hrf(x?);tai+o(ta) )0 hrf(x?);tai+o(t)kak )0 hrf(x?);ai+o(t)t kak )0 hrf(x?);ai hicham.janati@inria.fr 3

Optimisation dierentiable ENSAE 2020Local maximaGlobal maximumLocal minimaGlobal minimumSaddle pointFigure1 { Exemples de points critiques

ou on a divise partavant de passer a la limitet!0.

Commeaest arbitraire dansRn, on arf(x?) = 0.On remplacantfparf, on voit que tout maximiseur local defannule egalement le gradient def.

Les points annulant le gradient defsont appelespoints critiquesoupoints stationnaires. Pour connaitre

leur nature, il faut aller au second ordre et evaluer la Hessienne def: Proposition 4.Soitx?un point critique def. Alors :

1.Hf(x?)0)x?est un minimiseur local.

2.Hf(x?)0)x?est un maximiseur local.

proof.Soita2Rnett >0. On a : f(x?+ta)f(x?) ==0 z}|{ hrf(x?);tai+12 t2a>Hf(x?)a+kak2o(t2) f(x?+ta)f(x?)t 2=12 a>Hf(x?)a+kak2o(1) Donc pourtassez petit, le signe du membre de gauche est le signe dea>Hf(x?)a, et commeaest arbitraire on obtient 1 et 2.Exercice 4 (Examen 2018).Calculer le gradient et la Hessienne des fonctions suivantes. En deduire les points critiques des fonctions suivantes et determiner leur nature

1.f: (x;y)2RR+7!x2py

2.f: (x;y)2R+R+7!pxy

3.f: (x;y)2RR7!x2+y2

La proposition

3 donne une condition susa ntep ourd eterminersi un p ointc ritiqueest un minimiseur ou maximiseur local. Si en revanche la Hessienne a des valeurs propres de signe oppose ou une valeur

propre nulle, ce critere de deuxieme ordre ne permet pas de determiner la nature du point critique. En eet,

si par exemple la Hessienne a une valeur propre nulle, il faudra aller a un ordre d'approximation superieur

pour evaluer le signe de la courbure de la fonction. En pratique, pour un probleme de minimisation sans

contraintes, apres avoir enumere tous les points critiques, il sut d'evaluerfen ces points et comparer

les valeurs obtenues : car si un minimiseur global existe, il doit ^etre parmi ces points critiques. L'exercice

suivant illustre cette situation. hicham.janati@inria.fr 4

Optimisation dierentiable ENSAE 2020fL'épigraphe de f est convexeEnsembles convexesEnsembles non-convexesFonctions convexesFonctions non-convexesfL'épigraphe de f est non-convexefffxySegment [x, y]

non inclusFigure2 { Exemples d'ensembles et fonctions convexes Exercice 5.Determinez les points critiques (et leur nature) des fonctions suivantes.

1.f(x;y) =x3+ 3xy215x12y.

2.g(x;y) = 3x3+xy2xy.

3.h(x;y) =x4+13

y34y2:

4.k(x;y) =x3+xy2x2yy3.

Exercice 6.Soit f :R2!Rtelle que :

f(x;y) =x4+y42x22y2+ 4xy

On s'interesse au probleme

minR2f(x;y) (P)

1. Montrez que (P) admet une solution

2. Resoudre (P)

Exercice 7.Soit f :R2!Rtelle que :

f(x;y) =14 x4xy+y2

1. Montrez que f est coercive.

2. Calculez les points critiques de f.

3. Resoudreminf.

2.3 Cas d'une fonction convexeUn ensembleCest convexe si et seulement si pour toutx;y2C, le segment liantxay(formellement

tout pointtx+(1t)ypour toutt2[0;1]) est inclus dansC. On dit qu'une fonctionfest convexe si son

epigraphe est convexe. L'epigraphe d'une fonction est tout simplement l'ensemble des points au-dessus

de son graphe : epif=f(x1;:::;xn;y)2Rn+1jf(x)yg. Cette denition admet d'autres formulations equivalentes : hicham.janati@inria.fr 5

Optimisation dierentiable ENSAE 2020(1)(2)(3)(4)(5)Figure3 { Surfaces de fonctions quadratiques - Exercice8

Proposition 5.Soitfune fonction deux fois dierentiable deRndansR. Les assertions suivantes sont equivalentes :

1.fest convexe

2. l'ensemble epi f=f(x1;:::;xn;y)2Rn+1jf(x)ygest convexe.

3.8(x;y)8t2[0;1]f(tx+ (1t)y)tf(x) + (1t)f(y)

4.8(x;x0)f(x)f(x0) +hxx0;rf(x0)i(f est superieure a toutes ses tangeantes)

5. L ahessienne de f est semi-d eniep ositivep ourtout x:Hf(x)<0. Lors quefest convexe, elle admetau plusun minimum global, atteint en potentiellementplusieurs minimiseurs . Si elle est strictement convexe, alorss'il existe, ce minimiseur est unique. En eet,

l'approximation au premier ordre d'une fonction convexe permet de montrer que tout point critique est

un minimiseur global. C'est donc une caracterisation des solutions du probleme minf.

Proposition 6.

Soitfune fonction convexe et dierentiable deRndansR.x?est un minimiseur global defsi et seulement sirF(x?) = 0.

2.4 Fonction quadratique

La proposition

3 mon treque l' etudedes p ointscritiq uespasse par l' etudede la fonction quadratique h!h>Hfh. Les fonctions quadratiques donnent l'approximation de second ordre de toute fonction deux

fois dierentiable. Comprendre le lien entre la courbure d'une fonction quadratique, sa convexite et sa

Hessienne est crucial en optimisation. Ceci est l'object de l'exercice suivant.

Exercice 8.

SoitSune matrice symmetrique dansRn;netb2Rn. On s'interesse a la fonction quadratique :f(x) =12 x>Sx+b>x. 1.

Calculez le gr adientet la Hessienne de f.

2. Quels sont les p ointscritiques de f? Discutez leur nature. 3. Montr ezque si Sa une valeur propre strictement negative,fne peut pas ^etre coercive. 4. On suppose queS<0. Trouvez une condition necessaire et susante surbetSpour qu'un minimum defexiste. 5. Prenonsn= 2. La gure3 visualise la surfac ede fpour dierentes matricesA. Determinez le signe des valeurs propres deAdans les cas suivants :

Exercice 9.

SoitAune matrice dansRm;netb2Rm. On s'interesse a la fonction quadratique : f(x) =12 kAxbk2. hicham.janati@inria.fr 6

Optimisation dierentiable ENSAE 2020

1.

Calculez le gr adientet la Hessienne de f.

2. f est-el lec onvexe? 3. f est-el lec oercive? 4.

R esoudreminf

3 Optimisation sous contraintesObjectifs :

1.

Etudier la qualication des contraintes

2.

Appliquer KKT et visualiser les probl emesdans R2

3.

Conclure par con vexiteou existence de soluti on

4.

T rouverun probl emedual equivalentSoitf:Rn!Rune fonction deux fois dierentiable surRn. EtKun ferme deRn. On s'interesse au

probleme d'optimisation suivant : minx2Kf(x) (10) Nous allons nous restreindre aux cas ouKpeut s'exprimer sous forme deEcontraintes d'egalite et Icontraintes d'inegalites avec des fonctions dierentiablesg:Rn!REeth:Rn!RI:K=fx2 R njg1 (x) =:::gE(x) = 0;h1(x)0:::;hI(x)0g. Pour simplier les notations, on dira qu'un vecteur y2Rpest negatif si toutes ses coordonnees le sons :y0,y10;:::;yp0. Ainsi, (10) devient : min g(x)=0 h(x)0f(x) (11)

3.1 Qualication des contraintes

Lorsque le probleme d'optimisation est sous contraintes, on verra que les conditions necessaires d'optimalite ne s'appliquent qu'aux pointsx2Kou les contraintesg;hverient certaines proprietes

de regularite. Ces proprietes ditesde qualication, traduisent le fait que l'on peut entierement decrire

la geometrie locale deKenxa l'aide des jacobiennesJg(x) etJh(x). En pratique, on ne cherchera pas a exprimer ces proprietes explicitement mais on se contentera de verier des conditions susantes qui les garantissent. On enumere dans cette section ces dierentes conditions susantes en allant du plus particulier au plus general.

Proposition 7

(Contraintes anes).Sigethsont anes, alors elles sont qualiees en tout point deK. Proposition 8(Slater).Sigest ane,h1;:::;hrsont anes ethr;:::;hIconvexes, alors s'il existe x02Ktel quehj(x0)<0pour toutj2Jr;IKalorsh;gsont qualiees en tout point deK.

Proposition 9

(Independence lineaire).Soitx2K. S'il existektel quehk(x) = 0, alors quitte a reindexer les(hj)j, supposons queh1(x) =:::hk(x) = 0ethk+1(x):::hI(x)<0. Si la famille des gradientsfrg1(x);:::;rgE(x);rh1(x);:::rhr(x)gest libre, alorsh;gsont qualiees enx.

En particulier, on remarque que si l'on n'a que des contraintes d'egalite, la condition d'independence

lineaire se resume en l'independence lineaire des gradients degenx, et donc la surjectivite de la Jacobienne

degenx:

Proposition 10

(Independence lineaire - egalite).Soitx2K=fx;g(x) = 0g. Si la famille des gradients frg1(x);:::;rgE(x)gest libre, alorsgest qualiee enx.

Proposition 11

(Condition de Mangasarian-Fromovitz (MF)).Soitx2K. S'il existektel quehk(x) = 0, alors quitte a reindexer les(hj)j, supposons queh1(x) =:::hk(x) = 0ethk+1(x):::hI(x)<0. Si frg1(x);:::;rgE(x)gest libre, et s'il existev2Ktel que(8i)rgi(x)>v= 0et(8i > r)rhi(x)>v <

0, alorsh;gsont qualiees enx.

hicham.janati@inria.fr 7

Optimisation dierentiable ENSAE 2020NotonsI0(x)J1;IKl'ensemble des indices des contrainteshitel quehi(x) = 0, dites contraintes

actives enx. Comme on cherche a decrire l'ensembleKlocalement enx, par continuite deh, les contraites

inactives (hj(x)<0) ne participent pas a la description locale deKen x. On peut donc donner une formulation generale des proprietes 7 et 8 en restreignan tles conditions aux con traintesd'in egaliteactiv es. Ceci a par contre l'inconvenient de devoir traiter la qualication en un pointx2K. Pour la premiere condition de qualication, cela donne :

Contraintes anes - (actives)

Soitx2K. Sigethi8i2I0(x) sont anes, alors les contraintes sont qualiees enx.

3.2 Contraintes d'egalite

Considerons tout d'abord le cas de contraintes d'egalite uniquement. min g(x)=0f(x) (12) On rappelle quegest une fonction dierentiableRn!RE, exprimantEcontraintes d'egalite g1(x) ==gE(x) = 0. On rappelle egalement que la Jacobienne degenx2Rnest la matrice donnee par : J g(x) =@gi@x j(x) i;j =0 B

BBB@rg1(x)

rgi(x) rgE(x)1 C

CCCA(13)

On commence par donner une condition necessaire d'optimalite, veriee par tout minimum local du probleme ( 12 ) qui verie une condition de qualication.

3.2.1 KKT - condition necessaire

Proposition 12

(KKT - condition necessaire).Soitx2K. Sixest un minimum local de f tel quegest qualiee enx, alors il existe2REtel que : rf(x) +Jg(x)>= 0 g(x) = 0 ,rf(x) +PE i=1irgi(x) = 0 g(x) = 0(14)

Par la proposition

10 , la surjectivite deJg(x) est une condition susante de qualication degenx.

Avec(13), on voit que pour chercher les points ou cette condition de qualication est veriee, il sut de

chercher lesxtels que la famille des gradients (rgi(x))iest libre.

Exemple 5.On considere le probleme :

min xy+2=0x2+y2(15) hicham.janati@inria.fr 8 Optimisation dierentiable ENSAE 2020Graphiquement, on cherche un(x;y)ap- partenant a la droite d'equationy=x+2 qui minimise la normek(x;y)k2, autre- ment dit le point le plus proche de(0;0) veriant la contrainte.2.0 1.5 1.0 0.5

0.00.51.00.5

0.00.51.01.52.02.53.0

x - y + 2 = 0

Solution

On a une seule contrainteg(x) =xy+2.rg(x) = (1;1)6= 0. Une famille constituee d'un seul element

est libre si et seulement si ce dernier est non nul, doncJg(x;y)est inversible quelque soitx;y;gest donc

qualiee pour toutx;y. Cherchonsx;y2Rnet2Rtels que : rf(x;y) +rg(x;y) = 0 (16) )2x+= 0

2y= 0(17)

)x+y= 0 (18) Or la contrainte d'egalite s'ecritxy+ 2 = 0, avec(18)on obtientx=1ety= 1, et enn= 2. Conclusion 1 : si un minimum existe alors, c'est forcement(x;y) = (1;1). En revanche, la restriction defsur K est clairement coercive, donc un minimum global existe.

Conclusion,(x;y) = (1;1)est un minimiseur global.Exercice 10.Resoudre les problemes d'optimisation suivants :

1.min x2+y2=1x+y

2.minx+y=1x4+y4

3.minx+2y=1x2+y2+xy

Exercice 11.Soitp1.Etudier les probleme d'optimisation selonp: min x2p+y2p=1x2+y2 Et max x2p+y2p=1x2+y2

3.2.2 Probleme convexe - condition susante

Denition 6

(Probleme convexe).on dit que le problememing(x)=0f(x)est convexe sifest convexe etg est ane. Proposition 13(KKT - condition susante).Si le problememing(x)=0f(x)est convexe, alors : S'il existex2Rnet2REsolutions du systeme KKT(14)alorsxest un minimum global de ming(x)=0f(x). Exercice 12.SoitA2Rm;netb2Rm. On s'interesse au problememinAx=bkxk2. 1.

S'agit-il d'un pr oblemec onvexe?

2.

Ecrire les equations KKT du probleme

hicham.janati@inria.fr 9

Optimisation dierentiable ENSAE 2020

quotesdbs_dbs33.pdfusesText_39

[PDF] optimisation convexe exercices corrigés

[PDF] fonction strictement convexe

[PDF] optimisation quadratique sous contrainte linéaire

[PDF] optimisation convexe pdf

[PDF] fonction convexe plusieurs variables

[PDF] modélisation et simulation d'un moteur ? courant continu matlab

[PDF] modélisation mcc

[PDF] simulation mcc simulink

[PDF] asservissement et regulation de vitesse d'un moteur a courant continu

[PDF] modélisation d'un moteur ? courant continu

[PDF] equation differentielle moteur courant continu

[PDF] schéma bloc moteur ? courant continu

[PDF] commande pid d'un moteur ? courant continu pdf

[PDF] modélisation machine asynchrone simulink

[PDF] onduleur triphasé matlab