[PDF] Université Paris Dauphine Optimisation et programmation dynamique

View - Download Université Paris Dauphine Optimisation et programmation dynamique

Previous PDF

Next PDF

Universite Paris Dauphine

Optimisation et programmation dynamique

Master mention Mathematiques appliquees 1ere annee

2015-2016

Pierre Cardaliaguet

2

Introduction

L'objet de ce cours est de presenter quelques notions sur deux types de problemes d'optimisation :

l'optimisation avec 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 recourent a des concepts similaires (conditions d'optimalite,

fonction valeur, etc...). Un mot d'avertissement : comme souvent en mathematiques, nous presentons ci-apres un cadre d'etude de ces problemes, en aucun cas des \recettes" pour les \resoudre". Trois raisons a cela : D'ab ordparce que l'expression \r esoudre"est am bigue.Dans la plupart des cas pratiques, la solu- tion explicite est inaccessible, et il faut recourir a des methodes numeriques|celles-ci s'appuyant fortement sur l'analyse mathematique du probleme (existence de solution, conditions necessaires d'optimalite, dualite, programmation dynamique,...). Bien garder en t ^etequ'assez fr equemmentles probl emesrencon tresen pratique sorten tdu cadre des hypotheses de l'analyse du cours. C'est notamment le cas en contr^ole optimal, ou je ne connais pas

un exemple utilise en economie qui entre parfaitement dans le cadre etudie : il faut alors comprendre

au cas par cas ce qui reste correct et ce qui ne l'est plus, en adaptant les techniques developpees dans ce cours au probleme etudie. Enn, les pr oblemesrencon trese npratique on ttr essouv entune structure sp eciale,qu'il faut bien s^ur utiliser pour gagner en ecacite. Le cours se contente de traiter de situations assez generales, et fait l'impasse sur plusieurs cas particuliers importants. En optimisation, nous ne mentionnerons que rapidement l'algorithme du simplexe (dans le cas ou les contraintes et le critere sont anes)

qui est de loin l'algorithme le plus utilise mais qui est traite dans d'autres UE. En contr^ole optimal,

on rencontre frequemment des problemes avec dynamiques lineaires et co^uts quadratiques, dont la resolution fait l'objet de techniques algebriques ecaces, mais qui sort du cadre du cours. Pre-requis :le cours utilise largement (et 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 gurent en appendice. Certaines parties du polycopie sont reprises d'annees anterieures et ne gurent pas au programme du cours 2014-2015.Sont hors programmela demonstration du theoreme de Kuhn & Tucker (section 1.3)

ainsi que les conditions du second ordre (section 1.6); la partie sur l'optimisation de portefeuille nancier

(section 1.7) est egalement hors programme, mais pourra ^etre traitee en exercice.

Table des matieres

1 Optimisation sous contraintes 5

1.1 Existence d'un minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.1 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.2 Condition d'existence d'un minimum sous contraintes . . . . . . . . . . . . . . . .

7

1.2 Conditions necessaires d'optimalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2.1 Condition necessaire d'optimalite dans un ouvert . . . . . . . . . . . . . . . . . . .

8

1.2.2 Le theoreme de Kuhn & Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.3 Demonstration geometrique du theoreme de Kuhn & Tuker . . . . . . . . . . . . . . . . .

14

1.3.1 Condition d'Euler abstraite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 4

1.3.2 Le lemme de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

1.3.3 Les contraintes anes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

1.3.4 Les contraintes d'inegalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

1.3.5 Le cas des contraintes d'egalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

1.3.6 Le cas general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

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

24

1.4 Problemes convexes et dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

1.4.1 Une condition de qualication de la contrainte . . . . . . . . . . . . . . . . . . . .

24

1.4.2 Le theoreme de Kuhn & Tucker exprime en termes de Lagrangien . . . . . . . . .

24

1.4.3 Les conditions necessaires sont susantes . . . . . . . . . . . . . . . . . . . . . . .

25

1.4.4 Le theoreme de dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

1.5 Methodes numeriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

1.5.1 Projection sur un ensemble convexe ferme . . . . . . . . . . . . . . . . . . . . . . .

27

1.5.2 Le gradient projete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

1.5.3 Algorithme d'Uzawa : contraintes d'egalite anes . . . . . . . . . . . . . . . . . . .

28

1.5.4 Algorithme d'Uzawa : contraintes d'inegalite anes . . . . . . . . . . . . . . . . .

30

1.5.5 Programmation lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

1.5.6 Autres methodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

1.6 Conditions du second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

1.6.1 Une condition necessaire du second ordre . . . . . . . . . . . . . . . . . . . . . . .

35

1.6.2 Preuve de la condition necessaire d'ordre 2 . . . . . . . . . . . . . . . . . . . . . .

35

1.6.3 Condition susante du second ordre . . . . . . . . . . . . . . . . . . . . . . . . . .

37

1.7 Optimisation de portefeuilles nanciers . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

1.7.1 Description du modele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

1.7.2 Formalisation du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

1.7.3 Le portefeuille de variance minimale . . . . . . . . . . . . . . . . . . . . . . . . . .

39

1.7.4 Caracterisation des portefeuilles ecients . . . . . . . . . . . . . . . . . . . . . . .

39

1.7.5 Le probleme avec un actif sans risque . . . . . . . . . . . . . . . . . . . . . . . . .

40

1.8 Tableau des conditions necessaires d'optimalite . . . . . . . . . . . . . . . . . . . . . . . .

42
3

4TABLE DES MATIERES

2 Programmation dynamique 43

2.1 Problemes en temps discret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

2.1.1 Probleme en horizon ni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

2.1.2 Probleme en horizon inni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

2.2 Calcul des variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

2.2.1 Quelques exemples de calcul des variations . . . . . . . . . . . . . . . . . . . . . .

49

2.2.2 Conditions necessaires d'optimalite . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

2.3 Contr^ole optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

2.3.1 Le theoreme de Cauchy-Lipschitz . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

2.3.2 Le principe du maximum de Pontryagin . . . . . . . . . . . . . . . . . . . . . . . .

58

2.3.3 Le principe de programmation dynamique . . . . . . . . . . . . . . . . . . . . . . .

59

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

60

A Convexite65

A.1 Denitions generales et propriete elementaires . . . . . . . . . . . . . . . . . . . . . . . . . 65

A.2 Convexite dansR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65

A.3 Caracterisation des fonctions convexes : le cas regulier . . . . . . . . . . . . . . . . . . . . 67
A.4 Caracterisation des fonctions convexes : le cas general . . . . . . . . . . . . . . . . . . . . 68

A.5 Regularite des fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

A.6 Convexite et optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

Chapitre 1

Optimisation sous contraintes

1.1 Existence d'un minimum

Dans cette partie, tres breve, on rappelle quelques denitions elementaires, et on enonce des conditions

susantes d'existence d'un minimum.

1.1.1 Vocabulaire

Inmum et minimum

Soitf:Rn!Rune fonction etKun sous-ensemble non vide deRn. Denition 1.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 noteeinfx2Kf(x):

l= infx2Kf(x):

Remarques :

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

8x2K; f(x)M :

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

Une suite ( xn) telle quexn2Kpour toutn2Net

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

1.8x2K; f(x)l :

2.f(x) =l.

Cette valeur est noteeminx2Kf(x).

5

6CHAPITRE 1. OPTIMISATION SOUS CONTRAINTES

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

Remarques :

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

Fonctions coercives

Denition 1.1.3.Une fonctionf:Rn!Rest coercive si

lim kxk!+1f(x) = +1 Remarque :Peu importe la normek kque l'on utilise puisque, surRn, toutes les normes sont equivalentes. En pratique, on choisit la norme la plus adaptee a la fonctionfetudiee.

Exemples a connaitre :

1. Soit Aune matrice symetrique, carree, d'ordreN,bun vecteur deRn, etcun reel. Alors la fonction f:Rn!Rdenie par f(x) =xTAx+bTx+c est coercive, si et seulement si,Aest une matrice denie positive. Rappelons que toute matrice

symetrique est diagonalisable. Une matrice est positive, si et seulement si, toutes ses valeurs propres

sont positives. Elle est denie positive, si et seulement si, toutes ses valeurs propres sont strictement

positives. SiAest symetrique, on a les inegalites suivantes :

8x2Rn; minkxk2 hAx;xi maxkxk2

ouminetmaxsont repectivement la plus petite et la plus grande valeur propre deA. En particlier, siAest denie positive, alorsmin>0. 2. T outefonction minor eepar une fonction co erciveest co ercive. Proposition 1.1.1.On suppose que la fonctionf:Rn!Rest de 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= maxijmij. SoitMxe. Il existe une constanteRi>0 telle que

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

PosonsR= maxiRi. Alors pour toutx2Rnaveckxk1R, il existei2 f1;:::;ngtel quejxij RRi. Donc f i(xi)M+nm. Comme

8j2 f1;:::;ng; fj(xj)mj m

on en conclut que f(x)M+X j6=i(mj+m)M

Donc on a montre que

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

Par consequent,

lim kxk1!1f(x) = +1:

Par consequent la fonctionfest coercive.

1.2. CONDITIONS N

ECESSAIRES D'OPTIMALITE7

1.1.2 Condition d'existence d'un minimum sous contraintes

Voici le resultat le plus important du chapitre :

Theoreme 1.1.1.Soitf:Rn!Rune fonction continue etKun sous-ensemble non vide deRn. Le probleme (P) minx2Kf(x) a une solution sil'une des deuxconditions suivantes est satisfaite 1. la c ontrainteKest compacte (theoreme de Weierstrass) 2. la fonction fest coercive et la contrainteKest fermee, Rappelons que dans le premier cas,fa aussi un maximum surK.

Preuve.Le premier cas etant tres classique, on ne montre que le second. Supposons quefsoit coercive etK

ferme. Notonsm= infx2Kf(x) etK1l'ensemble K

1=fx2Kjf(x)m+ 1gsim2RetK1=fx2Kjf(x)0gsinon:

Commefest coercive, l'ensembleK1est compact. De plus,K1est non vide par denition de l'inmum. Donc, d'apres la premiere partie du theoreme,fatteint son minimum surK1en un point x2K1. Montrons que xest un minimum defsurK. En eet, pour toutx2K, i) soitxappartient aK1, et alorsf(x)f(x) carfatteint son minimum surK1en x, ii) soitx =2K1, auquel cas on a : sim2R,f(x)m+1< f(x) (car x2K1) et sim=1,f(x)0< f(x).

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

Proposition 1.1.2.On suppose queKest un ouvert borne, quefest continue surK, et qu'il existe un pointx0deKtel que

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

ou@Kest la frontiere deK. Alors le probleme(P)admet une solution.

Preuve.En eet, comme l'ensembleKest compact, la fonction continuefadmet un minimum surK, c'est-a-dire

qu'il existe un element xdeKtel que

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

Montrons par l'absurde que xappartient en fait aK. En eet, sinon, xappartient au bord deK, carKest

un ouvert. Doncf(x0)< f(x) par hypothese. Mais cette inegalite est en contradiction avec le fait que xest un

minimum defsurK. Donc xappartient aK. Comme xest un minimum defsurK, queKKet que x

appartient aK, on en deduit que xest aussi un minimum defsurK.1.2 Conditions necessaires d'optimalite

SoitKun sous-ensemble deRnetfune application deRndansR. On cherche le ou les minima du probleme (P) (P) minx2Kf(x)

Dans ce chapitre, nous cherchonsdes conditions necessaires d'optimalite, c'est-a-dire des conditions,

portant sur la derivee def, satisfaites par le ou les minima du probleme. Ces conditions portent le nom

de conditions de Kuhn & Tucker, ou de Karush, Kuhn & Tucker, ou encore KKT.quotesdbs_dbs28.pdfusesText_34

[PDF] Circulaire du 26 janvier 2017 concernant les budgets primitifs 2017

[PDF] Conditions tarifaires de location de Véhicules RENT A CAR au 1er

[PDF] Exemple conducteur emission

[PDF] conducteurs en equilibre electrostatique - usthb

[PDF] Travaux dirigés : Conductance et Conductivité - Lycée Gustave

[PDF] Ch3 - EXERCICES Courant électrique dans les solutions aqueuses

[PDF] TRANSFERTS DE CHALEUR - Exercices de références - Doc 'INSA

[PDF] Vapeur - ThermExcel

[PDF] La Conductivité thermique de quelques matériau de construction

[PDF] Propriétés thermiques des matériaux et références métrologiques

[PDF] fimo / fco - Pardessuslahaie

[PDF] Conduire en France avec un permis étranger et son échange I

[PDF] conduite ? tenir devant une femme ayant une cytologie - Aly Abbara

[PDF] Scorpion - Centre AntiPoison et de Pharmacovigilance du Maroc

[PDF] PDF 241 ko Gestion de projet - FOAD