[PDF] COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

View - Download COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

Previous PDF

Next PDF

COURS OPTIMISATION

Cours en Master M1 SITN

Ionel Sorin CIUPERCA

1

Table des matières

1 Introduction 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 Quelques rappels sur le calcul différentiel . . . . . . . . . . . . . . . 6

2.1.3 Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.4 Quelque rappels sur le matrices carrées réelles . . . . . . . . . . . . 11

2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.1 Fonctions convexes, strictement convexes, fortement convexes . . . . 11

2.2.2 Exemples des fonctions convexes, strictement convexes et fortement

convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.3 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 Conditions nécéssaires et suffisantes de minimum . . . . . . . . . . . . . . 17

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

3 Optimisation sans contraintes 23

3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

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

3.1.2 Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 27

3.2 Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

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

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

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

3.3.1 Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.2 Cas d"une fonctionJquelconque . . . . . . . . . . . . . . . . . . . 38

4 Optimisation avec contraintes 39

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

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

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

Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

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

2

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

4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3 Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 53

4.3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.2 Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . 54

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

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

3

Chapitre 1

Introduction

En généraloptimisersignifie le fait de chercher une configuration optimale d"un sys-

tème, c"est à dire, chercher la meilleure configuration parmi tous les configurations possibles

du système et ceci, par rapport à un critère donné. Pour décrire (et éventuellement résoudre) un problème d"optimisation nous utilisons la modélisation mathématique. La démarche de modélisation comporte 3 étapes : Etape 1.Choisir lesvariables de décision, qui sont les composantes du système sur lesquelles on peut agir. On supposera dans ce cours qu"il y a un nombre finit notén2IN

de variables de décision, chacune de ces variables étant un nombre réel. Alors les variables

de décision seront représentés par un vecteurx= (x1;x2;xn)T2IRn(vecteur colonne). Etape 2.Décrirel"étatdu système, étant donnée une configuration des variables de décision. Ceci revient mathématiquement à se donner une fonctionJ:IRn!IRqui s"appellefonction objectifoufonction coûtet que nous voulons rendre la plus petite possible ou la plus grande possible. Etape 3.Décrire lescontraintesque les variables de décision satisfont. Ceci revient à définir un ensemble de contraintesUIRnet imposer d"avoirx2U. Pour résumer on peut dire que pour décrire un problème 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:

Motivation et exemples pratiques :en classe

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)

(ij=symboles deKronecker).

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

est donné par < x;y >=nX i=1x iyi: Deux vecteursx;y2IRnsontorthogonaux(on noterax?y) si< x;y >= 0.

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

kxk=p< x;x >=v uutn X i=1x 2i: Rappellons lespropriétés d"une norme(donc aussi de la norme euclidienne) : i)kxk=jjkxk 82IR;8x2IRn ii)kx+yk kxk+kyk 8x;y2IRn iii)k0k= 0etkxk>0six2IRn f0g. 5

5. Pour tousx2IRnetr >0on notera parB(x;r)laboule ouvertedu centrexet

rayonr, donnée par

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

6. Si x(k) k2INest une suite dansIRnetxest un élément deIRnon dit quex(k) convergeversx(notéex(k)!x) sikx(k)xk !0. Rappellons que nous avons :x(k)!xsi et seulement six(k) i!xienIRoùx(k) i(respectivementxi) est lai-ème composante dex(k)(respectivementx).

7. SoitUIRn.

- On définitl"intérieurdeUcomme l"ensemble des élémentsx2Upour lesquels il exister >0tel queB(x;r)U. - On dit queUestouvertsi8x2U9r >0tel queB(x;r)U. - On dit queUestfermési pour tout suitefx(k)g Utel quex(k)!x2IRnon ax2U.

8. 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 < bon retrouve la notation[a;b]pour l"intervalle des nombres x2IRtels queaxb.

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

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

2.1.2 Quelques rappels sur le calcul différentiel

On considère dans cette partiemetndeux nombres deN(très souvent dans ce cours on auram= 1).

1. SoitUun sous-ensemble deIRnetf:U7!IRm.

On dit quefestcontinueenx2Usif(x(k))!f(x)pour toute suitex(k)U telle quex(k)!x. On dit quefest continue surUsifest continue en tout pointx2U. Remarque :Sif= (f1;f2;fm)avecf1;f2;fm:U!IRalorsfest continu enx2Usi et seulement sif1;f2;fmsont continues enx.

Pour tous les poins suivants on va supposer que

est un ouvert de IRnetfest une fonctionf: !IRm. 6

2. Pour toutx2

eth2IRnon note (quand9) @f@h (x) = limt7!01t [f(x+th)f(x)] (c"est ladérivée directionnelledefenxdans la directionh).

Remarques :

i)@f@0(x) = 0: ii)Sif= (f1;f2;fn)T2IRnavecf1;f2;fm: !IRalors @f@h (x) =@f1@h (x);@f2@h (x);@fm@h (x) T

3. Pour toutx2

et touti2 f1;2;;ngon note (quand9) @f@x i(x) =@f@e i(x) = limt7!01t [f(x+tei)f(x)] (c"est ladérivée partielledefenxpar rapport à la variablexi.)

En particulier, sin= 1on notef0(x) =@f@x

1(x) = limt!01t

[f(x+t)f(x)] = lim y!x1yx[f(y)f(x)]

4. Pour toutx2

on note (quand9)Jf(x) =lamatrice Jacobiennedefenxqui est un élément deMm;n(IR)définie par (Jf(x))ij=@fi@x j(x)2IR8i= 1;m;8j= 1;n: Legradientdefenxest défini comme la transposée de la matrice Jacoblenne de fenx: rf(x) = (Jf(x))T2 Mn;m(IR): Remarque importante :Dans le cas particulierm= 1(doncf: !IR) alors en considérant tout élément deMn;1comme un vector colonne deIRn, on va dire que rf(x)est le vecteur colonne rf(x) =@f@x 1@f@x

2;@f@x

n T 2IRn:

Rappellons la formule :

@f@h (x) =8x2

8h2IRn:

5. Sif:

!IR(icim= 1) on dit qu"un pointx2 est unpoint critiquepour la fonctionfsirf(x) = 0. 7

6. Pour toutx2

eti;j2 f1;2;ngon note (quand9) 2f@x i@xj(x) =@@x i @f@x j (x)2IRm dérivée partielle à l"ordre 2.

Notation :pouri=jon écrira@2f@

2xi(x)à la place de@2f@x

i@xi(x).

7. Dans le casm= 1on note pour toutx2

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

8. On dit quefest de classeCpsur

(on noteraf2Cp( )) pourp= 1oup= 2 si les dérivées partielles desfjusqu"à l"ordrepexistent et sont continues sur . Par extension on dit quefest de classeC0sur sifest continue sur

9. On a le Théorème de Schwarz : sif2C2(

)alors 2f@x i@xj(x) =@2f@x j@xi(x)8x2 ;8i;j= 1;n (c"est à dire, la matricer2f(x)est symmétrique).

10. (Lien entrer;Jfetr2) : Sif:

!IRest de classeC2alors r

2f(x) =Jrf(x) =rJf(x)8x2

(la matrice Hessienne defest le Jacobien du gradient defou le gradient de la

Jacobienne def).

11. (Composition) Soient

IRn; UIRmavec

;Uouvertsf: !IRm; g:U! IR pavecp2INetf( )U. Considérons la fonction composéegf: !IRp. i)Sifetgsont continues alorsgfest continue. ii)Sifetgsont de classeC1alorsgfest de classeC1et on a l"égalité matricielle J gf(x) =Jg(f(x))Jf(x)8x2

Conséquences :

i)Sim=p= 1alors r(gf)(x) =g0(f(x))rf(x): i)Sin=p= 1alors (gf)0(x) = : 8

Proposition 2.1.Nous avons

r

2f(x)h=r8x2

;8h2IRn:

où le premier gradient dans le membre de droite de l"égalité est considéré par rapport à la

variablex.

Démonstration.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 importants :

1. Sif:IRn!IRmest une fonctionconstantealorsrf= 0etJf= 0. On a aussi

évidementr2f= 0dans le casm= 1.

2. Soitf:IRn!IRmdéfinie par

f(x) =Ax8x2IRn oùA2 Mm;n(IR)est une matrice donné (c"est à dire,fest une fonctionlinéaire).

Il est facile de voir qu"on a

J f(x) =A8x2IRn (la matrice Jacobienne est constante). Dans la cas particulierm= 1une fonction linéaire générale peut être écrite sous la forme f(x) =< a; x >8x2IRn oùa2IRnest un vecteur donné. Il est clair alors que rf=a et 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 laforme 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 9 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:

En utilisant la formuler2f=Jrfon déduit

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:

2.1.3 Rappel formules de Taylor

Proposition 2.2.(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). 10

2.1.4 Quelque rappels sur le matrices carrées réelles

Soitn2INetA2 Mn(IR)une matrice carrée réelle.

1. SoitC=l"ensemble des nombres complexes. On rappelle que2Cest unevaleur

propredeAs"il existex2Cnavecx6= 0tel queAx=x; on appellexvecteur propredeAassocié à la valeur propre.

2. On dit que la matriceAestsemi-définie positivesi< Ax;x >0;8x2IRn.

On dit queAestdéfinie positivesi< Ax;x > >0;8x2IRnavecx6= 0.

3. Rappellons que siAest symétrique alors toutes les valeurs propres deAsont réelles;

en plus il existenvecteurs propres deAappartenant àIRnformant une base ortho- normée enIRn.

4. Supposons que la matriceAest symétrique. Alors

< Ah; h >minkhk2;8h2IRn 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.

5. Supposons queAest symétrique. AlorsAest semi-définie positive si et seulement si

min0etAest définie positive si et seulement simin>0.

6.Abréviation :La notation SDP pour une matrice carrée rélle signifie "matrice sy-

métrique et définie positive" (elle ne signifie pas "matrice semi-définie positive" !).

2.2 Convexité

2.2.1 Fonctions convexes, strictement convexes, fortement convexes

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

1. On dit quefestconvexesurUsi

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

2. On dit quefeststrictement convexesurUsi

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

3. On dit quefestfortement convexesurUs"il existe >0tel que

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

4. On dit quefestconcave(respectivementstrictement concave, respectivement

fortement concave) sifest convexe (respectivement strictement convexe, res- pectivement fortement convexe). Remarque :Il est facile de voir qu"on a : fortement convexe=)strictement convexe =)convexe. Les réciproques ne sont pas vraies 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) donc elle n"est pas fortement convexe (ni fortement concave).

On a le résultat utile suivant :

Proposition 2.5.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 :

1. La fonctionfest convexe (donc toute combinaison linéaire avec des coefficients stric-

tement positifs de fonctions convexes est convexe).

2. Si au moins l"une des fonctionsf1;;fpest strictement convexe alorsfest stric-

tement convexe.

3. Si au moins l"une des fonctionsf1;;fpest fortement convexe alorsfest fortement

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!) Les propositions suivantes

donnent des critères de convexité, convexité stricte et convexité forte, plus faciles à utiliser

que les définitions respectives. Proposition 2.6.(caractérisation de la convexité) Soit

IRnouvert,U

avecUconvexe etf:

7!IR une fonction de classeC1.

Alors a)Les 3 propositions suivantes sont équivalentes :

1.fest convexe surU

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

3.rfestmonotone surU, c"est à dire

08x;y2U: b)Si de plusfest de classeC2sur alorsfest convexe surUsi et seulement si 0;8x;y2U(2.2) 12 Démonstration.a)On montre ici l"équivalence entre 1), 2) et 3).

1) =)2) :Supposonsfconvexe; la définition de la convexité peut s"écrire

f(x+t(yx))f(x)t[f(y)f(x)] En fixantx;yen divisant partet en faisantttendre vers 0 (ce qui est possible cart2[0;1]) on obtient 2).

2) =)3) :De 2) on déduit

f(y)f(x)+;8x;y2U et aussi (en inversantxety) : f(x)f(y)+;8x;y2U En faisant la somme de ces 2 inégalités on obtient 3).

3) =)1) :Soientx;y2Ufixés. On introduit la fonctiong:I!IRdéfinie par

t2I!g(t) =f(ty+ (1t)x)2IR oùIest un intervalle ouvert qui contient[0;1]. Il est facile de voir quegest de classeC1 et on a g

0(t) =8t2I:

Soientt1;t22[0;1]avect1< t2. Alors

g

0(t2)g0(t1) ==

1t 2t1: Par hypothèse 3) le dernier term de l"égalité précédente est0, ce qui montre que la fonctiong0est une fonction croissante. On déduit alors quegest une fonction convexe sur [0;1], ce qui nous donne pour toutt2[0;1] : g(t1 + (1t)0)tg(1) + (1t)g(0) c"est à dire f(ty+ (1t)x)tf(y) + (1t)f(x) doncfest convexe. b)On suppose icif2C2( "=)" Supposons quefest convexe et montrons (2.2). Soith2IRnfixé et notons g:

7!IRla fonction donnée parg(x) =;8x2

. Nous avons en utilisant aussi la Proposition 2.1 : ==@g@h (x) = limt7!0t 13 ce qui nous donne = limt7!0t 2: Considérons maintenantx;y2Uarbitraires eth=yx. Commex+t(yx)2U8t2

[0;1], de l"égalité précédente on déduit à l"aide de la monotonie derfque

0, c"est à dire (2.2).

"(=" Supposons maintenant que (2.2) est satisfaite et montrons quefest convexe. Soient x;y2Ufixées arbitraires, et considérons la fonctiong1:

7!IRdonnée par

g

1(z) =8z2

. 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.2) : =0:

Ceci nous donne la monotonie derfdonc la convexité def.Proposition 2.7.(caractérisation de la convexité stricte)

Soit

IRnouvert,U

avecUconvexe etf:

7!IR une fonction de classeC1.

Alors a)Les 3 propositions suivantes sont équivalentes :

1.fest strictement convexe surU

2. f(y)> f(x)+;8x;y2Uavecx6=y

3.rfeststrictement monotone surU, c"est à dire

>08x;y2Uavecx6=y:quotesdbs_dbs31.pdfusesText_37

[PDF] condition de germination des graines 6eme

[PDF] pour germer une graine a besoin

[PDF] tp de germination des graines pdf

[PDF] conditions germination graines pdf

[PDF] la germination des graines cours pdf

[PDF] les étapes de la germination pdf

[PDF] tp germination graines 6ème

[PDF] conditions de germination d'une graine de haricot

[PDF] définition du travail selon karl marx

[PDF] le travail selon hegel

[PDF] qu'est ce que le travail en philosophie

[PDF] le travail selon kant

[PDF] condition de l homme moderne fiche de lecture

[PDF] condition de l homme moderne epub

[PDF] réaction de précipitation exercices corrigés pdf