[PDF] [PDF] Cours doptimisation Nous avons vu dans le

View - Download [PDF] Cours doptimisation

Previous PDF

Next PDF

L1 Eco - Analyse 2

Cours d'optimisation

T. DUMONT, C. L

EONARD, X. MARY, H. MOHAMED

Contents

1 Semaine 1 : Geometrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1 Points et vecteurs deR2. . . . . . . . . . . . . . . . . . . . . . . . . . . .2

1.1.1 Premiere denition . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1.2 Operations sur les points et les vecteurs . . . . . . . . . . . . . . .

2

1.2 Vecteurs : Norme et Produit scalaire . . . . . . . . . . . . . . . . . . . . .

2

1.2.1 La norme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.2 Le produit scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3 Domaines deR2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

2 Semaine 2 : Fonctions de 2 variables relles . . . . . . . . . . . . . . . . . . . . .

4

2.1 Fonctions 2 variables relles . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.2 Derivees partielles et vecteur gradient . . . . . . . . . . . . . . . . . . . .

4

2.3 Derivees partielles du second ordre . . . . . . . . . . . . . . . . . . . . . .

6

3 Semaine 3 : Developpement de Taylor . . . . . . . . . . . . . . . . . . . . . . .

6

4 Semaine 4 : Optimisation de fonctions d'une variable reelle . . . . . . . . . . .

10

4.1 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

4.2 Application a l'optimisation sous contrainte d'une fonction de deux vari-

able : Methode de substitution . . . . . . . . . . . . . . . . . . . . . . . . 12

4.3 Convexite et caractrisation des extremums . . . . . . . . . . . . . . . . . .

13

5 Semaine 5 : Optimisation libre des fonctions de deux variables . . . . . . . . .

14

5.1 Condition du premier ordre . . . . . . . . . . . . . . . . . . . . . . . . . .

14

5.2 Conditions du second ordre et convexite . . . . . . . . . . . . . . . . . . .

15

6 Semaine 6 : Optimisation sous contrainte d'egalite : la methode du Lagrangien

20

6.1 Condition necessaire du premier ordre . . . . . . . . . . . . . . . . . . . .

20

6.2 Caracterisation faible des extremums locaux sous contrainte - Condition

susante du second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.3 Extremums globaux sous contrainte d'egalite . . . . . . . . . . . . . . . .

24

6.4 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

7 Semaine 7 : Methode du Lagrangien : La bonne condition susante du second

ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Universite Paris Ouest - Nanterre - La Defense

1 2

1. Semaine 1 : Geometrie

1.1. Points et vecteurs deR2

1.1.1. Premiere denition

R

2=f(x;y)jx2Ry2Rg

ExempleP= (2;3) est un point deR2.

l'ensemble de pointsR2est un espace ane avec comme origineO= (0;0).

ExempleP= (2;3) est un point deR2.

Pour chaque paire de points (P;Q) deR2, (P= (xP;yP)Q= (xQ;yQ)) on peut denir le vecteur!PQ= (xQxP;yQyP) (exemple)

SiQ=P,PPest le vecteur nul~0 = (0;0).

Attention : points et vecteurs sont denis par des coordonnees (x;y) cependant, durant ce cours nous ferons la distinction entre les deux! (exemples graphiques)

1.1.2. Operations sur les points et les vecteurs

- Combinaison lineaire de vecteurs. Soientn2N,~u1= (x1;y1);:::;~un= (xn;yn) des vecteurs deR2et1;:::;ndes scalaires (i2R). Alors1~u1+2~u2+:::+n~un est un vecteur deR2de coordonnees (1x1+:::+nxn;1y1+:::+nyn). Exemples. - Addition d'un point et d'un vecteur. SiP= (xP;yP) et~u= (x~u;y~u),Q=P+~u est un POINT deR2de coordonnees (xP+x~u;yP+y~u). Exemples. - Addition de POINTS ensemble possible mais on s'interdira de le faire.

1.2. Vecteurs : Norme et Produit scalaire

1.2.1. La norme

- Theoreme de Pythagore (+demonstration). - Denition : Norme (longueur) d'un vecteur.

Propriete 1.1.Soient~u;~vvecteurs deR2et2R

1.~u=~0si et seulement sijj~ujj= 0.

2.jj~ujj=jj jj~ujj.

3. In egalitet riangulaire.jj~u+~vjj jjujj+jjvjj(sans preuve) - Denition : vecteurs colineaires. Soient~u;~vvecteurs deR2avec~v6=~0.~uet~vsont colineaires s'il existe2Rtel que~u=~v. (Remarque:~upeut ^etre le vecteur nul.)

Propriete 1.2.Soient~u;~vvecteurs deR2et2R

Mathematiques 2 : Optimisation3

1.

L eve cteurnul est c olineaire atout ve cteur.

2. Si ~u=~vavec0,~uet~vsont colineaires dans le m^eme sens et (cas degalite de l'inegalite triangulaire)jj~u+~vjj=jj~ujj+jj~vjj 3. Si ~u=~vavec0,~uet~vsont colineaires de sens oppose etjj~u+~vjj= j jj~ujj jj~vjj j.

1.2.2. Le produit scalaire

- DansRle produit scalaire de deux reelsuetvest le produit classiqueuv. Il apparait dans l'identite remarquable: (u+v)2=u2+v2+ 2uv - De la m^eme maniere on cherche a denir un produit scalaire dansR2a partir de l'identitejj~u+~vjj2=jj~ujj2+jj~vjj2+2~u~v. Comment denir le produit~u~vpour qu'une telle identite s'applique? Denition 1.1.Soient~u;~vvecteurs deR2(~u= (x~u;y~u)et~v= (x~v;y~v)). On deni le produit scalaire~u~vpar ~u~v=x~ux~v+y~uy~v:

Propriete 1.3.Soient~u;~v; ~wvecteurs deR2et;2R

1.jj~ujj2=~u~u

2. (sym etrie)~u~v=~v~u 3. (bilin eairite)~u(~v+~w) =~u~v+~u~w Proposition 1.2(Orthogonalite et reciproque de Pythagore).Soient~u;~vvecteurs de R 2 ~u?~v,~u~v= 0

De plus

jj~u+~vjj2=jj~ujj2+jj~vjj2,~u~v= 0 - Application : equation de la tangente pour les graphs de fonctions d'une variable.

1.3. Domaines deR2

- Domaines denis par une equation - Cas particulier graphe d'une fonction - Les cercles. (exemples) - Domaines denis par une inequation (exemples) - Domaines denis comme intersection ou reunion d'autres domaines. - Complementaire d'un domaine. 4

2. Semaine 2 : Fonctions de 2 variables relles

2.1. Fonctions 2 variables relles

- Fonction reelle de deux variables reellesf: (x;y)7!f(x;y)2R. - Domaine de denitionDf=(x;y)2R2jf(x;y) "est bien deni". - Exemples : Don- ner et representer les domaines de denition (Df) des fonctions suivantes f(x;y) =xy f(x;y) = ln(x+y) f(x;y) = ln(xy) - Representation 3D (cf. pdf) - Courbes de niveau : La courbe de niveaud'une fonctionfest deni par l'ensemble des points (x;y) appartenant a l'ensemble de denition def(Df) veriantf(x;y) =.

On la noteC.

C =f(x;y)2 Dfjf(x;y) =g: Exemples : Dessiner les courbes de niveauCpour les fonctions et niveaux suivants : f(x;y) =yx

2, niveaux=1 et= 2

f(x;y) =xy, niveau= 0 et= 1 f(x;y) =xln(xy), niveau= 0 et= 1 - Ensembles de niveaux : exemples - Continuite d'une fonction de deux variables : Denition 2.1.Soitfune fonction denie surDfet(x0;y0)2 Df. fest continue en(x0;y0)si lim (x;y)!(x0;y0)jf(x;y)f(x0;y0)j= 0 c'est a dire, si quelque soit >0aussi petit qu'on veut, il existe un rayonr >0 tel que : si un point(x;y)deDfest dans le disque de rayonret de centre(x0;y0) alorsf(x0;y0) < f(x;y)< f(x0;y0) +. fest continue sur un domaineD Dfsifcontinue en tout point deD.

2.2. Derivees partielles et vecteur gradient

Fonctions partielles :

Denition 2.2.Soitfune fonction de deux variables denie sur un domaine D fR2. Soit(x0;y0)un point deDf. On peut denir deux fonctions d'une vari- able, appeles fonctions partielles obtenues en "xant" l'une des deux variables:

Mathematiques 2 : Optimisation5

f x:x7!f(x;y0) f y:y7!f(x0;y) f xetfysont donc des fonctions d'UNE variable denies respectivement surDx= fx2Rj(x;y0)2 DfgetDy=fy2Rj(x0;y)2 Dfg.

Exemples : donner les fonctions partielles :

{f(x;y) =xy3en (x0;y0) = (2;3) {f(x;y) =p1x2y2en (x0;y0) = (1=2;1)

Derivees partielles

Denition 2.3.

{ La derivee partielle de la fonctionfpar rapport axen (x0;y0)est la derivee de la fonction partielle : x7!f(x;y0);enx0:

Elle est notee

@@x f(x0;y0)ou@f@x (x0;y0)(comprendre "Derivee defpar rapport axen(x0;y0)"). @@x f(x0;y0)existe si la fonction partielle x7!f(x;y0) est derivable enx0. {La derivee partielle de la fonctionfpar rapport ayen(x0;y0)est la derivee de la fonction partielle : y7!f(x0;y);eny0:

Elle est notee

@@y f(x0;y0)ou@f@y (x0;y0)(comprendre "Derivee defpar rapport ayen(x0;y0)").@@y f(x0;y0)existe si la fonction partielle y7!f(x0;y) est derivable eny0.

Exemples : Calculer les derivees partielles@@x

f(x0;y0) et@@y f(x0;y0) des fonctions et pour les points suivants : f(x;y) =x(y1) (x0;y0) = (0;0) f(x;y) =xexp(xy) (x0;y0) = (1;0) f(x;y) = lnxy (x0;y0) = (1;1) f(x;y) =p1x2y2(x0;y0) = (0;0) 6

Vecteur gradient

Denition 2.4.soitfune fonction de 2 variables dont les derivees partielles existent en un point(x0;y0)2R2. On appelle gradient defen(x0;y0)le vecteur deR2forme par les derivees partielles : rf(x0;y0) =@@x f(x0;y0);@@y f(x0;y0) Remarque importante: Sifpossede des derives partielles@f@x (x;y) et@f@y (x;y) en tout point d'un domaineDalors les fonctions denies surD: (x;y)7!@f@x (x;y) et (x;y)7!@f@y (x;y) sont elles m^emes des fonctions de deux variables des derivees partielles sont des fonctions de deux variables.

2.3. Derivees partielles du second ordre

Denition 2.5.Sifpossede des derivees partielles@f@x et@f@y et si ces deux fonc- tions possedent des derivees partielles on dit quefpossede des derivees partielles du second ordre. On note alors : 2f@x 2=@@x @f@x ;@2f@y@x =@@y @f@x 2f@y 2=@@y @f@y ;@2f@x@y =@@x @f@y Theorem 2.6(Theoreme de Schwarz).Sifpossede des derivees partielles du second ordre au voisinage de(x0;y0)et si les derivees partielles secondes croisees

2f@x@y

et@2f@y@x sont continues en(x0;y0)alors elles sont egales.

2f@x@y

(x0;y0) =@2f@y@x (x0;y0) Exemple : Calculer les derivees partielles du second ordre des fonctions suivantes.

Illustrez le Theoreme de Schwarz.

{f(x;y) =x(y1) {f(x;y) =p1x2y2

3. Semaine 3 : Developpement de Taylor

Denition 3.1.Soitf:DfR2!Rune fonction de deux variables, soit(x0;y0)2 D fet soitk0un entier positif. On dit quefest negligeable devantjj(xx0;yy0)jjk Mathematiques 2 : Optimisation7Figure 1: DL de log(1 +x2+y2) au voisinage de(x0;y0)si lim (x;y)!(x0;y0)f(x;y)jj(xx0;yy0)jjk= 0: Dans ce cas on peut mettre la fonctionfsous la forme: f(x;y) =jj(xx0;yy0)jjk(x;y);

Aveclim(x;y)!(x0;y0)(x;y) = 0

Theorem 3.2(Developpement limite de Taylor-Young du second ordre).Soitfune fonction de deux variables denie au voisinage de(x0;y0). On suppose quefadmet des derivees partielles secondes et que celles ci sont continues au voisinage de(x0;y0). Alors fadmet un developpement limite a l'ordre deux en(x0;y0): f(x;y) =f(x0;y0) +@f@x (x0;y0)(xx0) +@f@y (x0;y0)(yy0) 12 @2f@x

2(x0;y0)(xx0)2+ 2@2f@x@y

(x0;y0)(xx0)(yy0) +@2f@y

2(x0;y0)(yy0)2

+jj(xx0;yy0)jj2(x;y) aveclim(x;y)!(x0;y0)(x;y) = 0. Exemple: Calculer le Developpement l'ordre 2 en (0,0) de la fonctionf(x;y) = log(1 +x2+y2) (voir gure1 ) Exemple: Ecrire le DL d'ordre 2 en (0;0) puis en (1;1) des fonctions suivantes : 8 f(x;y) =x2+y2 f(x;y) =xy f(x;y) = exp(x+y)

Remarque 3.1.-

1. la plup artdes fonctions qu'on r encontreraadmetter ontun d eveloppementlimit e. 2. On p eutr eecrirela formule de T aylorY oung al'aide du gr adientintr oduitdans la section precedente : f(x0+u;y0+v) =f(x0;y0) +rf(x0;y0)(u;v) 12 @2f@x

2(x0;y0)u2+ 2@2f@x@y

(x0;y0)uv+@2f@y

2(x0;y0)v2

+ (u2+v2)(u;v) aveclim(u;v)!(0;0)(u;v) = 0. 3. Du d eveloppementd'or dre2 on p eutd eduirele d eveloppementdu pr emieror dre: f(x0+u;y0+v) =f(x0;y0) +rf(x0;y0)(u;v) +p(u2+v2)(u;v) aveclim(u;v)!(0;0)(u;v) = 0.

D'apres la remarque

3.1 3 , lorsque le vecteur de deplacement (u;v) est tres petit (c.f. gure 2 f(x0+u;y0+v)f(x0;y0) +rf(x0;y0)(u;v) Le gradient indique donc la direction de variation maximale de la fonction au voisinage de (x0;y0) : rf(x0;y0)(u;v) =jjrf(x0;y0)jj jj(u;v)jjcos() Ainsi la variation sera d'autant plus forte quejcos()jsera grand, c'est-a-dire quand la direction du deplacement sera proche de celle du gradient. a l'inverse sirf(x0;y0) (u;v) = 0 alors la variation est minimale : le gradient est orthogonal aux lignes de niveaux de la fonction. La gure 3 illustre ce rsultat sur une carte top ographique.P ourse rendre au sommet d'une montagne partant de son an il sut de se deplacer perpendiculairement aux lignes de niveaux, c'est a dire : suivre les gradients.

Exemple

f(x;y) = (x2+y2) tracer plusieurs lignes de niveaux defainsi que le gradient de fpour certains points faire de mme avec la fonctionf(x;y) =(x2+y2) Mathematiques 2 : Optimisation9Figure 2: Gradient et ligne de niveaux

Figure 3: illustration : carte Topographique

10 (a)f(x;y) =x2+y2(b)f(x;y) =x2+y2

4. Semaine 4 : Optimisation de fonctions d'une

variable reelle

4.1. Vocabulaire

l'optimisation libre contraste avec l'optimisation sous contraintes que nous verrons dans la suite du cours. Denition 4.1.soitf:Df!Rune fonction d'une variable etx02 Df. x0est un point de maximum (resp. minimum) global pourfsi pour toutx2 Df f(x)f(x0)(resp.x2 Dff(x)f(x0)).f(x0)est alors le maximum (resp. minimum) global def. x0est un point de maximum (resp. minimum) local pourfs'il existeun voisinage Vdex0(x02V Df) tel quex0soit un maximum (resp. minimum) global de la fonctionfrestreinte au domaineV. un extremum est un minimum ou un maximum. Remarque 4.1.Comme voisinageVdex0, on peut considerer l'intervalleV=]x0 r;x

0+r[avecraussi petit que l'on veut.

Denition 4.2.Sifest derivable surDfet six0est a l'interieur du domaineDf(pas sur le bord).x0est appele point stationnaire sif0(x0) = 0.

Mathematiques 2 : Optimisation11

Proposition 4.3.Sifest derivable surDf, six0est un extremum local situe l'interieur du domaineDfet sif0continue au voisinage dex0, alorsx0est un point stationnaire. Proof.Supposonsx0point de maximum local (preuve similaire six0point de minimum local) :f(x0+h)f(x0) pour touthassez petit. Developpement de Taylor defa l'ordre 1 enx0: f(x0+h) =f(x0) +f0(x0)h+h(h); ou lim h!0(h) = 0. Donc pourhpetit sih >0 ,f0(x0)+(h) =f(x0+h)f(x0)h

0 et, en prenant la limite en 0+,f0(x0)0

sih <0 ,f0(x0)+(h) =f(x0+h)f(x0)h

0 et, en prenant la limite en 0,f0(x0)0

nalementf0(x0) = 0Figure 4: Illustration maximum minimum Exemple :Trouver l'ensemble des points stationnaires et extremum globaux et locaux des fonctions suivantes (faire les tableaux de variation).

1.f(x) =x+ 5p5x1 + 1

2.f(x) =x3(x21)

3.f(x) =jxj

4.f(x) = log(x) que l'on deni uniquement sur [1;+1[

5.f(x) =x2

12

6.f(x) =x2

4.2. Application a l'optimisation sous contrainte d'une fonction

de deux variable : Methode de substitution Considerons une fonction de deux variablesf(x;y). On souhaite trouver les extremums defsous la contraintey=g(x). exemple : Maximiserf(x;y) sous la contraintey=g(x), c'est a dire, trouver maxff(x;y)j(x;y)2 Dfety=g(x)g:Figure 5: Optimisation sous contrainte La methode de substitution consiste simplement a trouver les extremums de la fonction d'une variable :ef(x) =f(x;g(x)). Exemple: Optimiser sous les contraintes indiquees les fonctions suivantes :

1.f(x;y) =x2+y2, sous la contrainte :x+y= 1

2.f(x;y) =xy, sous la contrainte :xy= 1

Mathematiques 2 : Optimisation13

4.3. Convexite et caractrisation des extremums

Denition 4.4(Convexite).Sifest deux fois derivable sur son domaine de denition D f. On dit quefest convexe (resp. concave) sif000(resp.f000). On dit quefest localement convexe (resp. localement concave) autour d'un point x

0situe l'interieur deDfs'il existe un voisinageVdex0tel quef00(x)0(resp.

f

00(x)0) pour toutx2V.

Remarque 4.2.Sif00>0on dit quefest strictement convexe. Proposition 4.5.f est convexe (resp. concave) sur un intervalleIssif(tx+(1t)y) tf(x) + (1t)f(y)(resp.f(tx+ (1t)y)tf(x) + (1t)f(y)) pour toutx;y2Iet toutt2[0;1]. Remarque 4.3.Cette caracterisation de la convexite est generalement prise comme denition. Exemple :Reprendre les fonctions de la partie4.1 et discuter leur con vexite.

Proposition 4.6.1.fconvexe ssifconcave.

2.

Une somme de fonctions c onvexesest c onvexe.

3. Un pr oduitde fonctions c onvexesn 'esten g eneralpasconvexe.(contre exemplequotesdbs_dbs7.pdfusesText_13

[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