[PDF] Cours doptimisation ENSAI Rennes

View - Download Cours doptimisation ENSAI Rennes

Previous PDF

Next PDF

Cours d'optimisation

ENSAI Rennes

Jocelyne Erhel

11 decembre 2019

Table des matieres

1 Problemes d'optimisation 4

1.1 Un peu de topologie . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.1 Ouvert et ferme . . . . . . . . . . . . . . . . . . . . . .

4

1.1.2 Fonction continue a plusieurs variables . . . . . . . . .

5

1.2 Minimum local ou global . . . . . . . . . . . . . . . . . . . . .

6

1.2.1 Contraintes d'egalite et d'inegalite . . . . . . . . . . . .

6

1.3 Condition susante d'existence . . . . . . . . . . . . . . . . .

8

1.4 Optimisation convexe . . . . . . . . . . . . . . . . . . . . . . .

9

1.4.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . .

9

1.4.2 Fonction convexe . . . . . . . . . . . . . . . . . . . . .

9

1.4.3 Proprietes d'une fonction convexe . . . . . . . . . . . .

1 0

2 Fonctions a une variable 11

2.1 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1

2.2 Convexite et derivabilite . . . . . . . . . . . . . . . . . . . . .

12

2.3 Minimisation sans contrainte . . . . . . . . . . . . . . . . . . .

1 3

2.3.1 Conditions d'optimalite d'ordre 1 . . . . . . . . . . . .

1 3

2.3.2 Conditions d'optimalite d'ordre 2 . . . . . . . . . . . .

1 4

3 Algebre lineaire 16

3.1 Vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 6

3.1.1 Formes lineaires . . . . . . . . . . . . . . . . . . . . . .

1 6

3.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.2.1 Applications lineaires . . . . . . . . . . . . . . . . . . .

1 8

3.2.2 Formes quadratiques . . . . . . . . . . . . . . . . . . .

18

3.3 Matrices symetriques . . . . . . . . . . . . . . . . . . . . . . .

1 9

3.3.1 Matrices symetriques denies ou semi-denies . . . . .

1 9 1

Optimisation J. Erhel

4 Calcul dierentiel 22

4.1 Fonctions de classeC1. . . . . . . . . . . . . . . . . . . . . .22

4.2 Fonctions de classeC2. . . . . . . . . . . . . . . . . . . . . .23

4.2.1 Forme lineaire et forme quadratique . . . . . . . . . . .

2 4

4.3 Fonction vectorielle de classeC1. . . . . . . . . . . . . . . . .25

4.3.1 Application lineaire . . . . . . . . . . . . . . . . . . . .

26

4.4 Convexite et dierentiation . . . . . . . . . . . . . . . . . . . .

27

4.4.1 Forme quadratique convexe . . . . . . . . . . . . . . .

2 8

5 Optimisation sans contrainte 29

5.1 Condition d'optimalite d'ordre 1 . . . . . . . . . . . . . . . . .

29

5.1.1 Forme lineaire . . . . . . . . . . . . . . . . . . . . . . .

3 0

5.1.2 Forme quadratique . . . . . . . . . . . . . . . . . . . .

3 0

5.2 Condition d'optimalite d'ordre 2 . . . . . . . . . . . . . . . . .

31

5.2.1 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.3 Point selle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3

6 Optimisation avec contraintes d'egalite 35

6.1 Condition de Qualication des contraintes CQC . . . . . . . .

3 5

6.2 Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 6

6.3 Condition d'optimalite d'ordre 1 . . . . . . . . . . . . . . . . .

37

6.4 Condition d'optimalite d'ordre 2 . . . . . . . . . . . . . . . . .

39

6.5 Sensibilite d'une contrainte . . . . . . . . . . . . . . . . . . . .

3 9

6.6 Fonction quadratique et contraintes lineaires d'egalite . . . . .

4 0

7 Optimisation avec contraintes d'inegalite 42

7.1 Condition de Qualication des contraintes CQC . . . . . . . .

4 2

7.2 Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 3

7.3 Condition d'optimalite d'ordre 1 . . . . . . . . . . . . . . . . .

43

7.4 Point selle du Lagrangien . . . . . . . . . . . . . . . . . . . . .

4 5

7.4.1 Optimisation convexe . . . . . . . . . . . . . . . . . . .

4 6

7.4.2 Dualite . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 6

8 Optimisation avec contraintes mixtes d'egalite et d'inegalite 48

8.1 Condition de Qualication des contraintes CQC . . . . . . . .

4 8

8.2 Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 9

8.3 Condition d'optimalite d'ordre 1 . . . . . . . . . . . . . . . . .

50
2

Optimisation J. Erhel

9 Methodes numeriques 51

9.1 Methodes iteratives . . . . . . . . . . . . . . . . . . . . . . . .

51

9.1.1 Criteres d'arr^et . . . . . . . . . . . . . . . . . . . . . .

51

9.1.2 Direction de descente . . . . . . . . . . . . . . . . . . .

5 2

9.2 Methode de gradient . . . . . . . . . . . . . . . . . . . . . . .

52

9.2.1 Methode de gradient a pas xe . . . . . . . . . . . . .

53

9.2.2 Methode de gradient a pas variable . . . . . . . . . . .

53

9.2.3 Recherche lineaire . . . . . . . . . . . . . . . . . . . . .

54

9.3 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . .

5 4

9.3.1 Approximation defa l'ordre 2 . . . . . . . . . . . . .56

9.3.2 Convergence globale . . . . . . . . . . . . . . . . . . .

56

9.3.3 Algorithme de quasi-Newton . . . . . . . . . . . . . . .

5 7

9.3.4 Algorithme de Newton inexact . . . . . . . . . . . . . .

57

9.3.5 Minimisation avec contraintes d'egalite . . . . . . . . .

5 8

10 Bibliographie 59

3

Chapitre 1

Problemes d'optimisation

1.1 Un peu de topologie

Soitnun entier non nul. L'ensembleRnest un espace vectoriel norme de dimensionn. Un vecteurxdeRnancoordonnees et est note x=0 B B@x 1 x 2 x n1 C

CA= (xi)1in:

Le produit scalaire de deux vecteursxetyest un scalaire deni par < x;y >=nX i=1x iyi:

La norme euclidienne du vecteurxest denie par

kxk2=< x;x >=nX i=1x 2i:

1.1.1 Ouvert et ferme

Une boule ouverte de centrexet de rayonr >0 est denie par

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

4

Optimisation J. Erhel

Une boule fermee de centrexet de rayonr >0 est denie parB(x;r) =fy2Rn;kyxk rg:

Un ouvert non vide

deRnest tel que 8x2 ;9r >0;B(x;r) Un fermeKdeRnest tel que son ensemble complementaire est un ouvert. L'ensembleRnest a la fois ouvert et ferme, ainsi que l'ensemble vide. Les intervalles ouverts deRsont des ensembles ouverts, les intervalles fermes deRsont des ensembles fermes.

Exemple 1.1.1.

K

1=fx2Rn;xi>0;i= 1;;ng:

L'ensembleK1est un ouvert deRn.

K

2=fx2Rn;xi0;i= 1;;ng:

L'ensembleK2est un ferme deRn.

dessins en cours

1.1.2 Fonction continue a plusieurs variables

Soit un ouvert deRnetfune fonction scalaire a plusieurs variables de dansR. On notef(x) ouf(x1;x2;:::;xn) la valeur defenx.

La fonctionfest continue enxsi et seulement si

lim kyk!0f(x+y) =f(x): SoitFune fonction vectorielle a plusieurs variables de dansRp. On noteF(x) = (Fi(x))1iple vecteur valeur deFenx, ouFiest une fonction scalaire a plusieurs variables. La fonctionFest continue enxsi et seulement siFiest continue pour touti= 1;:::;p. 5

Optimisation J. Erhel

1.2 Minimum local ou global

Soit un ouvert deRnetfune fonction scalaire a plusieurs variables de dansR. SoitKun sous-ensemble non vide de . Un probleme de minimisation consiste a trouver un pointxdansKtel que la valeurf(x) soit minimale dansK. L'ensembleKest appele ensemble admissible et la fonctionfest l'objectif ou le co^ut. Denition 1.2.1.Le pointx2Kest un point de minimum global dansK, et la valeurf(x)est le minimum global defdansK, si et seulement si

8x2K;f(x)f(x):

Denition 1.2.2.Le pointx2Kest un point de minimum local dansK, et la valeurf(x)est un minimum local defdansKsi et seulement s'il existe une boule ouverteB(x;r)telle que

8x2B\K;f(x)f(x):

Dans ce cours, on s'interesse au probleme de minimisation : min x2Kf(x) (1.1) Un probleme de minimisation, local ou global, peut n'avoir aucune solu- tion, une solution unique, plusieurs solutions. S'il existe un point de minimum global, sa valeur est unique. Par contre, il peut y avoir plusieurs valeurs de minima locaux. Si la fonctiongadmet un maximum local enx, alors la fonctionf=g admet un minimum local enx. Donc la recherche d'un maximum peut se faire en cherchant le minimum de la fonction opposee. Dans la suite du cours, on etudie l'existence et l'unicite de solutions. Le cas convexe est important car les resultats sont plus nombreux. On etudie ensuite les conditions necessaires d'existence dans le cas die- rentiable. Celles-ci permettent de construire des algorithmes de calcul. dessins en cours

1.2.1 Contraintes d'egalite et d'inegalite

SiK= , il s'agit d'un probleme d'optimisation sans contrainte. L'en- semble admissible est donc un ouvert. 6

Optimisation J. Erhel

Sinon, l'ensembleKrepresente des contraintes. Dans ce cours, on consi- dere des contraintes d'egalite ou d'inegalite large.

Soitgi;i= 1;:::;petqj;j= 1;:::;mdes fonctions de

dansR. Les contraintes d'egalite sont denies pargi(x) = 0;i= 1;:::;pet les contraintes d'inegalite parqj(x)0;i= 1;:::;m. Denition 1.2.3.L'ensemble admissible pour les contraintes d'egalite et d'inegalite, noteK, est l'ensemble des points qui respectent les contraintes : K=fx2 ;gi(x) = 0;i= 1;:::;p;qj(x)0;i= 1;:::;mg: Siqj(x) = 0, la contraintejest active enx. Sinon, elle est inactive. Dans ce cours, les contraintes seront en general des fonctions continues. Lorsquefest denie dans l'espace entier, l'ensemble admissible avec des contraintes d'egalite ou d'inegalite continues est un ferme.

Theoreme 1.2.1.Si

=Rn, siKest non vide et si les fonctionsgietqj sont continues, alorsKest un ensemble ferme. Voici quelques exemples d'ensembles admissibles avec des contraintes conti- nues.

Exemple 1.2.1.

K=fx2Rn;kxak rg:

L'ensemble admissible est une boule fermee et bornee, il y a une contrainte d'inegalite :q(x) =kxak r:

Exemple 1.2.2.

K=fx2Rn;bTx= 0g;

oub2Rn. L'ensemble admissible est un hyperplan ferme non borne, il y a une contrainte d'egalite :g(x) =bTx:

Exemple 1.2.3.

K=fx2Rn;xi0;i= 1;:::;ng:

L'ensemble admissible est un ferme non borne, il y ancontraintes d'inegalite q i(x) =xi:il y ancontraintes d'inegalite :qi(x) =xi: 7

Optimisation J. Erhel

1.3 Condition susante d'existence

Dans le cas d'un probleme d'optimisation avec contraintes (plus precise- mentKferme), il existe une solution sous certaines hypotheses sur l'ensemble admissible ou la fonction co^ut. Theoreme 1.3.1.SiKest non vide, ferme et borne, et sifest continue, alors il existe au moins un point de minimum global dansK, et aussi un point de maximum global.

Exemple 1.3.1.

K=fx2Rn;kxk 1g:

L'ensemble admissible est une boule fermee, donc est non vide, ferme et borne. f(x) =kxk2: La fonctionfest continue, donc il existe un point de minimum global. On peut le verier directement. En eet8x2K; f(x) 1et8x2 K;kxk= 1)f(x) =1. Donc tous les points de la sphere sont des points de minimum global. dessin en cours Denition 1.3.1.Soitfune fonction denie dans un ensembleKnon borne. Elle est coercive si et seulement si lim kxk!1f(x) = +1 Theoreme 1.3.2.SiKest non vide, ferme et non borne, et sifest continue et coercive dansK, alors il existe au moins un point de minimum global dans K. Exemple 1.3.2.L'ensemble admissible estK=Rnetf(x) =kxk2:L'en- sembleKest non vide, ferme et non borne, la fonctionfest continue et coercive, donc il existe un point de minimum global. On peut le verier directement. En eet8x2Rn;x6= 0; f(x)>0et f(0) = 0. Donc le point0est l'unique point de minimum global. dessin en cours

Exemple 1.3.3.Soitf(x) =Pn

i=1(exibixi)deRndansR, avecbi>0;i=

1;:::;n. Alorsfest continue et coercive, donc il existe au moins un point

de minimum global. 8

Optimisation J. Erhel

Dans la suite du cours, on verra des conditions necessaires d'existence, dans les cas ou existent des "derivees"d'ordre 1 ou 2. C'est de l'optimisation dierentiable.

1.4 Optimisation convexe

Lorsque l'ensemble admissible est convexe et que la fonction est convexe, le probleme d'optimisation est nettement plus simple.

1.4.1 Ensemble convexe

Denition 1.4.1.Un sous-ensembleKdeRnest convexe si et seulement si

8x;y2K;8t2[0;1];tx+ (1t)y2K:

Exemple 1.4.1.Une boule ouverteB(x;r), une boule fermeeB(x;r)sont des ensembles convexes. Il est facile de caracteriser les ensembles convexes dansR. Theoreme 1.4.1.Les sous-ensembles convexes deRsont les intervalles de R. Un paveKdeRnest un produit d'intervalles : soitI1;I2;:::;Indes intervalles deR. Le paveKassocie est deni par Theoreme 1.4.2.Les paves deRnsont des ensembles convexes.

1.4.2 Fonction convexe

Une fonction peut^etre convexe, strictement convexe, ou fortement convexe.

Denition 1.4.2.SoitK

un sous-ensemble convexe de

La fonctionfest convexe dansKsi et seulement si

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

La fonctionfest strictement convexe dansKsi et seulement si

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

9

Optimisation J. Erhel

La fonctionfest fortement convexe dansKsi et seulement s'il existe >0 tel que Toute fonction fortement convexe est strictement convexe et toute fonc- tion strictement convexe est convexe. Une fonction constante dansKest convexe dansKmais n'est pas stric- tement convexe.

La convexite locale est utile en optimisation.

Denition 1.4.3.Soit

un ouvert deRnetfune fonction de dansR etx2 . La fonctionfest localement convexe au voisinage dexsi et seulement sifest convexe dans une boule ouverteB(x;r)incluse dans dessins en cours

1.4.3 Proprietes d'une fonction convexe

En optimisation convexe, il est inutile de distinguer minimum local et minimum global.

Theoreme 1.4.3.SiKest un convexe non vide de

et sifest une fonc- tion convexe dansK, alors tout point de minimum local est aussi point de minimum global dansK. La convexite stricte garantit l'unicite d'une solution.

Theoreme 1.4.4.SiKest un convexe non vide de

etfest une fonction strictement convexe dansK, alors s'il existe un point de minimum dansK, il est unique. La convexite forte garantit l'existence d'une solution lorsque l'ensemble admissible est ferme. Theoreme 1.4.5.SiKest un convexe non vide ferme de etfest une fonction fortement convexe dansK, alors il existe un unique point de mini- mum dansK. dessins en cours 10

Chapitre 2

Fonctions a une variable

Dans ce chapitre, on etudie les problemes d'optimisation pour les fonc- tions a une variable, en utilisant les derivees premiere et seconde. Le cas des fonctions convexes permet d'aner les resultats.

Dans tout le chapitre,

est un intervalle ouvert non vide deRetfest une fonction de dansR.quotesdbs_dbs32.pdfusesText_38

[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