[PDF] Résumé dOptimisation Résumé d'Optimisation. MI5

View - Download Résumé dOptimisation

Previous PDF

Next PDF

Resume d'Optimisation

MI5 Master Pro 1ere annee

Jean-Pol Guillement

Departement de Mathematiques

Nantes 2010/2011

2

Table des matieres

Introduction5

1 Rappels7

1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Condition d'ordre 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.1Equation d'Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Conditions d'ordre 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.1 Condition de Legendre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.2 Condition susante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Extrema lies, multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Programmation lineaire 9

2.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Probleme sous forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Caracterisation des sommets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4 Methode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Programmation en dimension 1 11

3.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.2 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3 Interpolation quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.4 Methode par decoupage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Prise en compte de la convexite 13

4.1 Condition necessaire de minimum sur un convexe . . . . . . . . . . . . . . . . . . . . . 13

4.2 Caracterisation des fonctions convexes derivables . . . . . . . . . . . . . . . . . . . . . 13

4.3 Minimum des fonctions convexes sur un convexe . . . . . . . . . . . . . . . . . . . . . 13

4.4 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.5 Notation : probleme (P) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.6 Existence de minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.7 Fonctionnelles elliptiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.8 Caracterisation des fonctionnelles elliptiques . . . . . . . . . . . . . . . . . . . . . . . . 14

4.9 Minimum des fonctions elliptiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.10 Fonctionnelles quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.11 Resolution des systemes lineaires au sens des moindres carres . . . . . . . . . . . . . . 15

4.12 Projection sur un convexe ferme non vide . . . . . . . . . . . . . . . . . . . . . . . . . 15

5 Optimisation sans contrainte 17

5.1 Methodes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5.1.1 Methode de la relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5.1.2 Methode de la plus profonde descente (methode du gradient) . . . . . . . . . . 17

5.2 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5.3 Methode de la metrique variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5.4 Methode du gradient conjugue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5.4.1 Cas des fonctionnelles quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . 19

5.4.2 Cas des fonctionnelles non quadratiques . . . . . . . . . . . . . . . . . . . . . . 19

4TABLE DES MATIERES6 Optimisation avec contraintes 21

6.1 Relations de Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6.1.1 Cas des contraintes non convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6.1.2 Cas des contraintes convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6.2 Interpretation des relations de Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . 22

6.3 Point-selles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.4 Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.5 Point-selle du Lagrangien et solution du probleme (P) . . . . . . . . . . . . . . . . . . 23

6.6 Probleme dual du probleme (P) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.7 Methode d'Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.7.1 Demarche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.7.2 Calcul dek+1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.7.3 Calcul derGk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6.7.4 Condition susante de convergence de la methode d'Uzawa . . . . . . . . . . . 24

Bibliographie24

Introduction

Ceci un resume des principaux resultats du cours d'optimisation. Il est autorise aux contr^oles.

6Introduction

Chapitre 1

Rappels

1.1 Notations

Sifest une fonction reguliere deE=Rn!R, on note sa derivee enx0parf0x

0ouf0(x0)(2 L(E;R)),

sa derivee seconde enx0parf00x

0ouf00(x0)(2 B(E;R)), son gradient enx0parrfx0ourf(x0)(2E),

sa matrice hessienne parr2fx0. La matrice Hessienne peut ^etre vue comme une matrice symetrique nn, comme un operateur lineaire deEdansEou comme une forme bilineaire symetrique surE.

1.2 Formules de Taylor

([3, p.151-146]) Les formules de Taylor dierent selon l'ordre, l'ecriture du reste, l'utilisation des derivees ou du gradient et de la matrice Hessienne. En voici deux exemples :

Sifest deux fois derivable on a :

f(x0+h) =f(x0) +f0(x0)h+12 f"(x0)(h;h) +"(h)khk2:

Sifest de classeC2on a :

f(x0+h) =f(x0) +ht:rfx0+12 ht:r2fx0:h+Z 1 0 (1t)ht:r2f(x0+th):h dt

1.3 Condition d'ordre 1

1.3.1

Equation d'Euler

([3, p.146]) Soit un ouvert deEet soitf: !R:Sifadmet un extremum local enx2 et sifest derivable enxalors (equation d'Euler) f

0(x) = 0

1.4 Conditions d'ordre 2

1.4.1 Condition de Legendre

([3, p.152]) Soit un ouvert deEet soitf: !R. Sifadmet un minimum local enx2 et sifest deux fois derivable enxalors (condition de Legendre) f"(x) est une forme bilineaire symetrique positive.

8Rappels1.4.2 Condition susante

([3, p.152]) Soit un ouvert deEet soitf= !R. Sifest deux fois derivable sur , sif0(x) = 0 et sif"(x) est positive dans un voisinage dex2 , alorsfa un minimum local enx:

1.5 Extrema lies, multiplicateurs de Lagrange

([3, p.148]) Soit un ouvert deE, soitf: !R, soient'i: !R;i= 1;::;m:

On suppose que les'i2 C1(

Soitx2K=fx2

;'i(x) = 0;i= 1:::mgtel que les derivees'0i(x) soient lineairement independantes (dansL(E;R)) et tel quefsoit derivable enx. Alors sifadmet un extremum local relativement aKenx, il existe1;:::;muniques (multiplicateurs de Lagrange) tels que rf(x) +1r'1(x) +:::+mr'm(x) = 0

Chapitre 2

Programmation lineaire

Pas enseigne cette annee. (Voir [3], [5], [7], [9]).

2.1 Generalites

2.2 Probleme sous forme standard

2.3 Caracterisation des sommets

2.4 Methode du simplexe

10Programmation lineaire

Chapitre 3

Programmation en dimension 1

3.1 Generalites

3.2 Methode de Newton

3.3 Interpolation quadratique

3.4 Methode par decoupage

12 Programmation en dimension 1

Chapitre 4

Prise en compte de la convexite

4.1 Condition necessaire de minimum sur un convexe

([3, p.153])

SoitKun convexe dans

ouvert deE. Soitf: !R: Sifadmet un minimum relativement aKenx, et sifest derivable enxalors (Inequation d'Euler) f

0(x)(xx)08x2K

4.2 Caracterisation des fonctions convexes derivables

([3, p.154-155]))

SoitKun convexe dans

ouvert deE. Soitf: !Rderivable sur

1.fest convexe surKsi et seulement si

f(x)f(x0) +f0(x0)(xx0)8x;x02K

2.fest strictement convexe surKsi et seulement si

f(x)> f(x0) +f0(x0)(xx0)8x;x02K; x6=x0

3. On suppose quefest deux fois derivable dans

. Alorsfest convexe surKsi et seulement si f"(x)(yx;yx)0;8x;y2K

4. On suppose quefest deux fois derivable dans

. Si f"(x)(yx;yx)>0;8x;y2K;x6=y alorsfest strictement convexe surK.

4.3 Minimum des fonctions convexes sur un convexe

([3, p.156-175])

SoitKun convexe dans

ouvert deE, soitf: !Rconvexe surK.

1. Sifadmet un minimum local enx2K, relativement aK, ce minimum est un minimum global.

2. Sifest strictement convexe surK;fadmet au plus un minimum local relativement aK(qui

est aussi un minimum strict et global)

3. Sifest derivable enx2K, alorsfadmet un minimum par rapport aKenxsi et seulement

si (Inequation d'Euler) f

0(x)(xx)08x2K

ou, en terme de gradient (rfx;xx)0;8x2K:

14 Prise en compte de la convexite

4. SiKest un sous espace vectoriel l'inequation d'Euler est equivalente a

f

0(x)(x) = 0;8x2K:

ou, en terme de gradient rfx?K

5. SiKest ouvert, l'inequation d'Euler est equivalente a la condition d'Euler

f

0(x) = 0

4.4 Fonctions coercives

([3, p.175])

Une fonctionf:E!R, est dite coercivesi lim

kxk!1f(x) = +1

4.5 Notation : probleme(P)

Dans la suite, quand on parle du probleme (P), il s'agit de la recherche dextel que (P)(f(x) = infx2KEf(x) x 2K

4.6 Existence de minimum

([3, p. 175])

1. SiKest un ferme borne non vide deE, sifest continue alors le probleme (P) a au moins une

solution.

2. SiKest ferme non borne deE, sifest continue et coercive, alors le probleme (P) a au moins

une solution.

3. SiKest un convexe ferme non vide deE, sifest continue, coercive, strictement convexe sur

K, alors le probleme (P) a une solution et une seule.

4.7 Fonctionnelles elliptiques

([3, p. 183]) Une fonctionf:E!R, de classeC1est dite elliptiques'il existe >0 tel que (rfx rfy;xy)kxyk28x;y2E

4.8 Caracterisation des fonctionnelles elliptiques

Une fonctionf:E!R, deux fois derivable, est elliptique si et seulement si il existe >0 tel que (r2fx0x;x)kxk2;8x;x02E

4.9 Minimum des fonctions elliptiques

SoitKest un convexe ferme non vide deEetf:E!Relliptique.quotesdbs_dbs6.pdfusesText_11

[PDF] cours optimisation pdf

[PDF] cours optique géométrique mpsi

[PDF] cours optique géométrique smpc s2 pdf

[PDF] cours optique ondulatoire prépa

[PDF] cours organisation des entreprises pdf

[PDF] cours outils mathématiques

[PDF] cours outlook 2010 pdf

[PDF] cours paces ue3 pdf

[PDF] cours paie pdf

[PDF] cours pc 4eme pdf

[PDF] cours pdf économie de la construction

[PDF] cours permanente cap coiffure

[PDF] cours permanente coiffure

[PDF] cours pharmacologie 3eme annee medecine

[PDF] cours philosophie terminal e