[PDF] Optimisation et programmation dynamique

View - Download Optimisation et programmation dynamique

Previous PDF

Next PDF

Optimisation et programmation dynamique

Master mention Mathematiques Appliquees, 1

ereannee

Universite Paris Dauphine

Olga Mula

(Version du 6 janvier 2019) 1

Introduction

Ces notes sont un support pour le cours

Optimisation et programmation dynamique

du Master 1 de mathematiques appliquees de l'Universite Paris Dauphine. L'objectif est de presenter quelques notions sur deux types de problemes d'optimisation : l'optimisation enRnsous contraintes,

d'une part, et le contr^ole optimal, d'autre part. Ces deux problematiques se rencontrent frequemment

dans toutes les questions liees a la decision. Si les methodes de resolution dierent sensiblement, les deux domaines ont recours a des concepts similaires (conditions d'optimalite, fonction valeur, etc...). Dans la pratique, les problemes rencontres ont souvent une structure speciale qui sortira du cadre general abstrait du cours. Il faudra alors adapter les techniques developpees au probleme etudie.

Aussi, la solution explicite est en general inaccessible et il faut recourir a des methodes numeriques,

celles-ci s'appuyant fortement sur l'analyse mathematique du probleme. Nous donnerons un apercu de quelques unes de ces methodes. Pre-requis :Le cours utilise souvent sans rappel des notions de calcul dierentiel et d'analyse convexe de L2, de topologie et d'equations dierentielles de L3, et d'analyse fonctionnelle de L3 et de M1. Quelques rappels d'analyse convexe sont neanmoins donnes au debut de ces notes. References bibliographiques :Quelques references sont donnees a la n du poly. Pour la

partie sur l'optimisation sous contraintes, deux bonnes references en langue francaise sont les livres

respectifs de P. G. Ciarlet et G. Allaire. Pour la partie sur le contr^ole optimal, le poly du cours a l'ENSAE de Carlier constitue une bonne introduction. Nous citons aussi le livre de Lucas et Stokey qui est une excellent reference pour les problemes en temps discret et contient de nombreux exempleseconomiques. Pour la partie en temps continu, une reference possible est le livre de Fleming et Rishel.

Remarques :

Ces notes son tbas eessur plusieurs do cumentsexistan ts.Le c hapitresur l'optimisation sous contraintes est un resume de certains chapitres du livre de G. Allaire. La partie sur la programmation dynamique est reprise pratiquement integralement du polycopie de P. Car- daliaguet utilise les annees anterieures. La pr esenteforme de ces notes con tientcertainemen tdes co quilleset des pass agesdon tla redaction pourrait ^etre amelioree. Merci de me signaler toutes remarques permettant des les ameliorer. 2

Table des matieres

I Rappels5

1 Convexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1 Fonctions convexes, strictement convexes, fortement convexes . . . . . . . . .

5

1.2 Exemples de fonctions convexes, strictement convexes, fortement convexes . .

6

1.3 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

II Optimisation sous contraintes 9

1 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2 Conditions generales d'existence d'un minimum . . . . . . . . . . . . . . . . . . . . .

10

2.1 Conditions susantes lorsqueKest ouvert ou ferme . . . . . . . . . . . . . .10

2.2 Conditions necessaire et susantes lorsqueKest convexe . . . . . . . . . . .11

3 Le theoreme de Kuhn et Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.1 Contraintes d'egalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

3.2 Contraintes d'inegalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.3 Contraintes d'egalite et d'inegalite . . . . . . . . . . . . . . . . . . . . . . . .

16

3.4 Methode de resolution d'un probleme de minimisation . . . . . . . . . . . . .

17

3.5 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4 Dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.2 Theorie generale du point selle et de la dualite . . . . . . . . . . . . . . . . .

22

4.3 Application de la theorie du point selle a l'optimisation . . . . . . . . . . . .

23

5 Methodes numeriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

5.1 Projection sur un ensemble convexe ferme . . . . . . . . . . . . . . . . . . . .

26

5.2 Algorithme du gradient projete a pas xe . . . . . . . . . . . . . . . . . . . .

27

5.3 Algorithme d'Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

IIIProgrammation dynamique 33

1 Problemes en temps discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

1.1 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

1.2 Problemes en horizon ni . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

1.3 Problemes en horizon inni . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

2 Calcul des variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

2.1 Quelques exemples de calcul des variations . . . . . . . . . . . . . . . . . . .

44

2.2 Conditions necessaires d'optimalite . . . . . . . . . . . . . . . . . . . . . . . .

45

3 Contr^ole optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.1 Le theoreme de Cauchy-Lipschitz . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.2 Le principe du maximum de Pontryagin . . . . . . . . . . . . . . . . . . . . .

54
3

3.3 Le principe de programmation dynamique . . . . . . . . . . . . . . . . . . . .55

3.4 Lien avec les equations de Hamilton-Jacobi . . . . . . . . . . . . . . . . . . .

56

IVElements de bibliographie 61

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike

4.0 International License which permits unrestricted use, distribution, and reproduction in

any medium, provided the original authors are credited. The use is non-commercial. For the complete licence details, see

Partie I

Rappels

A toutes ns utiles, nous rappelons quelques elements de calcul dierentiel, analyse convexe et extrema.

1 Convexite

1.1 Fonctions convexes, strictement convexes, fortement convexes

Denition 1.1.Un ensembleKRnest dit convexe si8x; y2Kon atx+ (1t)y2Kpour toutt2[0;1] (quelque soit deux points dansK, tout le segment qui les unit est dansK). Denition 1.2.SoitKRnun ensemble convexe etf:K!Rune fonction. 1.

On dit que festconvexesurKsi

f(tx+ (1t)y)tf(x) + (1t)f(y);8x;y2K; t2[0;1]: 2.

On dit que feststrictement convexesurKsi

f(tx+ (1t)y)< tf(x) + (1t)f(y);8x6=y2K; t2]0;1[: 3. On dit que festfortement convexesurKs'il existe >0 tel que f(tx+ (1t)y)tf(x) + (1t)f(y)t(1t)kxyk2;8x;y2K; t2[0;1]: 4. On dit que festconcavesifest convexe (idem pour strictement/fortement concave).

Il est facile de voir que

fortement convexe)strictement convexe)convexe mais les reciproques ne sont pas vraies en general. Si la fonctionf2 C1(K), la convexite peut s'exprimer suivant les trois facons suivantes. Proposition 1.3(Caracterisation de la convexite).SoitKRnun ensemble convexe etf:K! Rune fonction de classeC1(K). Les trois propositions suivantes sont equivalentes : fest convexe surK(1.1) f(y)f(x) +hrf(x);yxi;8x;y2K(1.2) hrf(y) rf(x);yxi 0;8x;y2K(1.3) La stricte convexite a la m^eme caracterisation en remplacant les inegalites par des inegalites strictes. Finalement, la forte convexite se caracterise de facon similaire. 5 Proposition 1.4(Caracterisation de la forte convexite).SoitKRnun ensemble convexe et f:K!Rune fonction de classeC1(K). Les trois propositions suivantes sont equivalentes : fest-fortement convexe surK(avec >0)(1.4) f(y)f(x) +hrf(x);yxi+2 kyxk2;8x;y2K(1.5) hrf(y) rf(x);yxi kyxk2;8x;y2K(1.6) Denition 1.5.On appellefonction elliptiqueune fonctionf:K!Rde classeC1et fortement convexe. Ces fonctions se caracterisent par la proposition 1.4.

Proposition 1.6(Quelques proprietes).

1. T outec ombinaisonlin eaire ac oecientsp ositifsd'une famil lede fonctions c onvexesest convexe. 2. T outec ompositiond'une fonction f:Rn!Ret d'une fonction convexe croissanteg:R!R est convexe. Preuve.Commef(tx+ (1t)y)tf(x) + (1t)f(y) pour toutx; y2R, alors, comme g est croissante, gf(tx+ (1t)y)g(tf(x) + (1t)f(y))tgf(x) + (1t)gf(y)

ou nous avons utilise la convexite degdans la derniere inegalite.1.2 Exemples de fonctions convexes, strictement convexes, fortement convexes

1. La fonction f:R!Rdonnee parf(x) =x2est fortement convexe.

Preuve.Pour toutx; y2R,

hrf(y) rf(x);yxi= (f0(y)f0(x))(yx) = 2jyxj2

donc la fonction est fortement convexe avec= 2.2.De fa consimilaire, la norme euclidienne au carr ef:Rn!Ravecf(x) =kxk2est aussi

fortement convexe avec= 2. Preuve.Commerf(x) = 2xpour toutx2Rn, on ahrf(y) rf(x);yxi= 2ky xk2.3.Plus g eneralement,soit f:Rn!Rla fonction donnee par f(x) =12 hAx;xi+hb;xi+c(1.7) avecMn(R) une matrice carree reelle de taillenetb2Rnetc2R. On a hrf(y) rf(x);yxi=hA(yx);(yx)i

Par consequent,

(a)Asemi-denie positive,fconvexe. (b)Adenie positive de plus petite valeur propremin>0,ffortement convexe avec =min. 6

1.3 Fonctions coercives

Denition 1.7.SoitKRnun ensemble non borne (par exemple,Rn). Une fonctionf:K!R est coercive surKsi limx2K;kxk!+1f(x) = +1:

Ceci peut s'ecrire de facon equivalente :

Pour toute suite (xk)k2NKtelle quekxkk ! 1, alorsf(xk)! 1. Remarque :Comme toutes les normes sont equivalentes surRn, en pratique, on choisit la norme la plus adaptee a la fonctionfetudiee. Proposition 1.8.SoitKRnun ensemble convexe non borne. Sif:K!Rest de classeC1 surKet fortement comvexe surK. Alorsfest coercive surK. Preuve.La formule (1.5) pour les fonctions fortement convexes nous permet d'ecrire pour tout x;y2K, f(y)f(x) +hrf(x);yxi+2 kyxk2:(1.8)

De plus, par l'inegalite de Cauchy-Schwarz,

hrf(x);xyi krf(x)kkxyk ) hrf(x);yxi krf(x)kkxyk: En injectant la derniere inegalite dans (1.8), il vient f(y)f(x) krf(x)kkxyk+2 kyxk2:

En xantx2Ket en faisantkyk ! 1(ce qui impliquekyxk ! 1), on obtient le resultat.Examples de fonctions coercives :

1. P arla prop osition1.8, les fonction sfortemen tcon vexesson tco ercives.En particulier, la fonction f(x) =12 hAx;xi+hb;xi+c(1.9) est fortement convexe, donc coercive, siAest denie positive. 2. T outefonction minor eep arune fonction co erciveest co ercive. 3.

Soit la f onctionf:Rn!Rde la forme

8x= (x1;:::;xn)2Rn; f(x) =nX

i=1f i(xi) ou les fonctionsfi:R!Rsont minorees et coercives. Alorsfest coercive. Preuve.Pour touti2 f1;:::;ng,fiest minore par une constantemi. Posonsm= max1i6=njmij et soitM >0 xe. Comme chaquefiest coercif, il existe une constanteRi>0 telle que

8jxij Ri; fi(xi)M+nm :

7 SoitR= max1inRi. Alors pour toutx2Rnaveckxk1R, il existe un indicei2 f1;:::;ngtel quejxij RRiet doncfi(xi)M+nm. Pourj6=i, f j(xj)mj m:

Ces minorations permettent de conclure que

f(x)M:

On a donc montre que

8M0;9R >0 tel que8x2Rn;kxk1R)f(x)M :

Par consequent,

limkxk1!1f(x) = +1 ce qui prouve la coercivite def.8

Partie II

Optimisation sous contraintesDans toute la suite, nous consideronsf:Rn!Rune fonction continue etKun sous-ensemble

non vide deRn. Nous allons etudier le probleme d'optimisation min x2Kf(x):(P) Nous verrons tout d'abord des conditions susantes garantissant permettant de voir si le minimum existe bien. L'expression de ces conditions varie en fonction de la structure de l'ensembleKet la regularite de la fonctionf. On distinguera siKest ouvert, ferme, borne ou convexe et sifest seulement continu ou bien de classeC1. Nous aborderons ensuite la question reciproque, c'est a dire les conditions necessaires que sa- tisfont les points de minimum. Cela amene naturellement la question de savoir si ces conditions necessaires sont susantes. En utilisant des elements de la theorie de la dualite, nous verrons que les conditions necessaires sont susantes dans certains cas. La theorie de la dualite nous permettra aussi de construire des methodes numeriques ecaces que nous etudierons.

1 Terminologie

Inmum et minimum

Denition 1.1.On appelleinmumdefsurKla valeurl2[1;+1[ telle que

1.8x2K,f(x)l,

2. il existe une suite ( xn) d'elements deRntelle que

8n0; xn2Ket limnf(xn) =l

Cette valeur est notee inf

x2Kf(x) : l= infx2Kf(x):

Remarques :

1. L'inm umexiste toujours. Il est ni (c'est- a-direque l6=1) si et seulement si la fonction festminoreesurK, c'est-a-dire s'il existe une constanteM2Rtelle que

8x2K; f(x)M :

2.

Si fn'est pas minoree, alors l'inmum defest1.

3.

Une suite ( xn) telle quexn2Kpour toutn2Net

lim nf(xn) = infx2Kf(x) est appelee unesuite minimisantedu probleme de minimisation. 9 Denition 1.2.On appelleminimumdefsurKla valeurl2] 1;+1[ - si elle existe - pour laquelle il existe un element x2Ktel que

1.8x2K; f(x)l :

2.f(x) =l.

Cette valeur est notee min

x2Kf(x). On dit alors quefatteint son minimum surKen x, ou que le probleme minx2Kf(x) admet une solution x.

Remarques :

1. P arabus de language, on app elleaussi minim umun element x2Ksatisfaisant les proprietes ci-dessus (en toute rigueur, xdevrait s'appeler \argument du minimum".) 2. Con trairement al'inm um,l eminim umn'existe pas toujours. Des conditions susan tes d'existence sont donnees ci-dessous.

2 Conditions generales d'existence d'un minimum

2.1 Conditions susantes lorsqueKest ouvert ou ferme

Il est possible d'enoncer des conditions susantes d'existence de minima pour le probleme (P) dans le cas tres general ouKest ferme ou bien ouvert.

Theoreme 2.1(Condition susante,Kferme).

SoitKRnun ensemble non-vide et ferme etf:K!Rune fonction continue. Le probleme (P) minx2Kf(x) admet au moins une solution si l'une des deux conditions suivantes est satisfaite : 1. la c ontrainteKest bornee (theoreme de Weierstrass), 2. la c ontrainteKest non bornee etfest coercive. Rappelons que dans le premier cas,fa aussi un maximum surK. Preuve.Dans le premier cas,Kest ferme et borne, donc il est compact. Commefest continue, le theoreme de Weierstrass assure quefest bornee surKet elle atteint ses bornes. Donc il existe au moins un point de minimum. Prouvons le deuxieme point. Soitx02Kxe. La coercivite defentra^ne qu'il exister >0 tel que kxk r)f(x)f(x0) Donc, en notantB(0;r) la boule deRnde centre 0 et de rayonr, nous avons inf x2Kf(x) = inf x2K\B(0;r)f(x): Comme l'ensembleK\B(0;r) est ferme et borne et quefest continue, le theoreme de Weierstrass assure que quefatteint ses bornes dansK\B(0;r). Ceci assure l'existence d'un minimumxdans K\B(0;r). Ce minimum est aussi le minimum surK. En eet, pour toutx2K: 10

1.soit x2K\B(0;r), et alorsf(x)f(x) carfatteint son minimum surK\B(0;r),

2. soit x62K\B(0;r), auquel cas on af(x)f(x0)f(x).

Ceci montre donc quexest un minimum defsurK.SiKest un ensemble ouvert, le probleme est plus complique. Signalons la condition susante

suivante :

Proposition 2.2(Condition susante,Kouvert).

On suppose queKest un ouvert borne, quefest continue surK, et qu'il existe un pointx0deK tel que

8x2@K; f(x)> f(x0):

ou@Kest la frontiere deK. Alors le probleme(P)admet une solution. Preuve.Comme l'ensembleKest compact, la fonction continuefadmet un minimumxsurK par le theoreme 2.1. Cet element est donc tel que

8x2K; f(x)f(x):

Montrons par l'absurde quexest bien dans l'ouvertKet ne se trouve pas au bord. Supposons quex2@K. Alorsf(x)f(x) pour toutx2K. Or, par hypothese, il existex02Ktel que f(x)> f(x0) pour toutx2@K, donc pourx=x,f(x)> f(x0). Cette contradiction nous permet de conclure quexest bien dans l'ouvertK.2.2 Conditions necessaire et susantes lorsqueKest convexe A present, rajoutons un peu plus de structure sur l'ensembleKet supposons qu'il est convexe.

Ceci permet d'enoncer les conditions necessaires d'optimalite suivantes, c'est-a-dire des conditions,

portant sur la derivee def. Theoreme 2.3(Condition necessaire,Kconvexe : Inequation d'Euler). Soit

Rnun ouvert,K

un ensemble convexe etf: !Rune fonction de classeC1. Si x est un minimum local defsurK, alors hrf(x);yxi 0;8y2K:(2.1) Preuve.Soity2Keth2]0;1]. Alors,x+h(yx)2KcarKest convexe. De plus, commex est un minimum local deK, f(x+h(yx))f(x)h 0: On trouve (2.1) en faisant un developpement de Taylor def(x+h(yx)) autour dexau premier

ordre, puis en faisant tendrehvers 0+.Nous verrons dans le theoreme suivant 2.4 que la condition necessaire (2.1) devient susante

lorsquefest convexe. Avant de presenter ce resultat, il est important de voir que dans deux cas importants la condition (2.1) se reduit al'equation d'Euler rf(x) = 0:

Ces deux cas sont :

11

1.Si K=Rn, alorsyxengendre tout l'espaceRncary2Rn. Par consequent (2.1) implique

rf(x) = 0. 2. Si Kest un ouvert, ou bien siKest convexe maisxest dans l'interieur deK(qui est aussi un ouvert). Preuve.Il faut montrer que sixest un minimum local dans un ouvertK, alors hrf(x);yxi 0;8y2K() rf(x) = 0: L'implication inverse etant evidente, regardons l'implication directe. Soityun vecteur quel- conque deRn. Commexappartient aK, qui est ouvert, il existeh0>0 tel que, pour tout h2[0;h0], le pointx+hyappartient aK. Orxetant un minimum local du probleme, on a f(x+hy)f(x)0 Comme f(x+hy)f(x) =hhrf(x);yi+h(hy); en divisant l'inegalite ci-dessus parh >0, et en faisant tendrehvers 0, on obtientquotesdbs_dbs47.pdfusesText_47

[PDF] optimisation processus industriel

[PDF] optimisation sous contraintes

[PDF] optimisation synonyme

[PDF] optimiser la recette

[PDF] Optimiser un cout de fabrication

[PDF] optimiser une recette

[PDF] Optimiser une recette (fonction carré Problèmes du 2nd degré)

[PDF] Optimiser une recette (transmath 2nde chapitre foction carré Problémes du 2nd degré ex 101 P 86)

[PDF] optimiser une recette d'un cinéma ( statistique, équation)

[PDF] optimiser une recette maths seconde

[PDF] Optimum de Pareto

[PDF] optimum de pareto exercice corrigé

[PDF] optimum de pareto graphique

[PDF] option art plastique bac 2017 candidat libre

[PDF] option art plastique bac candidat libre