Next PDF List

COURS OPTIMISATIONCours en Master M1 SITNIonel Sorin CIUPERCA1Table des matières1 Introduction 42 Quelques rappels de calcul différentiel, analyse convexe et extremum 52.

1) Rappel calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1. 1) Quelques Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1. 2) Quelques rappels sur le calcul différentiel . . . . . . . . . . . . . . . 62.1. 3) Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 102.1. 4) Quelque rappels sur le matrices carrées réelles . . . . . . . . . . . . 112. 2) Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2. 1) Fonctions convexes, strictement convexes, fortement convexes . . . . 112.2.

2) Exemples des fonctions convexes, strictement convexes et fortementconvexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.

3) Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . 172. 3) Conditions nécéssaires et suffisantes de minimum . . . . . . . . . . . . . . 172.

4) Existence et unicité d"un point de minimum . . . . . . . . . . . . . . . . . 213 Optimisation sans contraintes 233.

1) Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.1. 1) Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 243.1. 2) Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 273. 2) Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.2. 1) Méthodes de gradient à pas optimal . . . . . . . . . . . . . . . . . . 293.2. 2) Autres méthodes du type gradient . . . . . . . . . . . . . . . . . . . 303. 3) La méthode des gradients conjugués . . . . . . . . . . . . . . . . . . . . . . 333.3. 1) Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.3.

2) Cas d"une fonctionJquelconque . . . . . . . . . . . . . . . . . . . 384 Optimisation avec contraintes 394.

1) Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . 404. 2) Optimisation sous contraintes d"inégalités . . . . . . . . . . . . . . . . . . . 414.2.

1) Conditions d"optimalité de premier ordre : multiplicateurs de Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.

2) Théorie générale du point selle . . . . . . . . . . . . . . . . . . . . . 4924.2. 3) Applications de la théorie du point selle à l"optimisation . . . . . . 514.2. 4) Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524. 3) Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 534.3. 1) Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 544.3. 2) Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . 544.3. 3) Méthodes de pénalisation exterieure . . . . . . . . . . . . . . . . . . 594.3.

4) Méthode d"Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613Chapitre 1IntroductionEn généraloptimisersignifie le fait de chercher une configuration optimale d"un sys-tème, c"est à dire, chercher la meilleure configuration parmi tous les configurations possiblesdu système et ceci, par rapport à un critère donné.Pour décrire (et éventuellement résoudre) un problème d"optimisation nous utilisons lamodélisation mathématique.

La démarche de modélisation comporte 3 étapes :Etape 1.Choisir lesvariables de décision, qui sont les composantes du système surlesquelles on peut agir.

On supposera dans ce cours qu"il y a un nombre finit notén2INde variables de décision, chacune de ces variables étant un nombre réel.

Alors les variablesde décision seront représentés par un vecteurx= (x1;x2;xn)T2IRn(vecteur colonne).Etape 2.Décrirel"étatdu système, étant donnée une configuration des variables dedécision.

Ceci revient mathématiquement à se donner une fonctionJ:IRn!IRquis"appellefonction objectifoufonction coûtet que nous voulons rendre la plus petitepossible ou la plus grande possible.Etape 3.Décrire lescontraintesque les variables de décision satisfont.

Ceci revient àdéfinir un ensemble de contraintesUIRnet imposer d"avoirx2U.Pour résumer on peut dire que pour décrire un problème d"optimisation on se donne1.

Une fonctionJ:IRn7!IR(fonction coût)2.

Un ensembleUIRn(ensemble des contraintes)On cherche à minimiserJsurU, c"est à dire, on cherchex2Utel queJ(x) = minx2UJ(x)ou équivalentJ(x)J(x);8x2U:Motivation et exemples pratiques :en classe4Chapitre 2Quelques rappels de calcul différentiel,analyse convexe et extremum2.

1) Rappel calcul différentiel2.1. 1) Quelques Notations1.

Pour toutn2IN;IRndésigne l"espaceeuclidienIRIRIR( "produitnfois").En général un vecteurx2IRnsera notéx= (x1;x2;xn)T(vecteur colonne).2.

On notee1;e2;enles éléments de labase canoniquedeIRn, oùeiest le vecteurdeIRndonné par :(ei)j=ij=0sij6=i1sij=i;8i;j= 1;2n(2.1)(ij=symboles deKronecker).3.

Pour tousx;y2IRnon note par< x;y >2IRleproduit scalairedexety, quiest donné par< x;y >=nXi=1xiyi:Deux vecteursx;y2IRnsontorthogonaux(on noterax?y) si< x;y >= 0.4.

Pour toutx2IRnon note parkxk 0lanorme euclidiennedex, donnée parkxk=p< x;x >=vuutnXi=1x2i:Rappellons lespropriétés d"une norme(donc aussi de la norme euclidienne) :i)kxk=jjkxk 82IR;8x2IRnii)kx+yk kxk+kyk 8x;y2IRniii)k0k= 0etkxk>0six2IRn f0g.55.

Pour tousx2IRnetr >0on notera parB(x;r)laboule ouvertedu centrexetrayonr, donnée parB(x;r) =fy2IRn;kyxk< rg:6.

Six(k)k2INest une suite dansIRnetxest un élément deIRnon dit quex(k)convergeversx(notéex(k)!x) sikx(k)xk !0.Rappellons que nous avons :x(k)!xsi et seulement six(k)i!xienIRoùx(k)i(respectivementxi) est lai-ème composante dex(k)(respectivementx).7.

SoitUIRn.- On définitl"intérieurdeUcomme l"ensemble des élémentsx2Upour lesquels ilexister >0tel queB(x;r)U.- On dit queUestouvertsi8x2U9r >0tel queB(x;r)U.- On dit queUestfermési pour tout suitefx(k)g Utel quex(k)!x2IRnonax2U.8.

Sia;b2IRnon note[a;b]le sous-ensemble deIRndonné par[a;b] =fa+t(ba)(1t)a+tb; t2[0;1]g:L"ensemble[a;b]est aussi appelléle segmentreliantaàb.Remarques :[a;b] = [b;a](Exo!)Sia;b2IRaveca < bon retrouve la notation[a;b]pour l"intervalle des nombresx2IRtels queaxb.9.

Rappellons aussi l"inégalité de Cauchy-Schwarz :j< x; y >j kxk kyk 8x;y2IRn:2.1.

2) Quelques rappels sur le calcul différentielOn considère dans cette partiemetndeux nombres deN(très souvent dans ce courson auram= 1).1.

SoitUun sous-ensemble deIRnetf:U7!IRm.On dit quefestcontinueenx2Usif(x(k))!f(x)pour toute suitex(k)Utelle quex(k)!x.On dit quefest continue surUsifest continue en tout pointx2U.Remarque :Sif= (f1;f2;fm)avecf1;f2;fm:U!IRalorsfest continuenx2Usi et seulement sif1;f2;fmsont continues enx.Pour tous les poins suivants on va supposer queest un ouvert de IRnetfest unefonctionf: !IRm.62.

Pour toutx2eth2IRnon note (quand9)@f@h(x) = limt7!01t[f(x+th)f(x)](c"est ladérivée directionnelledefenxdans la directionh).Remarques :i)@f@0(x) = 0:ii)Sif= (f1;f2;fn)T2IRnavecf1;f2;fm: !IRalors@f@h(x) =@f1@h(x);@f2@h(x);@fm@h(x)T:3.

Pour toutx2et touti2 f1;2;;ngon note (quand9)@f@xi(x) =@f@ei(x) = limt7!01t[f(x+tei)f(x)](c"est ladérivée partielledefenxpar rapport à la variablexi.)En particulier, sin= 1on notef0(x) =@f@x1(x) = limt!01t[f(x+t)f(x)] =limy!x1yx[f(y)f(x)]4.

Pour toutx2on note (quand9)Jf(x) =lamatrice Jacobiennedefenxquiest un élément deMm;n(IR)définie par(Jf(x))ij=@fi@xj(x)2IR8i= 1;m;8j= 1;n:Legradientdefenxest défini comme la transposée de la matrice Jacoblenne defenx:rf(x) = (Jf(x))T2 Mn;m(IR):Remarque importante :Dans le cas particulierm= 1(doncf: !IR) alorsen considérant tout élément deMn;1comme un vector colonne deIRn, on va dire querf(x)est le vecteur colonnerf(x) =@f@x1@f@x2;@f@xnT2IRn:Rappellons la formule :@f@h(x) =8x28h2IRn:5.

Sif: !IR(icim= 1) on dit qu"un pointx2est unpoint critiquepour lafonctionfsirf(x) = 0.76.

Pour toutx2eti;j2 f1;2;ngon note (quand9)@2f@xi@xj(x) =@@xi@f@xj(x)2IRmdérivée partielle à l"ordre 2.Notation :pouri=jon écrira@2f@2xi(x)à la place de@2f@xi@xi(x).7.

Dans le casm= 1on note pour toutx2(quand9)r2f(x) =la matrice carrée2 Mn(IR)donnée parr2f(x)ij=@2f@xi@xj(x);8i;j= 1;2;n:(r2f(x)s"appelle aussila matrice Hessiennedefenx).8.

On dit quefest de classeCpsur(on noteraf2Cp()) pourp= 1oup= 2si les dérivées partielles desfjusqu"à l"ordrepexistent et sont continues sur.

Parextension on dit quefest de classeC0sursifest continue sur.9.

On a le Théorème de Schwarz : sif2C2()alors@2f@xi@xj(x) =@2f@xj@xi(x)8x2;8i;j= 1;n(c"est à dire, la matricer2f(x)est symmétrique).10. (Lien entrer;Jfetr2) : Sif: !IRest de classeC2alorsr2f(x) =Jrf(x) =rJf(x)8x2(la matrice Hessienne defest le Jacobien du gradient defou le gradient de laJacobienne def).11. (Composition) SoientIRn; UIRmavec;Uouvertsf: !IRm; g:U!IRpavecp2INetf()U.

Considérons la fonction composéegf: !IRp.i)Sifetgsont continues alorsgfest continue.ii)Sifetgsont de classeC1alorsgfest de classeC1et on a l"égalité matricielleJgf(x) =Jg(f(x))Jf(x)8x2:Conséquences :i)Sim=p= 1alorsr(gf)(x) =g0(f(x))rf(x):i)Sin=p= 1alors(gf)0(x) = :8Proposition 2.1.Nous avonsr2f(x)h=r8x2;8h2IRn:où le premier gradient dans le membre de droite de l"égalité est considéré par rapport à lavariablex.Démonstration.On a :@@xi=@@xi nXj=1@f@xj(x)hj!=nXj=1@2f@xixj(x)hj=r2f(x)hi:Quelques exemples importants :1.

Sif:IRn!IRmest une fonctionconstantealorsrf= 0etJf= 0. On a aussiévidementr2f= 0dans le casm= 1.2.

Soitf:IRn!IRmdéfinie parf(x) =Ax8x2IRnoùA2 Mm;n(IR)est une matrice donné (c"est à dire,fest une fonctionlinéaire).Il est facile de voir qu"on aJf(x) =A8x2IRn(la matrice Jacobienne est constante).Dans la cas particulierm= 1une fonction linéaire générale peut être écrite sous laformef(x) =< a; x >8x2IRnoùa2IRnest un vecteur donné.

Il est clair alors querf=aetr2f= 0:3.

Soitf:IRn!IRdonnée parf(x) =< Ax; x >8x2IRn;oùA2 Mn(IR)est un matrice carrée, réelle, de taillen(c"est à dire,fest laformequadratiqueassociée à la matriceA).

Alors pour unp2 f1;2;ngfixé, on peutécriref(x) =nXi;j=1Aijxixj=Appx2p+nXj=1;j6=pApjxpxj+nXi=1;i6=pAipxixp+nXi;j=1;i6=p;j6=pAijxixj9ce qui nous donne@f@xp= 2Appxp+nXj=1;j6=pApjxj+nXi=1;i6=pAipxi=nXj=1Apjxj+nXi=1Aipxi= (Ax)p+(ATx)p:Nous avons donc obtenu :rf(x) = (A+AT)x;8x2IRn:En utilisant la formuler2f=Jrfon déduitr2f(x) =A+AT;8x2IRn(donc la hessienne defest constante).Remarque :En particulier, siAestsymmétrique(c"est à direA=AT) alorsr< Ax; x >= 2Ax;8x2IRn:r2< Ax; x >= 2A;8x2IRn:2.1.

3) Rappel formules de TaylorProposition 2.2.(sans preuve)SoitIRnouvert,f: 7!IR;a2eth2IRntels que[a;a+h].

Alors :1.

Sif2C1()alorsi)f(a+h) =f(a) +R10 dt(formule de Taylor à l"ordre 1 avec reste intégral).ii)f(a+h) =f(a)+avec0< <1(formule de Taylor - Maclaurin à l"ordre 1)iii)f(a+h) =f(a)++o(khk)(formule de Taylor - Young à l"ordre 1)2.

Sif2C2()alorsi)f(a+h) =f(a)++R10(1t) dt(formule de Taylor à l"ordre 2 avec reste intégral).ii)f(a+h) =f(a)++12avec0< <1(formule de Taylor - Maclaurin à l"ordre 2)iii)f(a+h) =f(a)++12+o(khk2)(formule de Taylor - Young à l"ordre 2).Remarque :Dans la proposition précédente la notationo(khkk)pourk2INsignifieune expression qui tend vers 0 plus vite quekhkk(c"est à dire, si on la divise parkhkk, lerésultat tend vers 0 quandkhktend vers 0).102.1.

4) Quelque rappels sur le matrices carrées réellesSoitn2INetA2 Mn(IR)une matrice carrée réelle.1.

SoitC=l"ensemble des nombres complexes.

On rappelle que2Cest unevaleurpropredeAs"il existex2Cnavecx6= 0tel queAx=x; on appellexvecteurpropredeAassocié à la valeur propre.2.

On dit que la matriceAestsemi-définie positivesi< Ax;x >0;8x2IRn.On dit queAestdéfinie positivesi< Ax;x > >0;8x2IRnavecx6= 0.3.

Rappellons que siAest symétrique alors toutes les valeurs propres deAsont réelles;en plus il existenvecteurs propres deAappartenant àIRnformant une base ortho-normée enIRn.4.

Supposons que la matriceAest symétrique.

Alors< Ah; h >minkhk2;8h2IRnoùmin2IRest la plus petite valeur propre deA.Rémarquons que l"inégalité précédente devient égalité sihest un vecteur propreassocié à la valeur propremin.5.

Supposons queAest symétrique.

AlorsAest semi-définie positive si et seulement simin0etAest définie positive si et seulement simin>0.6.Abréviation :La notation SDP pour une matrice carrée rélle signifie "matrice sy-métrique et définie positive" (elle ne signifie pas "matrice semi-définie positive" !)..2.

2) Convexité2.2.

1) Fonctions convexes, strictement convexes, fortement convexesDéfinition 2.3.Un ensembleUIRnest ditconvexesi8x;y2Uon a[x;y]U(quelque soit deux points dansU, tout le segment qui les unit est dansU).Définition 2.4.SoitUIRnun ensemble convexe etf:U!IRune fonction.1.

On dit quefestconvexesurUsif(ty+ (1t)x)tf(y) + (1t)f(x);8x;y2U;8t2[0;1]2. On dit quefeststrictement convexesurUsif(ty+ (1t)x)< tf(y) + (1t)f(x);8x;y2Uavecx6=y;8t2]0;1[:3.

On dit quefestfortement convexesurUs"il existe >0tel quef(ty+ (1t)x)tf(y) + (1t)f(x)t(1t)kyxk2;8x;y2U;8t2[0;1]114.

On dit quefestconcave(respectivementstrictement concave, respectivementfortement concave) sifest convexe (respectivement strictement convexe, res-pectivement fortement convexe).Remarque :Il est facile de voir qu"on a : fortement convexe=)strictement convexe=)convexe.

Les réciproques ne sont pas vraies en général; par exemple une applicationaffinef(x) =Ax+best convexe (et aussi concave) mais elle n"est pas strictement convexe(ni strictement concave) donc elle n"est pas fortement convexe (ni fortement concave).On a le résultat utile suivant :Proposition 2.5.SoitUIRnun ensemble convexe,p2IN,f1;f2;;fp:U!IR desfonctions convexes et1;2;;ndes constantes strictement positives.Posonsf=1f1+2f2+pfp.

Alors on a :1.

La fonctionfest convexe (donc toute combinaison linéaire avec des coefficients stric-tement positifs de fonctions convexes est convexe).2.

Si au moins l"une des fonctionsf1;;fpest strictement convexe alorsfest stric-tement convexe.3.

Si au moins l"une des fonctionsf1;;fpest fortement convexe alorsfest fortementconvexe.Démonstration.Laissée en exercice!Il est en général difficile de vérifier la convexité d"une fonction en utilisant uniquementla définition (essayez avecf(x) =x2ou avecf(x) =x4!) Les propositions suivantesdonnent des critères de convexité, convexité stricte et convexité forte, plus faciles à utiliserque les définitions respectives.Proposition 2.6.(caractérisation de la convexité)SoitIRnouvert,UavecUconvexe etf: 7!IR une fonction de classeC1.Alorsa)Les 3 propositions suivantes sont équivalentes :1.fest convexe surU2.f(y)f(x)+;8x;y2U3.rfestmonotone surU, c"est à dire08x;y2U:b)Si de plusfest de classeC2suralorsfest convexe surUsi et seulement si0;8x;y2U(2.2)12Démonstration.a)On montre ici l"équivalence entre 1), 2) et 3).1) =)2) :Supposonsfconvexe; la définition de la convexité peut s"écriref(x+t(yx))f(x)t[f(y)f(x)]En fixantx;yen divisant partet en faisantttendre vers 0 (ce qui est possible cart2[0;1])on obtient 2).2) =)3) :De 2) on déduitf(y)f(x)+;8x;y2Uet aussi (en inversantxety) :f(x)f(y)+;8x;y2UEn faisant la somme de ces 2 inégalités on obtient 3).3) =)1) :Soientx;y2Ufixés.

On introduit la fonctiong:I!IRdéfinie part2I!g(t) =f(ty+ (1t)x)2IRoùIest un intervalle ouvert qui contient[0;1].

Il est facile de voir quegest de classeC1et on ag0(t) =8t2I:Soientt1;t22[0;1]avect1< t2.

Alorsg0(t2)g0(t1) ==1t2t1:Par hypothèse 3) le dernier term de l"égalité précédente est0, ce qui montre que lafonctiong0est une fonction croissante.

On déduit alors quegest une fonction convexe sur[0;1], ce qui nous donne pour toutt2[0;1] :g(t1 + (1t)0)tg(1) + (1t)g(0)c"est à diref(ty+ (1t)x)tf(y) + (1t)f(x)doncfest convexe.b)On suppose icif2C2()."=)" Supposons quefest convexe et montrons (2.2).

Soith2IRnfixé et notonsg: 7!IRla fonction donnée parg(x) =;8x2.

Nous avons en utilisantaussi la Proposition 2.1 :==@g@h(x) = limt7!0t13ce qui nous donne= limt7!0t2:Considérons maintenantx;y2Uarbitraires eth=yx.

Commex+t(yx)2U8t2[0;1], de l"égalité précédente on déduit à l"aide de la monotonie derfque0, c"est à dire (2.2)."(=" Supposons maintenant que (2.2) est satisfaite et montrons quefest convexe.

Soientx;y2Ufixées arbitraires, et considérons la fonctiong1: 7!IRdonnée parg1(z) =8z2.

Alors=g1(x)g1(y) =avec2]0;1[(on a utilisé l"une des formules de Taylor).D"autre part, nous avonsrg1(z) =r2f(z)(xy)et ceci nous permet de déduire, en utilisant aussi (2.2) :=0:Ceci nous donne la monotonie derfdonc la convexité def.Proposition 2.7.(caractérisation de la convexité stricte)SoitIRnouvert,UavecUconvexe etf: 7!IR une fonction de classeC1.Alorsa)Les 3 propositions suivantes sont équivalentes :1.fest strictement convexe surU2.f(y)> f(x)+;8x;y2Uavecx6=y3.rfeststrictement monotone surU, c"est à dire >08x;y2Uavecx6=y:b)Si de plusfest de classeC2suralors si >0;8x;y2Uavecx6=y(2.3)alorsfest strictement convexe surU.Proposition 2.8.(caractérisation de la convexité forte)SoitIRnouvert,UavecUconvexe etf: 7!IR une fonction de classeC1.Alorsa)Les 3 propositions suivantes sont équivalentes :141.fest fortement convexe surU2.

Il existe >0tel quef(y)f(x)++kyxk2;8x;y2U3.

Il existe >0tel quekyxk2;8x;y2U:b)Si de plusfest de classeC2suralorsfest fortement convexe surUsi et seulementsi il existe >0tel quekyxk2;8x;y2U(2.4)Les démonstrations des Propositions 2.7 et 2.8 sont admises. (certains points sont dessimples adaptations des preuves des points analogues de la Proposition 2.6.Remarques :1.

Dans la Proposition 2.7b)il n"y a pas d"équivalence entre la stricte convexité defet l"inégalité (2.3) de cette proposition dans le casf2C2(par exemple la fonctionf:IR!IRdonnée parf(x) =x4est strictement convexe, mais l"inégalité n"est passatisfaite six= 0).2.

Dans le cas particulier où l"ensembleUest ouvert alors pour les 3 propositionsprécédentes les inégalités (2.2), (2.3) et (2.4) concernant la matrice Hessienner2fs"écrivent respectivement :08x2U;8h2IRn( pour la Proposition 2.6); >08x2U;8h2IRn(pour la Proposition 2.7);khk2;8x2U;8h2IRn(pour la Proposition 2.8):Pour voir ceci il suffit de remarquer que d"u