[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 maroc
[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
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
COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin