[PDF] Optimisation. alors on dit que m?

View - Download Optimisation.

Previous PDF

Next PDF

Optimisation.

Université Aix-Marseille

Préparation à l"agrégation (Option B)

2020/2021

Thomas Ourmières-Bonafos

Table des matières

1 Introduction 1

1.1 Extrait du programme de l"agrégation externe 2020 . . . . . . . . 1

1.2 Borne inférieure et minima . . . . . . . . . . . . . . . . . . . . . 2

1.3 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Questions associées au problème d"optimisation . . . . . . . . . . 4

1.5 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Rappels des outils mathématiques 7

2.1 Calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.1 Différentielle d"ordre un . . . . . . . . . . . . . . . . . . . 7

2.1.2 Différentielle d"ordre deux . . . . . . . . . . . . . . . . . . 14

2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Existence et unicité des minimiseurs 19

3.1 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Unicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 Caractérisation des minimiseurs 20

4.1 Problème sans contrainte . . . . . . . . . . . . . . . . . . . . . . 20

4.2 Problème avec contrainte . . . . . . . . . . . . . . . . . . . . . . 22

5 Méthodes de Gradient 23

5.1 Notion d"-convexité . . . . . . . . . . . . . . . . . . . . . . . . . 23

5.2 Méthode du gradient à pas constant . . . . . . . . . . . . . . . . 24

5.3 Méthode du gradient à pas optimal . . . . . . . . . . . . . . . . . 24

5.4 Méthode de gradient pour l"optimisation sous contrainte . . . . . 25

5.5 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 26

A Théorème de Rayleigh-Ritz 28

1 B Théorème de projection sur un convexe fermé 29

1 Introduction

1.1 Extrait du programme de l"agrégation externe 2020

Avant de commencer, on prendra connaissance du programme de l"agrégation externe, qui détaille les notions à maîtriser concernant les problèmes d"optimi- sation (voir Figure 1.1).Figure1 - Extrait du programme de l"agrégation 2020 concernant la partie optimisation. Disponible à l"url suivante :http://media.devenirenseignant.

1.2 Borne inférieure et minima

Définition 1 (Minorant d"un sous-ensemble deR)SoitJR. On dit quem2Rest un minorant deJsi pour toutx2Jon a mx: Définition 2SoitJR.Jest minorée s"il existe un minorant deJ. Autre- ment dit,Jest minorée s"il existem2Rtel que pour toutx2Jon ait mx: 2 Définition 3SoitJR, l"ensemble des minorants deJest

M(J) :=fm2R:pour toutx2J;mxg:

Définition 4SoitJR. S"il existem?2Rtel que pour toutm2M(J)on a mm? alors on dit quem?est la borne inférieure deJet on notem?= inf(J). Exercice 1 (?10min)Pour les ensembles suivants, démontrer s"ils sont ou non minorés et déterminer leur ensemble des minorants.

1.J1= [0;1],J2=]0;1],J3=]5;2][[5;8[,J4= [12;5][] 1;20],

J

5=] 1;2]\]0;1].

2.J=fun:n2Ngoù la suite(un)n2N2RNest définie par

u n=2nsinest pair;

2nsinest impair:

3.Jk=ffk(x) :x2Rgoù pourk2 f1;2;3gla fonctionfkest définie par

f 1:R!R x7!x23x+ 2; f2:R!R x7!ln(jxj+ 1); f

3(x) :=

1x six6= 0;

0sinon:

4.J=fcos(x1x2) :x1;x22Rg.

On commence par rappeler la proposition suivante à propos de l"existence d"une borne inférieure. Proposition 1Tout sous-ensembleJRnon vide et minoré admet une borne inférieurem?2R. Nous rappelons à toutes fins utiles les caractérisations suivantes de la borne inférieure. Proposition 2SoitJRnon vide et minoré. Il y a équivalence entre

1.m?= inf(J),

2.m?2M(J)et pour tout" >0il existem2Jtel quem?m < m?+".

3.m?2M(J)et il existe une suite(mn)n2N2JNtelle quelimn!+1mn=

m Nous proposons de faire la démonstration de ces points dans les questions sui- vantes. 3

Exercice 2 (?10min)Démontrer la Proposition 2.

Soitd1, considérons maintenant une fonctionf:ARd!R.

Définition 5 (Minimum local & Minimum global)

1.fadmet un minimum local enx?2Assidéf

9 >0;8x2Atel quekxx?kRd=)f(x?)f(x):

2.fadmet un minimum global enx?2Assidéf

8x2A; f(x?)f(x);

en particulier, on af(x?) = infff(x) :x2Ag. Exercice 3 (?5min)Pour les fonctionsfjsuivantes définies surAj2Rd, dire si elles sont minorées. Si oui, donnerinfffj(x) :x2Ajg, dire si c"est un minimum global et discuter l"unicité du minimiseur. f

1:R!R;

x7!x2; f2:R!R; x7!sin(x); f3:]1;+1[!R; x7!1jln(x)j f

4:R2!R;

(x1;x2)7!ex1jcos(x2)j

1.3 Généralités

Dans ce cours, on s"intéresse à la minimisation d"une fonctionf:A!Roù Aest un sous-ensemble de l"espace vectoriel norméRd(d1). La fonctionf est apellée l"objectifet, en termes mathématiques, le problème d"optimisation consiste à s"intéresser à la quantité infff(x) :x2Ag:(1) On dit que le problème d"optimisation est sans contrainte siA=Rdet il est dit avec contraintes sinon. Remarque 1En lieu et place du problème de minimisation(1), on peut être amené à étudier le problème de maximisation supff(x) :x2Ag: Il s"agit également d"un problème dit d"optimisation. Toutefois, par le simple changement defenf, on peut se ramèner systématiquement au problème de minimisation, cas que nous considérons dans ce cours. 4

1.4 Questions associées au problème d"optimisation

Lorsque l"on s"intéresse au problème d"optimisation (1) plusieurs questions " naturelles » apparaissent et nous les commentons maintenant. Question 1 (Existence d"un minimiseur)Il s"agit de savoir si " l"inf est un min » dans(1). En termes mathématiques, on se demande s"il existex?2A tel que f(x?) = infff(x) :x2Ag: Si la réponse est positive, alors l"infimum dans(1)est un minimum et il atteint enx?. Pour pouvoir répondre par l"affirmative à la Question 1 on utilise essentiel- lement un argument de continuité de la fonction objectiffcombiné ou bien à la compacité deAou alors à la coercivité de la fonction objectiff. Ces résultats font l"objet du §3.1. Question 2 (Unicité du minimiseur)Supposons qu"il existex?2Atel que f(x?) = infff(x) :x2Ag: Cex?est-il le seul élément deAà réaliser le minimum de la fonction objectif fsurA? En termes mathématiques, six#2Avérifie f(x#) = infff(x) :x2Ag; a-t-onx#=x?? L"argument le plus utilisé pour répondre par l"affirmative à la Question 2 est la convexité de la fonction objectiff. On en discute au §3.2. Question 3 (Caractérisation du (des) minimiseur(s))S"il existe un (des) minimiseur(s), comment peut-on le (les) caractériser? On utilise en grande partie des outils issus du calcul différentiel. Nous en faisons quelques rappels au §4. Question 4 (Résolution numérique)Quels algorithmes peut-on mettre en oeuvre afin de résoudre un problème de minimisation de type(1)? On discute le cas des algorithmes de gradient à pas constant et optimal au §5. Finalement, les Question 1-4 se résument à la liste suivante. On peut l"in- terpréter comme une " marche à suivre » lorsque l"on s"attaque à un problème d"optimisation.1. Existence d"un minimiseur.

2. Y a-t-il unicité des minimiseurs?

3. Peut-on caractériser un minimiseur par une condition nécessaire ou suffi-

sante?

4. Quel(s) algorithme(s) permettent de résoudre (1) numériquement?5

1.5 Quelques exemples

Les problèmes d"optimisation sont courants en mathématiques, voilà quelques exemples que vous avez probablement déjà rencontrés. Exemple 1 (Projection sur un compact en dimension finie)On considère R dmuni de son produit scalaire usuel etC Rdun ensemble compact. Pour y2Rdfixé, on s"intéresse à l"infimum inffkxyk:x2 Cg: Dans cet exemple, en reprenant les notations utilisées en(1), on a : (i) Le sous-ensembleARdest ici l"ensemble compactC. (ii) La fonction objectiffest donnée pourx2 Cparf(x) =kxyk. L"exemple 1 est un " cousin » du théorème de projection sur un convexe fermé (grand classique de l"agrégation). Vous pouvez le retrouver dans l"appendice B. Exemple 2 (Plus petite valeur propre d"une matrice symmétrique réelle) Soitd2NetM2Sd(R). On sait queMest diagonalisable dansRet on note

1(M)sa plus petite valeur propre. En particulier, le théorème de Rayleigh-Ritz

(voir Proposition 17) donne la caractérisation

1(M) = inffhMx;xi:x2Rd;kxk= 1g;

oùh;iest le produit scalaire usuel dansRdetkkest la norme associée. Ainsi, trouver la plus petite valeur propre d"une matrice symétrique réelle revient à étudier un problème d"optimisation. En reprenant les notations utilisées en(1), on a ici : (i) Le sous-ensembleARdest ici la sphère unité deRdc"est à direSd1:= fx2Rd:kxk= 1g. (ii) La fonction objectiffest donnée pourx2Sd1parf(x) =hMx;xi. Exemple 3 (Problème des moindres carrés)SoitN2Net(xj;yj)1jN Npoints deR2(on parle ici de nuage de points). Pourd2N, on considère le problème de minimisation suivant inffNX j=1jyjP(xj)j2:P2Rd[X]g: Autrement dit, on cherche un polynômeP?de degré au plusdqui approche le " mieux possible » le nuage de point. L"expression le " mieux possible » voulant dire ici qu"au sens de la norme2dansRNles vecteursy= (y1;;yN)et P ?=P?(x1);;P?(xN)sont les plus proches possibles. Afin de considérer 6 ce problème comme un problème d"optimisation on identifieRd[X]avecRd+1 grâce à l"isomorphisme canonique ':=8 :R d[X]!Rd+1

P(X) =dX

j=0a jXj7!(a0;;ad): En reprenant les notations utilisées en(1), on a ici

1. Le sous ensembleA=Rd+1.

2. La fonction objectiffest donnée, pour touta= (a0;:::;ad)2Rd+1par

f(a) =NX j=1 yjdX k=0a kxkj2:

2 Rappels des outils mathématiques

On rappelle plusieurs notions préalable à l"étude de problèmes d"optimisa- tions.

2.1 Calcul différentiel

Lorsque l"on étudie des problèmes d"optimisation, on se restreint au cadre de fonctionsf:URd!RavecUun ouvert deRd.

2.1.1 Différentielle d"ordre un

On commence par rappeller la notion de dérivée directionnelle. Définition 6Soith2Sd1etx02U. Si la fonctiont7!f(x0+th)est dérivable ent= 0, on définit la dérivée directionnelle defau pointx0dans la directionhcommeddt (f(x0+th))jt=0. Exercice 4 (?10min)Pour les fonctions suivantes, calculer (si elles existent) les dérivées directionnelles aux points et directions données.

1.f1: (x;y)2R27!xcos(y)+yexp(x)en(0;0)dans la direction(1p2

;1p2 2. f

2(x;y) =:

xyx

2+y2si(x;y)6= (0;0)

0sinon

en(0;0)dans la direction(1p2 ;1p2 )puis dans la direction(cos();sin()) pour2[0;2). 7 Lorsqu"elle existe, on définit la dérivée partielle defpar rapport à laj-ième variablexjen un pointx02Ucomme la dérivée directionnelle defenx0dans la direction deej= (0;:::;1;:::;0), lej-ème vecteur de la base canonique de R d. On note alors @f@x j(x0) := limt!0 f(x0+tej)f(x0)t =ddt f(x0+tej)jt=0 Remarque 2Sifest dérivable enx0dans la directionej, on note parfois la dérivée partielle@jf(x0)en lieu et place de@f@x j(x0). Exercice 5 (?5min)Calculer les dérivées partielles en(x;y;z)2R3de la fonction f:R3!R (x;y;z)7!xcos(xz) + ln(2sin2(y+z)) Exercice 6 (?5min)Calculer les dérivées partielles en(1;p3;1)de la fonc- tion f:R3!R (x;y;z)7!px

2+y2+z2

Par la suite, nous aurons besoin d"une notion " plus forte » qui est la notion de base en calcul différentiel, celle d"application différentiable. Définition 7 (Application différentiable)On dit quefest différentiable en x

02Us"il existe une forme linéaireL2 L(Rd;R)telle que pour touth2Rd

tel quex0+h2Uon ait f(x0+h) =f(x0) +L(h) +o(khk); h!0: Par définition, la différentielle defenx0estDf(x0) :=L2 L(Rd;R). On dit quefest différentiable surVUssidéfpour toutx2V,fest différentiable enx. Remarque 3D"autres auteurs peuvent utiliser des notations différentes comme, par exemple :

Df(x0) =df(x0) =dx0f:

Exercice 7 (?12min)

1. Montrer que sif:U!Rest différentiable enx02Ualorsfest continue

enx0.

2. Montrer que sif:U!Rest différentiable enx02Ualorsfadmet en

x

0des dérivées dans toutes les directionsh2Sd1.

3. Montrer que sif:U!Rest différentiable enx02Ualors pour tout

h2Rdon a

Df(x0)(h) =ddt

f(x0+th) j t=0: 8

4. Montrer que la fonctionf:x= (x1;;xd)2Rd7! kxk=qP

d j=1x2j est continue en0mais pas différentiable en0.

Exercice 8 (?15min)

1. Soitf:R!Rdérivable enx02R. Montrer quefest différentiable en

x

0et donner sa différentielle.

2. Soiru2 L(Rd;R)une application linéaire. Montrer queuest différentiable

en toutx2Rdet donner sa différentielle.

3. Soitu2 BL(Rd;R)une forme bilinéaire deRdà valeurs dansR. Montrer

queuest différentiable en tout(x;y)2RdRd)et donner sa différentielle.

4. SoitM2Rdd, montrer que l"application'M:x2Rd7! hMx;xiRdest

différentiable en tout point deRdet donner sa différentielle. Exercice 9 (?15min)Pourj2 f1;:::;dg, on introduit l"application coor- donée : e j:Rd!R (x1;:::;xd)7!xj

1. Montrer queejest une forme linéaire, c"est-à-dire une application linéaire

deRd!R. Quelle est la matrice deejdans la base canonique deRd?

2. Démontrer que sif:U!Rest différentiable enx02Ualors on a

Df(x0) =dX

j=1@f@x j(x0)ej: Dans quel espace vectoriel cette égalité est-elle vraie? Quelle est la matrice deDf(x0)dans la base canonique deRd? Remarque 4Historiquement, Leibniz notait la forme linéaireejcommedxj. C"est dans ce sens que l"on doit comprendre la relation

Df(x0) =dX

j=1@f@x j(x0)dxj que l"on trouve en physique ou dans certains ouvrages mathématiques. Exercice 10 (?5min)Après avoir rappelé le théorème de représentation de Riesz, justifier que sif:U!Rest différentiable enx02Ualors il existe un unique élémentG(f)x02Rdtel que pour touth=Pd j=1hjejon ait

Df(x0)(h) =hG(f)x0;~hi;où~h=0

B @h 1... h d1 C A: Donner explicitementG(f)x0.G(f)x0est le gradient defenx0(voir ci-dessous). 9 Définition 8 (Gradient)Lorsquefest différentiable enx02Uon définit le gradient defau pointx0comme rf(x0) :=0 B @@f@x 1(x0) @f@x d(x0)1 C A2Rd:

En particulier, pourh=Pd

j=1hjej, on obtient :

Df(x0)(h) =hrf(x0);~hiRd;où~h=0

B @h 1... h d1 C A: Exercice 11 (?15min - Calculs de gradients)Après avoir justifier leur existence, calculer le gradient des fonctions suivantes au poins indiqués.

1. En tout point deR2:

f

1:R2!R

(x;y)7!x2y+y2; f2:R2!R (x;y)7!x2y+y2; f

3:R2!R

quotesdbs_dbs33.pdfusesText_39

[PDF] démonstration variance probabilité

[PDF] relation de chasles parallélogramme

[PDF] vecteurs opposés

[PDF] vecteur nul exemple

[PDF] remplacement alternateur espace 3 2.2 dci

[PDF] tuto changement alternateur espace 4

[PDF] demontage alternateur espace 4 2.2 dci

[PDF] demontage alternateur espace 2 diesel

[PDF] demontage alternateur espace 4 1.9 dci

[PDF] prix changement alternateur espace 3

[PDF] changer alternateur renault espace 3

[PDF] tuto alternateur espace 4

[PDF] compétences conjugaison cm2 2016

[PDF] travailler la conjugaison en s amusant

[PDF] exercice radical terminaison ce2