[PDF] L 'alphabet arabe - Centre de langues
[PDF] Supports écrits leçons 1 ? 10
[PDF] - Fiche Méthodologique : Les lettres de l 'alphabet - Les minuscules
[PDF] Méthode d 'apprentissage des caractères chinois - Decitre
[PDF] - Fiche Méthodologique : Les lettres de l 'alphabet - Les minuscules
[PDF] L 'alphabet hébraïque - Morim
[PDF] - Fiche Méthodologique : Les lettres de l 'alphabet - Les minuscules
[PDF] Cahier de vacances Maternelle 2 - Tête ? modeler
[PDF] - Fiche Méthodologique : Les lettres de l 'alphabet - Les minuscules
[PDF] L 'Alphabet Phonétique International anglais (API) [COULEUR]
[PDF] 1 TRANSCRIPTION PHONÉTIQUE DU FRANÇAIS A Transcrivez
[PDF] Fonte BV-API (Alphabet Phonétique International)
[PDF] SYMBOLES PHONÉTIQUES DES SONS DU FRANÇAIS Alphabet
[PDF] Les analphabètes et le secteur informel en Côte d 'Ivoire : le français
[PDF] L 'Alphabétisation fonctionnelle au Mali: une formation pour le
Universite Paris Diderot L3 MIASHS { Annee 2015-2016
Cours d'Optimisation
Matthieu 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. 1 2
Chapitre 1
Introduction a l'optimisation
1.1 Generalites. Exemple introductif
L'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 depend deNvariables reelles, rassemblees en un vecteurx= (x1;:::;xN)2RN, et qui four- nissent une valeurJ(x) ouJest une fonction deRNdansR. En general, les variables x
1;:::;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 ecrira les 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 variablesx02K tel que
8x2K 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 et dispose d'une semaine de revisions, ce qui represente 42 heures de travail (en comptant 6 jours et 7 heures par jour). Pouri= 1;:::;4, on notexile nombre d'heures de revisions 3 pour la matiere numeroi. L'ensembleKest alors decrit par K=( x2R4;81i4xi0;4X i=1x i42) On noteM(x) la moyenne des notes (sur 20) obtenues par l'etudiant apres avoir revisexi heures la matiere numeroi. L'objectif est de maximiserM(x), ce qui revient a minimiser la dierence 20M(x). On peut donc formuler le probleme d'optimisation suivant : inf x2K(20M(x)) Remarque 1.1.Bien s^ur, dans l'exemple precedent, on ne conna^t pas la formule deM(x) de maniere explicite! De plus, il est evident que la moyenne obtenue ne depend pas seulement du nombre d'heures de revisions, mais de beaucoup d'autres parametres (assiduite en TD, concentration lors des revisions, qualite du sommeil la veille des epreuves...). Le choix de la fonction co^ut decoule d'un choix demodelisation du phenomene etudie. Cependant, dans ce cours, les fonctions co^ut seront considerees comme des donnees du probleme. Nous allons voir que la resolution d'un probleme d'optimisation depend en grande partie des proprietes mathematiques de la fonctionJ. Pour l'illustrer, placons-nous en dimensionN= 1.
1.2 Quelques exemples en dimensionN= 1
On considere un seul parametrex2R, et une fonction co^utJ:R!R. On choisit
K=RouK= [c;d] un intervalle ferme non vide.
Exemple 1.2.Cas d'une fonctionJgenerale (continue), qui n'a pas de min ni de max surR(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 intervalle ferme borne, mais n'atteint pas cet inf. Exemple 1.4.Cas d'une fonctionJconvexe, mais pas strictement convexe (son graphe contient un segment) : existence d'un minimum mais pas unicite. Exemple 1.5.Cas d'une fonction strictement convexe, derivable : le minimum surR est atteint au pointx0qui satisfaitJ0(x0) = 0. On dit quex0est un point critique de J. 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 sera remplacee par lesderivees partiellesouderivees directionnellesdeJ.
1.3 Rappels de calcul dierentiel
On se place dansRN, muni de la norme euclidiennek ket du produit scalaire euclidienh;i. Pourx2RNetR >0, on noteBR(x) la boule ouverte de centrexet de rayonRetB
R(x) la boule fermee correspondante :
B
R(x) =y2RN;kyxk< RB
R(x) =y2RN;kyxk R
Denition 1.1.1.Un ensem bleURNestouvertsi
8x2U9R >0; B(x;R)U
2. 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 lineaire
L2 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 la directiond, au pointu, si l'applicationt2R7!J(u+td) est derivable en 0. Si c'est le cas, on note cette derivee @J@d (u) := limt!0J(u+td)J(u)t 5 Sid=eiest l'un des vecteurs de base deRN, on appelle cette derivee direction- nelle lai-emederivee partielledeJau pointu, que l'on note @J@x i(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 admet des derivees directionnelles en toute direction au pointu(et en particulier, des derivees partielles). De plus, sa dierentielle au pointus'ecrit
8h= (h1;:::;hN)2RNDJ(u)(h) =NX
i=1@J@x i(u)hi: En introduisant le gradient deJau pointu, deni par rJ(u) =@J@x
1(u):::@J@x
N(u) T on peut ecrire de maniere condensee
DJ(u)(h) =hrJ(u);hi:(1.1)
On montre que siJest dierentiable au pointu, alorsrJ(u)est l'unique vecteur de R
Nt.q. la relation(1.1)soit veriee.
Remarque 1.2(Calcul du gradient).Pour calculer le gradient deJau pointu, il n'est pas toujours necessaire de calculer explicitement toutes les derivees partielles. Une autre methode 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 dierentiable enu, et que w=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: 6
Chapitre 2
Existence de minimum,
convexite, unicite Cadre general.On considere un ouvertURNet une fonctionJ:U!R(fonction co^ut). On se donne un ensemble ferme non videKUet on s'interesse au probleme d'optimisation suivant : (P) infx2KJ(x) On noteraI= infx2KJ(x) avec la convention suivante. SoitA:=fJ(x); x2Kg;A est 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 existe x
02Kt.q.I=J(x0).
2.1 Existence de minimum
Denition 2.1(Minimum global, minimum local).Soitx02K. On dit que la fonction
Jadmet
(i) unminimum global surKau pointx0, si
8x2K; J(x0)J(x);
7 (ii) unminimum localsurKau pointx0, si
9R >0;8x2BR(x0)\K; J(x0)J(x):
Pour etablir l'existence de minimiseurs, la premiere etape consiste a approcher la borne 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 toutm2R il existe un pointx2Ktel queJ(x)< m. Pour toutn2N, en prenantm=n on en deduit l'existence d'un pointxn2Ktel queJ(xn)
0, il existey"2A t.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 aimerait montrer queJ(xn) converge versJ(x), ouxest un certain point deK; on aurait alorsJ(x) =I. En general, on n'aura pas la convergence de la suite (xn) versx, mais seulement la convergence d'une suite extraite (x'(n)), qui decoulera de proprietes de compacite. Le passage a la limite dans la suite numerique (J(x'(n))) necessitera quant a lui lacontinuitede la fonctionJau pointx. 8 Theoreme 2.1.SiKest un compact non vide deRN(i.e., un ferme borne), et siJ est 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. CommeJest continue enx, lim n!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 cette diculte en considerant des fonctionsJqui contraignent les suites minimisantes a rester dans 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), si lim x2U;kxk!1J(x) = +1: Theoreme 2.2.SoitKRNt.q.(i)Kest ferme, non vide,(ii)Jest continue en tout point deK, et(iii)Jest coercive. AlorsJadmet un minimum global surK. Preuve.
L'inmumIdeJsurKetant soit un reel, soit egal a1, on peut choisir un reel Mt.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\B R(0), qui est compact; on peut donc conclure en
reprenant le raisonnement de la preuve du theoreme 2.1. 9 2.2 Convexite et unicite du minimiseur
SoitURNun ouvert,J:U!Rune application etKUun ensemble non vide. Denition 2.4.On dit que l'ensembleKestconvexesi
82[0;1];8(x;y)2K2;(1)x+y2K:
Cela signie que si deux pointsx;ysont dansK, alors le segment [x;y], qui relie ces points, 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 que l'applicationJestconvexesurKsi 82(0;1);8(x;y)2K2; J((1)x+y)(1)J(x) +J(y)
Jeststrictement convexesurKsi
82(0;1);8(x;y)2K2; x6=y)J((1)x+y)<(1)J(x) +J(y)
Jest-convexesurK(pour un0), si
82(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 deux minimiseurs distints,xety, sur K. On notemla valeur commune du minimum : 10 m=J(x) =J(y). Soitz=12 (x+y) le milieu du segment [x;y].Ketant convexe,z2K et par la stricte convexite deJ, J(z) =J(12
x+12 y)<12 J(x) +12
J(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 a equivalence 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))2 UR, s'ecrit
y=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 a J(u)(1)J(u) +J(v) =J(u) +(J(v)J(u)), donc
J(v)J(u)1
(J(u)J(u))!0+! hrJ(u);vui: (ii))(i) : On a J(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 fait que (1)(uu) +(vu) = 0, on obtient l'inegalite de convexite. (ii))(iii) : On ecrit J(v)J(u) +hrJ(u);vui(2.4)
J(u)J(v) +hrJ(v);uvi:(2.5)
11 En 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, g 0(t)g0(0) =hrJ(ut) rJ(u); vui=1t
hrJ(ut) rJ(u); utui 0: D'autre part, commeg2C([0;1])\(]0;1[), d'apres le theoreme des accroissements nis, il existec2(0;1) tel queg(1)g(0)1 =g0(c)g0(0). Ainsig(1)g(0) +g0(0), ce qui donne l'inegalite desiree. Il existe des criteres analogues permettant de caracteriser les fonctions dierentiables strictement convexes. C'est l'objet de la proposition suivante, dont la preuve est laissee en exercice. Proposition 2.4.On suppose queJest dierentiable en tout point deK. Alors les proprietes suivantes sont equivalentes : (i)Jstrictement convexe surK.quotesdbs_dbs5.pdfusesText_9
COURSOPTIMISATION CoursenMasterM1SITN IonelSorinCIUPERCA