[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)quotesdbs_dbs50.pdfusesText_50

[PDF] dynamique des fluides exercices corrigés

[PDF] dynamique du point matériel exercices corrigés

[PDF] dynamique géographique des grandes aires continentales

[PDF] dynamique physique cours

[PDF] dynamique physique exercices corrigés

[PDF] dynamiques territoriales etats unis croquis

[PDF] dysgraphie

[PDF] dysgraphie molle

[PDF] dysorthographie et dysgraphie 285 exercices comprendre évaluer remédier s entraîner

[PDF] dysorthographie pdf

[PDF] dysphasie

[PDF] dysplasie carotide interne

[PDF] dysplasie fibromusculaire pdf

[PDF] dysplasie fibromusculaire renale

[PDF] dysplasie fibromusculaire sfr