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

View - Download [PDF] 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

quotesdbs_dbs2.pdfusesText_2

[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

[PDF] programme daeu a

[PDF] cours physique daeu b pdf

[PDF] cours chimie daeu b

[PDF] la révolution et l'empire 4ème 2016

[PDF] cours de svt 6ème pdf