[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
M1 MApI3 - UE OPTIMISATION
Support de cours
Luca Amodei
15 decembre 2017
1
1 Introduction
Qu'est-ce qu'un probleme d'optimisation?
SoientXRnetf:Rn!R:
Un probleme d 'optimisation(PX)est deni par
minf(x) sous la contraintex2X . L'ensembleXest appele domaine ou ensemble des contraintes. Un point x2Xest dit admissible. . La fonctionfest appelee fonction co^ut (ou objectif, ou critere). . Chercher une solution du probleme revient a chercher un point de mini- mum local ou global defdans l'ensemble des contraintesX:
On notera le probleme(PX)sous forme synthetique
minf(x) x2X(1) Remarque :On pourrait noterinff(x)(borne inferieure de l'ensemblef(X)) a la place deminf(x). De fait, c'est bien un pointx2Xqui realise la valeur de la borne inferieure qui est recherche. C'est donc la notationminf(x)(minimum de l'ensemblef(X)) que l'on utilisera. Denition 1.1.Un pointx2Xest un minimum local defsurXsi et seulement si il existe un voisinageVxdextel que8x2Vx\X;on a f(x)f(x): Denition 1.2.Un pointx2Xest un minimum global defsurXsi et seulement si8x2X;on af(x)f(x): Les minima sont dits stricts si les inegalites dans les denitions precedentes sont strictes pourx6=x:Cela signie que le minimumxest unique, soit dans le voisinageVx\X(dans le cas local), soit dans l'ensembleX(dans le cas global). Qu'en est-il pour une probleme de recherche de valeur maximum?
Il sut de considerer le probleme(QX)
minf(x) x2X 2 Un pointxsolution du probleme precedent(QX)verief(x) f(x);8x2
Xet est donc solution du probleme
maxf(x) x2X
Grandes familles des problemes d'optimisation
. Optimisation numerique :XRn . Optimisation discrete :Xest un ensemble n ou denombrable . Commande optimale, problemes inverses :Xest un ensemble de fonctions (dimension deXinnie) . Optimisation stochastique :Xest un ensemble aleatoire . Optimisation multicritere : on veut optimiser plusieurs fonctions objectifs en m^eme temps (notion d'optimum de Pareto) Ce cours d'optimisation s'interesse uniquement a l'optimisation numerique.
Exemples de problemes d'optimisation
1. Probleme de gain optimal.
On suppose qu'un produitPest fabrique dans une usine a partir den matieres premieres. La quantite de produitsPfabriques est donnee par une fonctionf(x1;:::;xn)(dite fonction de production) qui depend des quantitesx10;:::;xn0desnmatieres premieres utilisees. On note q >0le prix de vente unitaire du produitP;etp1>0;:::;pn>0;les prix unitaires correspondant auxnmatieres premieres,
La fonction de gaings'ecrit alors
g(x1;:::;xn) =qf(x1;:::;xn)p1x1p2x2 pnxn:
On cherche donc la solution du probleme
maxg(x) x2X ouXest l'ensembleRn+:
2. Probleme du transport optimal.
On veut transporter des marchandises dendep^ots ampoints de vente. On conna^t les quantites stockeessidans chaque dep^oti, les demandes d jdans chaque point de ventejet le co^ut de transport unitairecijpour transporter du dep^otiau point de ventej:On suppose quePn i=1siPm j=1dj(l'ore est superieure a la demande). 3 On cherche les quantitesxijtransportees entre les dep^otsiet les points de ventejqui minimisent le co^ut total de transport nX i=1m X j=1c ijxij sous les contraintes : x ij0;8i= 1;:::;n;j= 1;:::;m;Pn i=1xij=dj;8j= 1;:::;m;(il faut satisfaire toutes les demandes)Pm j=1xijsi;8i= 1;:::;n;(il ne faut pas depasser les quantites stockees). La fonction co^ut est ici lineaire et les contraintes (de type egalites et inegalites) sontegalement lineaires. Il s'agit de ce qu'on appelle un probleme de programmation lineaire. Ces problemes seront etudies en detail dans le cours "Fondamentaux de la recherche operationnelle" du Master 2 MApI3.
Algorithmique de l'optimisation
Un algorithme associe au probleme(PX)consiste a generer a partir d'un point initialx02Rn(ouX), une suite(xk)ouxk2Rn(ouX) qui converge versxsolution locale ou globale du probleme(PX): On dit que la convergence est locale si elle a lieu pour des points initiauxx0 dans un voisinage dex:Sinon elle est dite globale.
Vitesse de convergence
Soit la suite(xk)generee par un algorithme telle quelimkxk=x:Les denitions suivantes caracterisent les vitesses de convergence de la suite(xk).
Denition 1.3.
| La convergence est lineaire s'il existe2]0;1[tel que lim kkxk+1xkkxkxk= | La convergence est superlineaire si lim kkxk+1xkkxkxk= 0 | La convergence est d'ordreps'il existe0tel que lim kkxk+1xkkxkxkp= Pourp= 2;on dit que la convergence est quadratique. 4 Denition 1.4.Soitf:Rn!Rde classeC1. On dit qu'un algorithme generant la suite(xk)est globalement convergent si8x02Rnon alimkrf(xk) = 0: Cette propriete est justiee par le fait qu'une solutionxdu probleme(PX) sans contraintes (X=Rn) est un point critique c.-a-d.rf(x) = 0(voir plus loin theoreme 2.4). Cette condition est evidemment plus faible que la convergence de la suite(xk)vers une solutionx:
2 Resultats d'existence et d'unicite
Dans ce chapitre on presente les resultats generaux concernant l'existence et l'unicite de la solution du probleme de minimisation(PX) minf(x) x2X(2) On y enonce des conditions necessaires et susantes pour qu'un pointx2X soit un minimum local ou global du probleme(PX): Nous commencons par un resultat classique d'existence. Theoreme 2.1.(theoreme de Weierstrass) SiXest un ensemble non vide compact (,ferme et borne) etf:X!Rest continue, alors(PX)admet au moins une solution. Dans le cas ouXest uniquement ferme, il faut ajouter une propriete supplementaire pour garantir l'existence d'une solution. Denition 2.1.Une fonctionf:Rn!Rest dite coercive sur un ensemble
Xnon borne deRnsif(x)!+1lorsquekxk !+1avecx2X
(avec des quanticateurs, cela se traduit par8A >0;9 >0;(x2Xetkxk ))f(x)A). Theoreme 2.2.SiXest un ensemble non vide ferme etf:X!Rest continue et coercive, alors(PX)admet au moins une solution. Preuve :La demonstration se fait en considerant un pointx02X(Xest non vide) et l'ensembleX0=fx2Xjf(x)f(x0)g:Il est facile de voir que X
0est un ensemble non vide et compact (il est ferme carfest continue, et
borne du fait quefest coercive). Le probleme(PX0)admet donc une solution x
2X0. Celle-ci est aussi une solution du probleme(PX)car8x2XnX0on a
f(x)f(x0)< f(x): 5
Unicite de l'optimum
L'unicite de la solution repose en general sur des arguments de convexite. Theoreme 2.3.Soit(PX)le probleme de minimisation avecXconvexe et f:X!Rconvexe. Alors, | tout minimum local de(PX)est un minimum global de(PX); | sifest strictement convexe, il y a au plus un minimum de(PX):
Rappels sur la convexite
Denition 2.2.
| On dit qu'un ensembleXRnest convexe si et seulement si
8x;y2X;82[0;1]; x+ (1)y2X:
| SoitXun ensemble convexe. La fonctionf:X!Rest convexe si et seulement si
8x;y2X;82[0;1]; f(x+ (1)y)f(x) + (1)f(y):
| On dit quefest strictement convexe si l'inegalite precedente est stricte pourx6=yet2]0;1[:
2.1 Conditions necessaires et susantes d'optimalite
dans le cas sans contraintes On rappelle les formules de Taylor a l'ordre un et deux qui permettent d'etablir les conditions necessaires et susantes d'optimalite. On suppose que la fonctionf:Rn!Rest de classeC1. La formule de
Taylor defau pointx2Rna l'ordre un s'ecrit :
f(x+h) =f(x) +rf(x)Th+o(khk); ou l'egalite est veriee pour touth2Rndans un voisinage de0:Le reste o(khk)est deni par la fonctiono(r)(petitoder) qui verielimr!0o(r)r = 0:Le resteo(khk)peut donc s'ecrireo(khk) =khk(khk)ou la fonction(r)verie limr!0(r) = 0: On noterf(x)le gradient defau pointx:Il s'agit du vecteur colonne ayant pour coordonnees les derivees partielles @f@x i(x); i= 1;:::;n:C'est donc la transposee de la matrice jacobienneJf(x):rf(x) =Jf(x)T:Le produit vecteur 6 lignevecteur colonnerf(x)Thest donc le produit scalairehrf(x);hi(les vecteursrf(x)ethsont des vecteurs colonnes). Si l'on suppose que la fonctionfest de classeC2on obtient la formule de
Taylor a l'ordre deux :
f(x+h) =f(x) +rf(x)Th+12 hTr2f(x)h+o(khk2); ou l'egalite est veriee pour touth2Rndans un voisinage de0:On note ici r
2f(x)la matrice hessienne (nn, symetrique) ayant pour coecientsij(ligne
i, colonnej,i= 1;:::;n; j= 1;:::;n) les derivees secondes@2f@x i@xj(x)defau pointx: Dans le cas du probleme sans contraintes (c.-a-d.X=Rn) on a les deux conditions necessaires d'optimalite suivantes.
Condition d'optimalite d'ordre un
Theoreme 2.4.Sifest de classeC1etx2Rnun minimum local du probleme(PRn), alorsrf(x) = 0: Un point qui annule le gradient de la fonctionfest dit un point critique (ou singulier ou stationnaire) def. Ce theoreme arme donc que sixest un minimum local def, alorsxest un point critique. Il est facile de voir que dans le cas particulier oufest convexe (et dierentiable), alors la conditionrf(x) = 0est aussi susante pour quexsoit un mini- mum local (et donc global puisquefest convexe). On utilise pour ca l'inegalite f(y)f(x) +rf(x)T(yx);8x;y2Rn;qui est satisfaite lorsquefest convexe.
Rappels et complements sur les fonctions convexes
Proposition 2.1.
| Sif:Rn!Rest dierentiable, on a les equivalences suivantes
1.fest convexe,
2.f(y)f(x) +rf(x)T(yx);8x;y2Rn;
3.(rf(y) rf(x))T(yx)0;8x;y2Rn:
| On a equivalence entre la convexite stricte defet les inegalites 2. et
3. precedentes strictes, pourx6=y:
7 | Sif:Rn!Rest deux fois dierentiable, on a les equivalences suivantes
1.fest convexe,
2.8x2Rn;la matrice hessienner2f(x)est semi-denie positive.
Remarques :
La proposition precedente reste vraie si la fonctionfest denie sur un ouvert convexeXRn: Pour la stricte convexite, dans le cas ou la fonction est deux fois dierentiable, on a uniquement l'implication (r2f(x)denie positive8x2X))fstricte- ment convexe. La reciproque n'est pas vraie. Exemple : la fonctionf(x) =x4 est strictement convexe maisf00(0) = 0:
Conditions d'optimalite d'ordre deux
Theoreme 2.5.Sifest de classeC2etx2Rnun minimum local du probleme(PRn), alorsxest un point critique et de plusr2f(x)est semi- denie positive. Rappel :On dit que la matrice hessienner2f(x)est semi-denie positive si et seulement si h
Tr2f(x)h0;8h2Rn:
On montre que cette propriete equivaut a dire que toutes les valeurs propres de la matrice symetriquer2f(x)sont des nombres reels positifs ou nuls. Remarque :La notion de semi-denie positive d'une matrice n'est consideree que si la matrice est au prealable symetrique. La condition enoncee dans le theoreme precedent devient une condition suf- sante si la matrice hessienner2f(x)est denie positive. Theoreme 2.6.Sifest de classeC2etxun point critique tel quer2f(x) est denie positive, alorsxest un minimum local du probleme(PRn). Rappel :On dit que la matrice hessienner2f(x)est denie positive si et seulement si h
Tr2f(x)h >0;8h2Rn; h6= 0:
On montre que cette propriete equivaut a dire que toutes les valeurs propres de la matrice symetriquer2f(x)sont des nombres reels strictement positifs.
Cas particulier des fonctions elliptiques
8
Denition 2.3.(fonction elliptique)
On dit que la fonction de classeC1f:Rn!Rest elliptique s'il existe >0(dite constante d'ellipticite) tel que (rf(x) rf(y))T(xy)kxyk2;8x;y2Rn: Dans le cas ou la fonctionfest de classeC2, la propriete d'ellipticite est equivalente a : il existe >0tel que y
Tr2f(x)ykyk2;8x;y2Rn:
Proposition 2.2.Une fonction elliptiquefest strictement convexe et coer- cive. Pour les fonctions elliptiques, on a le resultat fondamental suivant. Proposition 2.3.SiXRnest un ensemble convexe ferme etfune fonc- tion elliptique, alors le probleme(PX)admet une solution unique. Un exemple classique de fonction elliptique est la fonction quadratique f(x) =12 xTAxbTx; denie par une matriceA2Rnndenie positive et un vecteurb2Rn:On a en eetrf(x) rf(y) =A(xy)et (xy)TA(xy)1kxyk2;8x;y2Rn; ou1>0est la plus petite valeur propre deA:
2.2 Conditions necessaires et susantes d'optimalite
dans le cas general Dans ce paragraphe on enonce des resultats generaux dans le cas ou l'en- semble des contraintesXest quelconque. Pour caracteriser un point optimalx2Xdu probleme(PX), on introduit la notion de direction admissible et plus generalement de direction tangente en x Denition 2.4.d2Rnest une direction admissible enx2Xs'il existe >0tel quex+sd2X;8s2[0;]: 9 On dit aussi que la directiondest rentrante dansXenx:On noteTax(X) l'ensemble des directions admissibles enx(relativement aX). On voit facilement que l'ensembleTax(X)est un c^one (c.-a-d. sid2Tax(X), alorsd2Tax(X)pour tout >0). La notion de direction tangente generalise la notion de direction admissible en considerant la limite de directions admissibles. Denition 2.5.d2Rnest une direction tangente enx2Xs'il existe une suite(dk); dk2Rn;veriantlimkdk=d;et une suite(k);k>0;veriant lim kk= 0;telles quex+kdk2X;8k: On voit facilement que cette denition est equivalente a : il existe une suite (xk); xk2X;veriantlimkxk=x;et une suite(k);k>0;veriantlimkk= 0; telles quelimkx kx k=d: On noteTx(X)l'ensemble des directions tangentes enxrelativementX: Proposition 2.4.Tx(X)verie les proprietes suivantes :
1.Tx(X)est un c^one ferme etTax(X)Tx(X);
2.Tx(X)R
+(Xx);
3. Six =2X, alorsTx(X) =;;
4. Six2X, alorsTx(X) =Rn:
La propriete 4. montre que siXest un ouvert, alorsTx(X) =Rnpour tout x2X: Enoncons le resultat general donnant les conditions necessaires d'optimalite du premier ordre pour le probleme(PX): Theoreme 2.7.(condition necessaire de Peano-Kantorovitch) Sifest dierentiable etxest un minimum local du probleme(PX);alors rf(x)Td0;8d2Tx(X):quotesdbs_dbs6.pdfusesText_11
COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin