[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.

1.fest strictement convexe, coercive, et verie

f(x)f(x0)(rfx0;xx0) +2 kxx0k28x;x02E

2. Le probleme (P) a une solution et une seule.

4.10 Fonctionnelles quadratiques 15

3.x2Kest solution de (P) si et seulement si

(Inequation d'Euler) (rfx; xx)0;8x2K:

4. On suppose queK=E. Alorsxest solution de (P) si et seulement si

rfx= 0

4.10 Fonctionnelles quadratiques

Ce sont les fonctions de la forme

f(x) =12 (Ax;x)(b;x) +c Aetant un matrice symetrique (operateur deE!E); b2E; c2R.

Elles sont de classeC1;rf=Axb;r2f=A:

Elles sont elliptiques si et seulement si la plus petite valeur propre deAest>0 et dans ce cas, si K=E, le probleme (P) a une solution et une seule, qui est aussi la solution deAx=b:

4.11 Resolution des systemes lineaires au sens des moindres

carres

Mest une matrice amlignes etncolonnes,v2Rm:

Il s'agit de trouverx2Etel quekMxvk2soit minimal, ou encore de resoudre le probleme (P)f(x) = infx2Ef(x) avecf(x) =12 kMxvk212 kvk2: fse met sous la forme d'une fonctionnelle quadratique avecA=MtM;etb=Mtv: Le probleme (P) a au moins une solution. Ses solutions sont caracterisees par (Equations normales) M tMx=Mtv Si le rang deMestn, le probleme (P) a une solution et une seule. La solution peut se calculer par resolution du systeme triangulaire

Rx=PQtv

ouQetRsont les matrices de la decomposition QR de la matriceM,M=QR, etPla projection deRmsurRn f0gmn.

4.12 Projection sur un convexe ferme non vide

SoitKun convexe ferme non vide deE. Soitx2E.

Il existePx2K, unique, tel qued(x;K) =kxPxk:La projectionPxest caracterisee par (xPx;yPx)0;8y2K:

L'applicationx!Pxest contractante

kPxPyk kxyk

16 Prise en compte de la convexite

Chapitre 5

Optimisation sans contrainte

Il s'agit de resoudre numeriquement le probleme (P) (P)(trouverx2E=Rn f(x) = infx2Ef(x) Les algorithmes operent generalement pour des fonctionnelles assez generales, mais la convergence (theorique) n'est assuree que pour des fonctionnelles de classeC1ouC2, convexes ou elliptiques. Les solutions de (P) etant aussi solution derfx= 0, les algorithmes peuvent se voir comme des algorithmes de resolution de cette equation.

5.1 Methodes de descente

Elles sont iteratives. Pour passer deukauk+1, on se donne une direction de descentedket on minimise fle long de cette direction, c'est-a-dire que l'on cherchektel quef(uk+kdk) = inf2Rf(uk+dk):A defaut d'un telkon peut se contenter d'avoirf(uk+kdk)< f(uk).

5.1.1 Methode de la relaxation

([3, p. 185]) On descend de facon cyclique le long de chacun des axes de coordonnees.

La convergence est assuree sifest elliptique.

Note

Sifest une fonctionnelle quadratiquef(x) =12

(Ax;x)(b;x) dont la matriceAest symetrique

denie positive, la methode de la relaxation converge et ses iterations sont identiques a celles de la

methode de Gauss-Seidel pour la resolution de l'equationAx=b:

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

La direction choisie estrfukqui correspond a la direction de plus grande decroissance def:On peut en eet ecrire : f(x)f(x0) = (rfx0;xx0) +"(x)kxx0k et remarquer qu'akxx0kconstant, (rfx0;xx0) est minimal pourxx0=trfx0; t >0:

Description

On part deu0quelconque. Connaissantuk, on calculerfuketuk+1=ukkrfukavecksolution def(ukkrfuk) = inf(ukrfuk). En principe on trouvek>0.

18 Optimisation sans contrainte

Condition susante de convergence

([3, p. 188]) Sif:E!Rest elliptique, la methode de la plus profonde descente est convergente.

Remarque

Cette methode ne peut pas ^etre optimale car le cheminement desukest celui d'une ligne brisee faisant

des angles droits. En eet, deux gradients consecutifs sont orthogonaux caruk+1correspondant au minimum def(ukrfuk);la derivee defdans cette direction s'annule enuk+1. Et donc le gradient defenuk+1lui est orthogonal.

5.2 Methode de Newton

Sifest une fonction reguliere dont on sait calculer le gradient et la matrice hessienne, on peut tirer

partie du fait qu'en un pointuk;fest localement voisine de son developpement de Taylor quadratique, c'est-a-dire que f(uk+d)'f(uk) +dt:rfuk+12 dt:r2fuk:d Si en plus,r2fukest denie positive, l'approximation quadratique a un minimum qui verie r

2fukdk=rfuk

Ceci permet de calculer la direction de descentedket de denir l'iteration par u k+1=uk+dk On demontre, comme pour la methode de Newton pour la resolution des equations'(x) = 0, que si le point de departu0est assez voisin dex, et sir2fest denie positive, alors la methode converge versx, et ceci de facon quadratique.

Sir2fn'est pas denie positive, cette methode supporte certains amenagements (methode de Newton modiee,

[5, p. 106]). Quand le calcul der2fne peut ^etre fait, on peut aussi remplacerr2fukdans l'approximation de Taylor par une matriceHkqui se calcule iterativement (methode de quasi Newton, [5, p. 116])

Remarque

Cette methode est penalisante pour les grands systemes du fait de la necessite de calculerr2f, de la stocker, et de resoudre le systeme r

2fukdk=rfuk

5.3 Methode de la metrique variable

- On peut facilement observer que sif(x) =12 kxk2(b;x), la methode de la plus profonde descente converge en une seule iteration. - Qu'il en est de m^eme sifest la fonctionnelle quadratiquef(x) =12 (Ax;x)(b;x); a la condition de remplacer la metriquekxk2parkjxkj2= ((x;x)) = (Ax;x). - L'idee de la metrique variable, appliquee a une fonctionnelle non necessairement quadratique, consiste lors de chaque iteration de la plus profonde descente a choisir une metrique denie par la matrice hessienne de la fonctionnelle, permettant une acceleration de la convergence. Mais il y a un prix a payer. Le calcul du gradient necessite la connaissance d'une base orthogonale; on peut l'obtenir par exemple par orthogonalisation de Grahm-Schmidt. La methode du gradient conjugue reprend cette idee.

5.4 Methode du gradient conjugue

([3, p. 194][5, p. 144]) Cette methode presente, sur la methode de Newton, l'avantage de ne pas necessiter le calcul der2f,

et sur la methode de la plus profonde descente, celui de denir des directions de descente successives

coherentes.

5.4 Methode du gradient conjugue 19

5.4.1 Cas des fonctionnelles quadratiques

f(x) =12 (Ax;x)(b;x); Aetant symetrique denie positive.

Description generale

On part deu0quelconque. On suppose qu'a l'etapek, on a calculeu1;:::;uktels querful6= 0; l=

0;:::;k. (sinon on a trouve la solution derfx=Axb= 0). On pose

G k= [rfu0;:::;rfuk]: On denituk+1comme le minimum de la restriction defauk+Gk:Ceuk+1existe, est unique. Il se trouve qu'il correspond au minimum defdans une direction calculabledk. Les directionsdksont conjuguees par rapport a la matriceA((Adk;dl) = 0 ). Tout se calcule par des formules iteratives economiques, sans resolution de systeme lineaire. A chaque etape,Gks'accro^t d'une dimension. Au bout d'au plusniterations, la solution est theoriquement trouvee. Numeriquement, avec les erreurs d'arrondi, cela peut ^etre dierent.

Formules d'iterations

On part deu0quelconque. On posed0=rf(u0).

Sid0= 0, c'est termine, on ax=u0.

Sinon on pose

0=(rfu0;d0)(Ad0;d0)

et u

1=u00d0:

De facon generale, siu1;d1;:::;uk;dksont calcules, alors ou bienrf(uk) = 0, et alors c'est termine, x =uk, ou alors on pose :8>>< >:d k=rfuk+krfukk2krfuk1k2dk1 k=(rfuk;dk)(Adk;dk) u k+1=ukkdk

5.4.2 Cas des fonctionnelles non quadratiques

([3, p. 200][5, p. 147]) Le minimum defsur le sous-espaceuk+Gkne peut plus ^etre donne par une formule simple. On calculedkcomme precedemment ou selon une variante (Polak-Ribiere) d k=rfuk+(rfuk;rfuk rfuk1)krfuk1k2dk1 et on obtientken optimisant numeriquement !f(ukdk) La methode ne converge plus en un nombre ni d'iterations.

20 Optimisation sans contrainte

Chapitre 6

Optimisation avec contraintes

La diculte du probleme depend de la nature des contraintes. On peut distinguer : . les variables bornees,ixii . les contraintes anes egalites,Cx=b . les contraintes anes inegalites,Cxb . les contraintes convexes ,'i(x) = 0; 'i(x)0; 'iconvexes . les contraintes generales,'i(x) = 0; 'j(x)0 Dans tous les cas on se ramene a la resolution de problemes sans contrainte. Mais la reduction est plus ou moins aisee.

Regardons les cas des contraintes inegalites.

6.1 Relations de Kuhn-Tucker

Les relations de Kuhn-Tucker expriment que si la ou les solutions d'un probleme avec contraintes i(x)0 est a l'interieur du domaine des points admissibles, le gradient defs'annule comme c'est

le cas pour les problemes sans contrainte, et que si la ou les solutions sont sur le bord, il y a, comme

pour le cas des contraintes egalites, colinearite du gradient defet des gradients des'i.

6.1.1 Cas des contraintes non convexes

([3, p. 216])

Soitf:

E=Rn!R, derivable enx2Kavec

ouvert, K=fx2 ;'i(x)0;i= 1;:::;mg 6=; i: !Rderivables enx.

Sixest solution de

(P)(f(x) = infx2Kf(x) x 2K et si les contraintes sont qualieesenxau sens suivant : ou bien les'i; i2I(x) =fi;'i(x) = 0gsont anes, autrement dit les contraintes actives sont anes, ou bien9~!2Etel que8i2I(x); '0i(x)~!0 et'0i(x)~! <0 pour les'inon anes, alors il existe des multiplicateursde Lagrange i0, nuls pouri =2I(x), veriant les relations dites de Kuhn-Tucker f0(x) +Pm

1i'0i(x) = 0

i'i(x) = 0; i= 1;:::;m

6.1.2 Cas des contraintes convexes

([3, p. 218])

Soitf:

E=Rn!R, derivable enx2Kavec

22 Optimisation avec contraintes

ouvert convexe, K=fx2 ;'i(x)0;i= 1;:::;mg 6=; i: !Rconvexes, derivables enx.

1. Sixest solution de

(P)(f(x) = infx2Kf(x) x 2K et si les contraintes sont qualieesau sens suivant : les'isont anes ou9~!2Ktel que'i(~!)<0 pour les'inon anesquotesdbs_dbs29.pdfusesText_35

[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

[PDF] programme daeu a

[PDF] cours physique daeu b pdf