[PDF] Cours doptimisation ENSAI Rennes





Previous PDF Next PDF



DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- Optimisation

Fonction quadratique = polynôme de degré 2 Fonctions quadratiques à une variable ... Une fonction f définie sur S convexe est convexe si pour toute.



Convexité en optimisation convexité forte

fonction convexe définie sur ? ? V est différentiable presque partout (au sens de la mesure Exemple 3 Convexité d'une fonction quadratique.



COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

2.2.2 Exemples des fonctions convexes strictement convexes et fortement convexes . 3.1.2 Cas particulier des fonctions quadratiques .



Résolution dun problème quadratique non convexe avec

24 mai 2018 2.2.3 Cas des fonctions convexes : conditions nécessaires et suffi- ... matrice Hessienne d'une fonction quadratique est indépendante du ...



MAT 2410: Optimisation

Soit A une matrice symétrique définie-positive de format n × n. Proposition: La fonction quadratique f (x)=(Ax x) est strictement convexe. Preuve: Posons x2.



La programmation quadratique en variables entières

f : Rn ? R deux fois différentiable dans Rn et soit u un minimum local de f



Optimisation en nombres entiers de fonctions quadratiques non

o`u la fonction objectif est soit linéaire soit quadratique et convexe. Nous aborderons donc différentes méthodes de résolution de cette catégorie de.



THESE Reformulations quadratiques convexes pour la

reformulation de ce programme par un programme quadratique en variables. 0-1 dont la fonction objectif est convexe les contraintes restant linéaires.



Optimisation quadratique

1.4.2 Propriété des fonctions convexes. Théorème : Soit J une fonctionnelle différentiable sur un sous-ensemble K convexe non vide.



Cours doptimisation ENSAI Rennes

15 mars 2019 1.4.3 Propriétés d'une fonction convexe . ... 6.6 Fonction quadratique et contraintes linéaires d'égalité . . . . . 40.

Cours d'optimisation

ENSAI Rennes

Jocelyne Erhel

15 mars 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

quotesdbs_dbs1.pdfusesText_1
[PDF] fonction racine carrée exercices corrigés

[PDF] fonction ressources humaines dans l'entreprise

[PDF] fonction ressources humaines définition

[PDF] fonction ressources humaines pdf

[PDF] fonction statistique excel

[PDF] fonction variable complexe exercices corrigés

[PDF] fonction varoma thermomix tm5

[PDF] fonction word 2010

[PDF] fonctionnement boite de vitesse automatique pdf

[PDF] fonctionnement clé token

[PDF] fonctionnement d internet schéma

[PDF] fonctionnement d'un groupe electrogene pdf

[PDF] fonctionnement d'un hacheur

[PDF] fonctionnement d'un sprinkler

[PDF] fonctionnement d'une banque pdf