[PDF] COURS OPTIMISATION Cours à lISFA en M1SAF Ionel Sorin

View - Download COURS OPTIMISATION Cours à lISFA en M1SAF Ionel Sorin

Previous PDF

Next PDF

COURS OPTIMISATION

Cours à l"ISFA, en M1SAF

Ionel Sorin CIUPERCA

1

Table des matières

1 Introduction 4

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Le problème général d"optimisation . . . . . . . . . . . . . . . . . . . . . . 4

2 Quelques rappels de calcul différentiel, analyse convexe et extremum 5

2.1 Rappel calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Quelques Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.2 Rappel gradient et hessienne . . . . . . . . . . . . . . . . . . . . . 6

2.1.3 Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Rappel fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.2 Fonctions elliptiques, fonctions coercives . . . . . . . . . . . . . . . 12

2.2.3 Exemples des fonctions elliptiques . . . . . . . . . . . . . . . . . . . 14

2.3 Conditions nécéssaires de minimum . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Existence et unicité d"un point de minimum . . . . . . . . . . . . . . . . . 18

3 Optimisation sans contraintes 20

3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1.1 Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 21

3.1.2 Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 24

3.2 Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2.1 Méthodes de gradient à pas optimal . . . . . . . . . . . . . . . . . . 26

3.2.2 Autres méthodes du type gradient . . . . . . . . . . . . . . . . . . . 27

3.3 La méthode des gradients conjugués . . . . . . . . . . . . . . . . . . . . . . 30

3.3.1 Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.2 Cas d"une fonctionJquelconque . . . . . . . . . . . . . . . . . . . 35

4 Optimisation avec contraintes 36

4.1 Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . 37

4.2 Optimisation sous contraintes d"inégalités . . . . . . . . . . . . . . . . . . . 38

4.2.1 Conditions d"optimalité de premier ordre : multiplicateurs de Karush-

Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2.2 Théorie générale du point selle . . . . . . . . . . . . . . . . . . . . . 46

2

4.2.3 Applications de la théorie du point selle à l"optimisation . . . . . . 48

4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.3 Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 51

4.3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3.2 Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.3 Méthodes de pénalisation exterieure . . . . . . . . . . . . . . . . . . 56

4.3.4 Méthode d"Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3

Chapitre 1

Introduction

1.1 Motivation

Voir cours en amphi

1.2 Le problème général d"optimisation

On se donne :

1. Une fonctionJ:IRn7!IR(fonction coût)

2. Un ensembleUIRn(ensemble des contraintes)

On cherche à minimiserJsurU, c"est à dire, on cherchex2Utel que

J(x) = minx2UJ(x)

ou équivalent

J(x)J(x);8x2U:

4

Chapitre 2

Quelques rappels de calcul différentiel,

analyse convexe et extremum

2.1 Rappel calcul différentiel

2.1.1 Quelques Notations

1. Pour toutn2IN;IRndésigne l"espaceeuclidienIRIRIR( "produitnfois").

En général un vecteurx2IRnsera notéx= (x1;x2;xn)T(vecteur colonne).

2. On notee1;e2;enles éléments de labase canoniquedeIRn, oùeiest le vecteur

deIRndonné par : (ei)j=ij=0sij6=i

1sij=i;8i;j= 1;2n(2.1)

(symboles deKronecker).

3. Pour tousx;y2IRnon note par< x;y >2IRleproduit scalairedexety, qui

est donné par < x;y >=nX i=1x iyi:

4. Pour toutx2IRnon note parkxk 0lanorme euclidiennedex, donnée par

kxk=p< x;x >=v uutn X i=1x 2i: Pour tousx2IRnetr >0on notera parB(x;r)laboule ouvertedu centrexet rayonr, donnée par

B(x;r) =fy2IRn;kyxk< rg:

5

5. Sia;b2IRnon note[a;b]le sous-ensemble deIRndonné par

[a;b] =fa+t(ba)(1t)a+tb; t2[0;1]g: L"ensemble[a;b]est aussi appelléle segmentreliantaàb.

Remarques :

[a;b] = [b;a](Exo!) Sia;b2IRaveca < balors on retrouve le fait que[a;b]désigne l"intervalle des nombresx2IRtels queaxb.

6. On a

< Bx; y >=< x;By >8x2IRn; y2IRm; B2 Mm;n(IR)

7. Rappellons aussi l"inégalité de Cauchy-Schwarz :

j< x; y >j kxk kyk 8x;y2IRn:

2.1.2 Rappel gradient et hessienne

Soit

IRnunouvertetf:

!IR.

1. On dit quefest de classeCmsur

(f2Cm( ))si toutes les dérivées partielles jusqu"à l"ordremexistent et sont continues.

2. Pour toutx2

et touti2 f1;2;;ngon note (quand9) @f@x i(x) = limt7!01t [f(x+tei)f(x)]: (c"est ladérivée partielledefenxde directionxi.)

3. Pour toutx2

on note (quand9) rf(x) =@f@x

1;@f@x

2;@f@x

n T

2IRn;8x2

(legradientdefenx).

On note aussi

J f(x) =@f@x

1;@f@x

2;@f@x

n

2IRn;8x2

(laJacobiennedefenx). On a rf= (Jf)T

4. Pour tousx2

eth2IRnon note (quand9) @f@h (x) = limt7!01t [f(x+th)f(x)] =g0(0): 6 (c"est ladérivée directionnelledefenxde directionh) où on a notég(t) = f(x+th).

Remarques :

i)@f@0(x) = 0 ii)@f@x i(x) =@f@e i(x)

Nous rappellons aussi la formule :

@f@h (x) =;8x2

8h2IRn:

5. Pourx2

on note (quand9)r2f(x) =la matrice carrée2 Mn(IR)donnée par r2f(x) ij=@2f@x i@xj(x);8i;j= 1;2;n: (r2f(x)s"appelle aussila matrice hessiennedefenx).

Remarque :Sif2C2(

)alorsr2f(x)est une matricesymmétrique8x2 (c"est le Théorème de Schwarz). Proposition 2.1.(Gradient de la composée) Supposons qu"on deux ouverts IRnet

UIR et deux fonctionsf:

7!IR etg:U7!IR avec en plusf(

)U(on peut alors définirgf:

7!IR). Supposons que f, g sont de classeC1. Alorsgfest aussi de classe

C

1avec en plus

r(gf)(x) =g0(f(x))rf(x)8x2

Preuve très facile!

Proposition 2.2.(lien entreretr2)

a)Lai- ème ligne der2f(x)est la Jacobienne dui- ème élément derf. b)On a r

2f(x)h=r;8x2

;8h2IRn:

Démonstration.a)évidente

b)On a : @@x i=@@x i nX j=1@f@x j(x)hj! =nX j=1@ 2f@x ixj(x)hj=r2f(x)h i:Quelques exemples importantes :

1. Sif:IRn!IRest une fonctionconstantealorsrf=r2f= 0.

7

2. Soitf:IRn!IRdéfinie par

f(x) =< a; x >8x2IRn; oùa2IRnest un vecteur donné (c"est à dire,fest une fonctionlinéaire). Alors on calcule facilement : @f@x k=ak;donc rf=a (le gradient est constant).

Ceci nous donne

r

2f= 0:

3. Soitf:IRn!IRdonnée par

f(x) =< Ax; x >8x2IRn; oùA2 Mn(IR)est un matrice carrée, réelle, de taillen(c"est à dire,fest la fonction quadratiqueassociée à la matriceA). Alors pour unp2 f1;2;ngfixé, on peut

écrire

f(x) =nX i;j=1A ijxixj=Appx2p+nX j=1;j6=pA pjxpxj+nX i=1;i6=pA ipxixp+nX i;j=1;i6=p;j6=pA ijxixj ce qui nous donne @f@x p= 2Appxp+nX j=1;j6=pA pjxj+nX i=1;i6=pA ipxi=nX j=1A pjxj+nX i=1A ipxi= (Ax)p+(ATx)p:

Nous avons donc obtenu :

rf(x) = (A+AT)x;8x2IRn:

On peut aussi écrire

@f@x i(x) =nX k=1(A+AT)ikxk;8i= 1;;n:

On a alors immédiatement :

2f@x i@xj(x) = (A+AT)ij;8i;j= 1;;n: c"est à dire r

2f(x) =A+AT;8x2IRn

(donc la hessienne defest constante). Remarque :En particulier, siAestsymmétrique(c"est à direA=AT) alors r< Ax; x >= 2Ax;8x2IRn: r

2< Ax; x >= 2A;8x2IRn:

8

2.1.3 Rappel formules de Taylor

Proposition 2.3.(sans preuve)

Soit

IRnouvert,f:

7!IR;a2

eth2IRntels que[a;a+h] . Alors :

1. Sif2C1(

)alors i)f(a+h) =f(a) +R1

0 dt

(formule de Taylor à l"ordre 1 avec reste intégral). ii)f(a+h) =f(a)+avec0< <1 (formule de Taylor - Maclaurin à l"ordre 1) iii)f(a+h) =f(a)++o(khk) (formule de Taylor - Young à l"ordre 1)

2. Sif2C2(

)alors i)f(a+h) =f(a)++R1

0(1t) dt

(formule de Taylor à l"ordre 2 avec reste intégral). ii)f(a+h) =f(a)++12 avec0< <1 (formule de Taylor - Maclaurin à l"ordre 2) iii)f(a+h) =f(a)++12 +o(khk2) (formule de Taylor - Young à l"ordre 2). Remarque :Dans la proposition précédente la notationo(khkk)pourk2INsignifie une expression qui tend vers 0 plus vite quekhkk(c"est à dire, si on la divise parkhkk, le résultat tend vers 0 quandkhktend vers 0).

2.2 Convexité

2.2.1 Rappel fonctions convexes

Définition 2.4.Un ensembleUIRnest ditconvexesi8x;y2Uon a[x;y]U (quelque soit deux points dansU, tout le segment qui les unit est dansU). Définition 2.5.SoitUIRnun ensemble convexe etf:U!IRune fonction.

1. On dit quefestconvexesurUsi

f(tx+ (1t)y)tf(x) + (1t)f(y);8x;y2U;8t2[0;1]

2. On dit quefeststrictement convexesurUsi

f(tx+ (1t)y)< tf(x) + (1t)f(y);8x;y2Uavecx6=y;8t2]0;1[:

3. On dit quefestconcave(respectivementstrictement concave) sifest convexe

(respectivement strictement convexe). 9 Remarque :Il est facile de voir que toute fonction strictement convexe est convexe, mais que la réciproque n"est pas vraie en général. Par exemple une application affinef(x) =Ax+best convexe (et aussi concave) mais elle n"est pas strictement convexe (ni strictement concave). On montre facilement le résultat utile suivant : Proposition 2.6.SoitUIRnun ensemble convexe,p2IN,f1;f2;;fp:U!IR des fonctions convexes et 1; 2;; ndes constantes strictement positives.

Posonsf=

1f1+ 2f2+ pfp. Alors on a : a)La fonctionfest convexe (donc toute combinaison linéaire avec des coefficients stric- tement positifs de fonctions convexes est convexe). a)Si au moins une des fonctionsf1;;fpest strictement convexe alorsfest strictement convexe.

Démonstration.Laissée en exercice!Il est en général difficile de vérifier la convexité d"une fonction en utilisant uniquement

la définition (essayez avecf(x) =x2ou avecf(x) =x4!) La proposition suivant donne

des critères de convexité plus faciles à utiliser pour montrer la convexité ou la convexité

stricte d"une fonction.

Proposition 2.7.Soit

IRnouvert,U

avecUconvexe etf:

7!IR une fonction.

Alors on a :

Partie I(caractérisation de la convexité avec "r").

Supposons quefest de classeC1. Alors

1.fest convexe surUsi et seulement si :

f(y)f(x)+;8x;y2U

2.fest strictement convexe surUsi et seulement si :

f(y)> f(x)+;8x;y2Uavecx6=y:

3.fest convexe surUsi et seulement sirfestmonotone surU, c"est à dire

08x;y2U:

4. Sirfest strictement monotone surU(c"est à dire :

>08x;y2Uavecx6=y) alorsfest strictement convexe surU. Partie II(caractérisation de la convexité avec "r2").

Supposons quefest de classeC2. Alors

10

1.fest convexe surUsi et seulement si :

0;8x;y2U 2. Si >0;8x;y2Uavecx6=y alorsfest strictement convexe surU.

Remarques :

1. Dans le cas particulier où

=U=IRnalors les deux inégalités de laPartie IIde la proposition précédente peuvent s"écrire : 0;8x;h2IRn et respectivement >0;8x;h2IRn;avech6= 0:

2. Dans le cas particuliern= 1et

un intervalle ouvert dansIR, on ar2f(x) =f00(x), donc=f00(x)(yx)2. Alors les deux inégalités de laPartie IIde la proposition précédente peuvent s"écrire : f

00(x)0;8x2U

et respectivement f

00(x)>0;8x2U:

On rétrouve un résultat bien connu!

Exemple :Soitf:IR!IRdonnée parf(x) =x2. Commerf(x) =f0(x) = 2xon a

8x;y2IR:

f(y)f(x)=y2x22x(yx) =y2+x22xy= (yx)2>0six6=y et ceci montre la stricte convexité de cette fonction, en utilisant laPartie I2)de la proposition précédente.

On peut aussi utiliser la Partie I4) :

= 2(yx)2>0siy6=x doncfest strictement convexe. C"est encore plus facile si on utilise laPartie II: f

00(x) = 2>0

doncfest strictement convexe. 11

2.2.2 Fonctions elliptiques, fonctions coercives

Définition 2.8.Soitf:IRn!IR. On dit quefest une fonctionelliptiquesi elle est de classeC1et si9 >0telle que kxyk2;8x;y2IRn:

Définition 2.9.Soit

IRnun ensemblenon bornéetf:

!IR. On dit quefest coercivesur si on a limx2 ;kxk7!+1f(x) = +1: Proposition 2.10.Soitf:IRn!IR une fonction elliptique. Alors elle est strictement convexe et coercive. Elle vérifie en plus l"inégalité : f(y)f(x)++2 kyxk2;8x;y2IRn:(2.2) Démonstration.Montrons d"abord l"inégalité (2.2). On utilise la formule de Taylor à l"ordre 1 avec reste intégral. On a f(y) =f(x) +Z 1 0 dt ce qui nous donne f(y)f(x)=Z 1 0 1t dt: En utilisant le fait quefest elliptique on déduit : kt(yx)k2 ce qui nous donne (cart >0) : f(y)f(x)kyxk2Z 1 0 tdt=2 kyxk2 ce qui prove (2.2). Montrons la stricte convexité def: de la définition de l"ellipticité on déduit : >0;8x;y2IRnavecx6=y: ce qui nous donne la convexité stricte def, comme conséquence de la Partie I4 de la Proposition 2.7 (autre méthode : utiliser (2.2) et la Partie I2 de la Proposition 2.7).

Montrons la coercivité def.

En prennantx= 0en (2.2) on obtient

f(y)f(0)++2 kyk2:(2.3) 12 Nous utilisons l"inégalité de Cauchy-Schwarz jj krf(0)kkyk qui nous donne krf(0)kkyk;8y2IRn: En utilisant cette dernière inégalité en (2.3) on déduit f(y)f(0) krf(0)kkyk+2 kyk2 ce qui nous donne f(y)7!+1sikyk 7!+1:

La preuve de la proposition est alors terminée.Proposition 2.11.(Caractérisation de l"ellipticité avec "r2")

Soitfune fonction de classeC2. Alorsfest elliptique si et seulement si9 >0tel que khk2;8x;h2IRn:(2.4) Démonstration.a)Supposons quefest elliptique et montrons (2.4). Soith2IRnfixé et notonsg:IRn7!IRla fonction donnée parg(x) =;8x2IRn. Nous avons en utilisant aussi la Proposition 2.2 : ==@g@h (x) = limt7!0t En utilisant la bilinéarité du produit scalaire et ensuite le fait quefest elliptique, on obtient : = limt7!0t

2kthk2t

2=khk2

ce qui nous donne (2.4) avec=. b)Supposons maintenant que (2.4) est satisfaite et montrons quefest elliptique. Soient x;y2IRnfixées arbitraires, et considérons la fonctiong1:IRn7!IRdonnée par g

1(z) =;8z2IRn. Alors

=g1(x)g1(y) = avec2]0;1[(on a utilisé l"une des formules de Taylor).

D"autre part, nous avons

rg1(z) =r2f(z)(xy) et ceci nous permet de déduire, en utilisant aussi (2.4) : =kxyk2:

On a donc obtenu l"ellipticité defavec=.13

On a aussi le résultat suivant :

Proposition 2.12.Soitp2IN,f1;f2;;fp:IRn!IR des fonctions de classeC1et convexes et 1; 2;; ndes constantes strictement positives. Si au moins une des fonctionsf1;;fpest elliptique alorsf 1f1+ 2f2+ pfpest elliptique. Démonstration.Soiti2 f1;2;pgtel quefisoit elliptique. Alors il existe >0tel que kxyk28x;y2IRn:

D"autre part, comme tous lesfksont convexes on a

08x;y2IRn;8k6=i:

En multipliant la première inégalité par

iet les autres par ket en sommant enk, on obtient immédiatement le résultat.2.2.3 Exemples des fonctions elliptiques

1.Sin= 1:

Toute fonctionf:IR!IRde classeC2et satisfaisant :

9 >0; f00(x);8x2IR

est une fonction elliptique (c"est une conséquence immédiate de la Proposition 2.11).

Exemples :

i)f(x) =ax2+bx+caveca >0 ii)f(x) =x2+ sin(x)(carf00(x) = 2sin(x)1;8x2IR).

2.Le cas général (n2IN)

Soitf:IRn!IRdonnée par

f(x) =12 < Ax; x >< b;x >+c;8x2IRn(2.5) avecA2 Mn(IR)une matrice carrée réelle etsymmétriquede taillen, avecb2IRn un vecteur etc2IRun scalaire(on appelle encore, par abus de language, fonction (ou forme)quadratiqueune fonction de ce type). On calcule facilement : rf(x) =Axb r

2f(x) =A

(donc la hessienne defest constante). CommeAest symmétrique alors on sait que toutes les valeurs propres deAsont réelles et que < Ah; h >minkhk2;8h2IRn 14 oùmin2IRest la plus petite valeur propre deA. Rémarquons que l"inégalité précédente devient égalité sihest un vecteur propre associé à la valeur propremin. Rappellons aussi queAest une matricedéfinie positivesi et seulement simin>0. (par définition une matrice carrée rélleB2 Mn(IR)est définie positive si < Bx;x > >0;8x2IRn; x6= 0). En utilisant la Proposition 2.11 on déduit quefest une fonction elliptique si et seulement siAest une matrice définie positive. (Voir des exemples "concrètes" en TD).

2.3 Conditions nécéssaires de minimum

Définition 2.13.SoitUIRn; u2Uetf:U!IR.

quotesdbs_dbs29.pdfusesText_35

[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