Universite Paris Diderot L3 MIASHS { Annee 2015-2016Cours d'OptimisationMatthieu Bonnivard (d'apres le polycopie d'Olivier Bokanowski)References bibliographiques :|Philipp eG.
Ciarlet, Introduction a l'analyse numerique matricielle et a l'optimi-sation.|Jean-Baptiste Hiriart-Urrut y,Optimisation et analyse convexe (exercices cor-riges).|Gr egoireAllaire, Analyse numerique et optimisation, chap. 9 et 10.12Chapitre 1Introduction a l'optimisation1.
1) Generalites.
Exemple introductifL'optimisation consiste en la recherche du minimum (ou du maximum) d'une cer-taine quantite, appelee co^ut ou objectif.
Dans ce cours, on supposera que le co^ut dependdeNvariables reelles, rassemblees en un vecteurx= (x1;:::;xN)2RN, et qui four-nissent une valeurJ(x) ouJest une fonction deRNdansR.
En general, les variablesx1;:::;xNne seront pas autorisees a prendre n'importe quelle valeur, mais devront sa-tisfaire des contraintes que l'on representera par un sous ensembleKRN.
On ecrirales problemes d'optimisation sous la forme generale suivante :(P) infx2KJ(x):On dit que probleme (P) admet une solution s'il existe un choix de variablesx02Ktel que8x2K J(x0)J(x):On dit alors quex0est un minimiseur (ou point de minimum) deJsurK, et queJ(x0)est un minimum deJsurK.Exemple 1.1.Un etudiant doit reviser pour ses examens.
Il a 4 matieres a passer etdispose d'une semaine de revisions, ce qui represente 42 heures de travail (en comptant 6jours et 7 heures par jour).
Pouri= 1;:::;4, on notexile nombre d'heures de revisions3pour la matiere numeroi.
L'ensembleKest alors decrit parK=(x2R4;81i4xi0;4Xi=1xi42)On noteM(x) la moyenne des notes (sur 20) obtenues par l'etudiant apres avoir revisexiheures la matiere numeroi.
L'objectif est de maximiserM(x), ce qui revient a minimiserla dierence 20M(x).
On peut donc formuler le probleme d'optimisation suivant :infx2K(20M(x))Remarque 1.1.Bien s^ur, dans l'exemple precedent, on ne conna^t pas la formuledeM(x) de maniere explicite! De plus, il est evident que la moyenne obtenue nedepend pas seulement du nombre d'heures de revisions, mais de beaucoup d'autresparametres (assiduite en TD, concentration lors des revisions, qualite du sommeil laveille des epreuves ).
Le choix de la fonction co^ut decoule d'un choix demodelisationdu phenomene etudie.
Cependant, dans ce cours, les fonctions co^ut seront considereescomme des donnees du probleme.Nous allons voir que la resolution d'un probleme d'optimisation depend en grandepartie des proprietes mathematiques de la fonctionJ.
Pour l'illustrer, placons-nous endimensionN= 1.1. 2) Quelques exemples en dimensionN= 1On considere un seul parametrex2R, et une fonction co^utJ:R!R.
On choisitK=RouK= [c;d] un intervalle ferme non vide.Exemple 1.2.Cas d'une fonctionJgenerale (continue), qui n'a pas de min ni de maxsurR(par exemple, ane), mais un min et un max sur tout intervalle ferme borne.Exemple 1.3.Cas d'une fonction discontinue, qui possede un inf sur un intervalleferme borne, mais n'atteint pas cet inf.Exemple 1.4.Cas d'une fonctionJconvexe, mais pas strictement convexe (son graphecontient un segment) : existence d'un minimum mais pas unicite.Exemple 1.5.Cas d'une fonction strictement convexe, derivable : le minimum surRest atteint au pointx0qui satisfaitJ0(x0) = 0.
On dit quex0est un point critique deJ.
4) Bilan.Face au probleme (P),|l'existence d'un minim umest li ee ala continuitedeJ,|l'unicit edu m inimiseurx0est liee a laconvexite(stricte) deJ,|l' equationsatisfaite par x0est associee a laderiveedeJ.Toutes ces proprietes joueront des r^oles analogues en dimensionN; la derivee seraremplacee par lesderivees partiellesouderivees directionnellesdeJ.1.
3) Rappels de calcul dierentielOn se place dansRN, muni de la norme euclidiennek ket du produit scalaireeuclidienh;i.
Pourx2RNetR >0, on noteBR(x) la boule ouverte de centrexetde rayonRetBR(x) la boule fermee correspondante :BR(x) =y2RN;kyxk< RBR(x) =y2RN;kyxk RDenition 1.1.1.Un ensem bleURNestouvertsi8x2U9R >0; B(x;R)U2.Un ensem bleFRNestfermesi son complementaireRNnFest ouvert.Denition 1.2.SoitURNun ouvert etJ:U!Rune application.
Soitu2U.1.On dit que Jestdifferentiableau pointus'il existe une application lineaireL2 L(RN;R) t.q. pour touth2RNt.q.u+h2U,J(u+h) =J(u) +L(h) +o(khk):La notationo(khk) signie qu'il existe une fonction":RN!Rt.q. limh!0"(h) =0, et qui permette d'ecrire le reste sous la formeo(khk) =khk"(h).SiLexiste, elle est unique; on la noteL=DJ(u).2.Soit d2RNn f0g.
On dit queJadmet unederivee directionnelledans ladirectiond, au pointu, si l'applicationt2R7!J(u+td) est derivable en 0.
Sic'est le cas, on note cette derivee@J@d(u) := limt!0J(u+td)J(u)t:5Sid=eiest l'un des vecteurs de base deRN, on appelle cette derivee direction-nelle lai-emederivee partielledeJau pointu, que l'on note@J@xi(u) := limt!0J(u+tei)J(u)t= limt!0J(u1;:::;ui1;ui+t;ui+1;:::;uN)J(u1;:::;uN)t:Proposition 1.1.SiJ:U!Rest dierentiable au pointu2U, alors elle admetdes derivees directionnelles en toute direction au pointu(et en particulier, des deriveespartielles).
De plus, sa dierentielle au pointus'ecrit8h= (h1;:::;hN)2RNDJ(u)(h) =NXi=1@J@xi(u)hi:En introduisant le gradient deJau pointu, deni parrJ(u) =@J@x1(u):::@J@xN(u)T;on peut ecrire de maniere condenseeDJ(u)(h) =hrJ(u);hi:(1.1)On montre que siJest dierentiable au pointu, alorsrJ(u)est l'unique vecteur deRNt.q. la relation(1.1)soit veriee.Remarque 1.2(Calcul du gradient).Pour calculer le gradient deJau pointu, il n'estpas toujours necessaire de calculer explicitement toutes les derivees partielles.
Une autremethode consiste a etablir un developpement limite deJsous la forme suivante :J(u+h) =J(u) +hw;hi+o(khk)ouw2RNest un certain vecteur xe.
Alors, on peut armer queJest dierentiableenu, et quew=rJ(u):Exercice 1.1.Montrer que siJest dierentiable enu, alors pour toutd2RNn f0g,sa derivee directionnelle dans la directionds'ecrit@J@d(u) =hrJ(u);di:6Chapitre 2Existence de minimum,convexite, uniciteCadre general.On considere un ouvertURNet une fonctionJ:U!R(fonctionco^ut).
On se donne un ensemble ferme non videKUet on s'interesse au problemed'optimisation suivant :(P) infx2KJ(x)On noteraI= infx2KJ(x) avec la convention suivante.
SoitA:=fJ(x); x2Kg;Aest une partie deR, non vide carKest non vide.
On distingue deux cas de gure :(i)si An'est pas minoree, on poseI=1;(ii)si Aest minoree, elle possede une borne inferieure et on poseI= infA2R.La premiere question que l'on se pose est de savoir siIest atteint, c'est-a-dire s'il existex02Kt.q.I=J(x0).2.
1) Existence de minimumDenition 2.1(Minimum global, minimum local).Soitx02K.
On dit que la fonctionJadmet(i) unminimum global surKau pointx0, si8x2K; J(x0)J(x);7(ii) unminimum localsurKau pointx0, si9R >0;8x2BR(x0)\K; J(x0)J(x):Pour etablir l'existence de minimiseurs, la premiere etape consiste a approcher laborne inferieureIa l'aide d'une suite de pointsxn2K, qu'on appelle suite minimisante.Denition 2.2.On appellesuite minimisantepour le probleme (P) toute suite(xn)n2Na valeurs dansRNt.q.8n2N; xn2Ket limn!1J(xn) =I:Proposition 2.1.Pour tout probleme(P), il existe au moins une suite minimisante.Preuve.On introduit l'ensembleA:=fJ(x); x2Kg.
Distinguons deux cas de gure :(i)Si An'est pas minoree, alors par convention,I=1. De plus, pour toutm2Ril existe un pointx2Ktel queJ(x)< m. Pour toutn2N, en prenantm=non en deduit l'existence d'un pointxn2Ktel queJ(xn)
En passant a lalimite dans l'inegalite on obtient limn!1J(xn) =1, donc (xn) est une suiteminimisante.(ii)Si Aest minoree, alors elle possede une borne inferieureI(comme une partienon vide et minoree deR). Alors par denition, pour tout" >0, il existey"2At.q.Iy"< I+"et par denition deA, il existe unx"2Kt.q.y"=J(x").Ainsi pour tout" >0, il existex"2Kt.q.IJ(x")< I+":On l'applique en remplacant"par1n: pour toutn2N, il existexn2Kt.q.IJ(xn)< I+1n:En passant a la limite quandn! 1, on obtient que limn!1J(xn) =I.Pour conclure a l'existence d'un minimum global pour le probleme (P), on aimeraitmontrer queJ(xn) converge versJ(x), ouxest un certain point deK; on auraitalorsJ(x) =I.
En general, on n'aura pas la convergence de la suite (xn) versx, maisseulement la convergence d'une suite extraite (x'(n)), qui decoulera de proprietes decompacite.
Le passage a la limite dans la suite numerique (J(x'(n))) necessitera quanta lui lacontinuitede la fonctionJau pointx.
8) Theoreme 2.1.SiKest un compact non vide deRN(i.e., un ferme borne), et siJest continue en tout point deK, alorsJadmet un minimum surK.Preuve.Soit (xn)n2Nune suite minimisante. (xn) est a valeurs dansK, qui est compact,donc il existex2Ket une suite extraite (x'(n)) t.q. limn!1x'(n)=x.
CommeJestcontinue enx,limn!1J(x'(n)) =J(x):La suite (J(x'(n))) etant une suite extraite de (J(xn)), elle converge vers la m^eme limite,d'ouI=J(x).Lorsque l'ensemble des contraintesKn'est pas compact, on pourra pallier cettediculte en considerant des fonctionsJqui contraignent les suites minimisantes a resterdans un ensemble compact deRN.
On introduit pour cela la notion de fonction coercive.Denition 2.3.On supposeUnon borne. On dit queJestcoercive(ou encore,innie a l'inni), silimx2U;kxk!1J(x) = +1:Theoreme 2.2.SoitKRNt.q.(i)Kest ferme, non vide,(ii)Jest continue entout point deK, et(iii)Jest coercive.
AlorsJadmet un minimum global surK.Preuve.L'inmumIdeJsurKetant soit un reel, soit egal a1, on peut choisir un reelMt.q.M > I.
Par denition de la coercivite, il existe alorsR >0 t.q.8x2U;kxk> R)J(x)M > I:(2.1)Soit (xn)n2Nune suite minimisante.
Par denition, limn!1J(xn) =I; commeM > I,il existe donc un entierNt.q.8n2N; nN)J(xn)< M:D'apres (2.1), on en deduit que pournN,kxnk R.
Ainsi, la suite minimisante(xn)nNest a valeurs dansK\BR(0), qui est compact; on peut donc conclure enreprenant le raisonnement de la preuve du theoreme 2.1.92.
2) Convexite et unicite du minimiseurSoitURNun ouvert,J:U!Rune application etKUun ensemble nonvide.Denition 2.4.On dit que l'ensembleKestconvexesi82[0;1];8(x;y)2K2;(1)x+y2K:Cela signie que si deux pointsx;ysont dansK, alors le segment [x;y], qui relie cespoints, est contenu dansK.Exemple 2.1.Les sous-ensembles convexes deRsont les intervalles.Exercice 2.1.SoitN:RN!R+une norme quelconque.
Montrer que la boule unite(fermee) pour cette norme est necessairement convexe.Denition 2.5.On suppose queKest convexe.
On dit quel'applicationJestconvexesurKsi82(0;1);8(x;y)2K2; J((1)x+y)(1)J(x) +J(y)Jeststrictement convexesurKsi82(0;1);8(x;y)2K2; x6=y)J((1)x+y)<(1)J(x) +J(y)Jest-convexesurK(pour un0), si82(0;1);8(x;y)2K2; J((1)x+y)+2(1)kxyk2(1)J(x)+J(y)En particulier siJest-convexe avec >0, elle est strictement convexe.Exemple 2.2.x2RN7! kxkest convexe mais pas strictement convexe.Proposition 2.2.SiJest strictement convexe surK, alorsJadmet au plus un mini-miseur surK.Preuve.Par l'absurde : supposons queJ, strictement convexe surK, possede deuxminimiseurs distints,xety, sur K.
On notemla valeur commune du minimum :10m=J(x) =J(y). Soitz=12(x+y) le milieu du segment [x;y].Ketant convexe,z2Ket par la stricte convexite deJ,J(z) =J(12x+12y)<12J(x) +12J(y) =m:Cela contredit la denition du minimum deJsurK.Criteres de convexite pour des fonctions dierentiables.Proposition 2.3.On suppose queJest dierentiable en tout point deK.
On aequivalence entre :(i)Jconvexe surK.(ii)8(u;v)2K2,J(v)J(u) +hrJ(u); vui.(iii)8(u;v)2K2,hrJ(v) rJ(u); vui 0.Remarque 2.1.L'equation de l'hyperplan tangent au graphe deJ, au point (u;J(u))2UR, s'ecrity=J(u) +hrJ(u); xui;pourx2RN; y2R:La relation (ii) signie geometriquement que le graphe deJest au-dessus de son hy-perplan tangent en tout point.Preuve.(i))(ii) : Notonsu:= (1)u+v=u+(vu).
Pour2]0;1], on aJ(u)(1)J(u) +J(v) =J(u) +(J(v)J(u)), doncJ(v)J(u)1(J(u)J(u))!0+! hrJ(u);vui:(ii))(i) : On aJ(u)J(u) +hrJ(u);uui(2.2)J(v)J(u) +hrJ(u);vui:(2.3)En sommant (1) fois la relation (2.2) etfois la relation (2.3), et en utilisant le faitque (1)(uu) +(vu) = 0, on obtient l'inegalite de convexite.(ii))(iii) : On ecritJ(v)J(u) +hrJ(u);vui(2.4)J(u)J(v) +hrJ(v);uvi:(2.5)11En sommant on obtient l'inegalite desiree.(iii))(ii) : Soitg(t) :=J(u+t(vu)) pourt2[0;1].
On remarque queg0(t) =hrJ(ut); vui, et en particulier queg0(0) =hrJ(u); vui. Ainsi, par hypothese,g0(t)g0(0) =hrJ(ut) rJ(u); vui=1thrJ(ut) rJ(u); utui 0:D'autre part, commeg2C([0;1])\(]0;1[), d'apres le theoreme des accroissementsnis, il existec2(0;1) tel queg(1)g(0)1=g0(c)g0(0).
Ainsig(1)g(0) +g0(0), cequi donne l'inegalite desiree.Il existe des criteres analogues permettant de caracteriser les fonctions dierentiablesstrictement convexes.
C'est l'objet de la
