[PDF] Cours-Optimisation.pdf Cours d'Optimisation Dans ce

View - Download Cours-Optimisation.pdf

Previous PDF

Next PDF

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. (ii)8(u;v)2K2,u6=v)J(v)> J(u) +hrJ(u); vui. (iii)8(u;v)2K2,u6=v) hrJ(v) rJ(u); vui>0. Exercice 2.2.On supposeJdierentiable en tout point deK. Soit0. Montrer les equivalences suivantes : Jest-convexe surK() 8(u;v)2K2; J(v)J(u) +hrJ(u);vui+2 kvuk2 () 8(u;v)2K2;hrJ(v) rJ(u);vui kvuk2 Il existe aussi quelques criteres de convexite portant sur la dierentielle seconde de J. Theoreme 2.3.On suppose queK=RN. SoitJ:RN!R, deux fois dierentiable surRN. Alors

Jest convexe surRN()

8u2RN;8h2RN;hD2J(u)h;hi 0

Preuve.Voir le TD.

Attention, l'enonce de l'implication ()) doit ^etre adapte si on veut etudier la convexite sur un sous-ensembleKdeRN. 12 Exercice 2.3.On supposeJdeux fois dierentiable en tout point deKRN. Soit

0. Montrer que

8u2K;8h2RN;hD2J(u)h;hi khk2

=)Jest-convexe surK, et que l'equivalence est vraie pourK=RN. Exemple 2.3.x2RN7! kxk2est= 2 convexe. En eet, sa matrice hessienne en toutxest 2 fois la matrice identite. Exercice 2.4.On supposeJdeux fois dierentiable en tout point deK. Montrer que

8u2K;8h2RN;hD2J(u)h;hi>0

=)Jest strictement convexe surK. Montrer que la reciproque est fausse (exemple :J(x) =x4).

Premieres applications.

Proposition 2.5.SoitKun convexe ferme non vide deRN, contenu dans un ouvert U. SoitJ:U!R, dierentiable en tout point deK. On suppose queJest-convexe surK, avec >0. AlorsJpossede un unique minimiseur surK. Idee de la preuve: Soituxe dansK. DeJ -convexe on deduit que pour tout v2K,

J(v)J(u) +hrJ(u);vui+2

kvuk2

J(u) krJ(u)kkvuk+2

kvuk2kvk!1!+1: DoncJest coercive, et admet un minimum surKd'apres le theoreme 2.2. L'unicite du minimiseur provient de la stricte convexite deJsurK. Theoreme 2.4(projection sur un convexe ferme non vide).SoitKun convexe ferme non vide deRN. Alors

8u2RN;9!u2K;kuuk= minv2Kkvuk

On noterau= K(u)la projection deusurK.

13quotesdbs_dbs32.pdfusesText_38

[PDF] optimisation mathematiques pdf exercices

[PDF] cours optimisation master

[PDF] exercices corrigés de convexité et optimisation

[PDF] exercices corrigés doptimisation pdf

[PDF] cours doptimisation pour économistes

[PDF] cours optimisation sans contrainte

[PDF] resume cours optique geometrique

[PDF] cours de physique optique cours et exercices corrigés pdf

[PDF] examen corrigé optique ondulatoire

[PDF] résumé cours optique ondulatoire

[PDF] physique optique cours complet

[PDF] controle optique 1ere s

[PDF] orientation scolaire et professionnelle définition

[PDF] oxydoréduction cours bac pro

[PDF] programme daeu b physique