[PDF] [PDF] optimisation Sp - mathuniv-paris13fr

View - Download [PDF] optimisation Sp - mathuniv-paris13fr

Previous PDF

Next PDF

Institut Galilee, Universite Paris 13, Sorbonne Paris Cite

Departement de mathematiques

Analyse numerique: optimisation

Specialite MACS de SupGalilee: Promotion

2017-2020.

Optimisation continue:

Mathematiques Financieres-Actuariat

Modelisation mathematique

Centrale Marseille (Promotion 2019).

Master EDP de Aix-Marseille Universite.

Olivier Latte

1 1 SupGalilee, Institut Galilee, Universite Paris XIII, LAGA olivier.latte@mines.org 2

Contents

1 Introduction et exemples 7

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Description du cours . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Euler-Legendre 21

2.1 Condition generale d'existence (susante) . . . . . . . . . . . . . 21

2.2 Condition d'Euler, condition de Legendre . . . . . . . . . . . . . 22

2.2.1 Derivabilite au sens de Frechet et au sens de G^ateaux . . 22

2.2.2 Deux espaces de Hilbert utiles dans la totalite de ce cours 24

2.2.3 Conditions necessaires d'optimalite. Conditions susantes

d'optimalite . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 Inequation d'Euler dans un probleme avec contraintes . . . . . . 27

2.4 Multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . . . . 28

2.4.1 Contraintes egalites . . . . . . . . . . . . . . . . . . . . . 29

2.4.2 Les contraintes inegalite . . . . . . . . . . . . . . . . . . . 32

2.4.3 L'inegalite de Hardy. . . . . . . . . . . . . . . . . . . . . . 36

2.4.4 Probleme mixte . . . . . . . . . . . . . . . . . . . . . . . . 36

2.4.5 Le probleme des entrep^ots . . . . . . . . . . . . . . . . . . 40

2.4.6 Demonstration du lemme de Kantorovich . . . . . . . . . 42

2.4.7 Calcul de la constante optimale de Poincare . . . . . . . . 43

3 Calcul des variations 45

3.1 Introduction et un peu d'histoire . . . . . . . . . . . . . . . . . . 45

3.2 Problemes isoperimetriques . . . . . . . . . . . . . . . . . . . . . 46

3.2.1 Egalite d'Euler-Lagrange . . . . . . . . . . . . . . . . . . 46

3.2.2 Derivee de Frechet et de G^ateaux, inegalite d'Euler-Lagrange 47

3.2.3 Egalite d'Euler-Lagrange pour une contrainte integrale . . 48

3.2.4 Les problemes de Bolza . . . . . . . . . . . . . . . . . . . 50

3.3 Les equations d'Euler pour les problemes de la mecanique . . . . 51

3.4 Formulation hamiltonienne . . . . . . . . . . . . . . . . . . . . . 52

4 Programme convexe 57

4.1 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.1.1 Complements et extensions . . . . . . . . . . . . . . . . . 60

4.2 Minimisation de fonctionnelles convexes . . . . . . . . . . . . . . 62

3

4CONTENTS

4.3 Fonctionnelles quadratiques. Formulations variationnelles. . . . . 64

4.4 Kuhn et Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.4.1 Introduction a la notion de Lagrangien . . . . . . . . . . . 65

4.4.2 Point selle, lagrangien, et minimisation de fonctionnelle

convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.4.3 Principe du Min-Max . . . . . . . . . . . . . . . . . . . . 70

5 Introduction au contr^ole optimal 73

5.1 Le probleme general . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.2 Traitement abstrait du cas general . . . . . . . . . . . . . . . . . 74

5.3 Le cas particulier du contr^ole distribue pour le probleme de

Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.3.1 Systeme gouverne par un probleme de Neumann . . . . . 76

5.4 Equation de Hamilton-Jacobi-Bellmann . . . . . . . . . . . . . . 77

6 Approximation de solutions 85

6.0.1 Algorithme de relaxation . . . . . . . . . . . . . . . . . . 85

6.1 Algorithmes de descente . . . . . . . . . . . . . . . . . . . . . . . 88

6.2 Cas classiques d'algorithmes de descente . . . . . . . . . . . . . . 90

6.2.1 Pas optimal . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.2.2 Pas de Curry . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.2.3 Pas de Goldstein . . . . . . . . . . . . . . . . . . . . . . . 91

6.2.4 Pas de Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.3 Resultats de convergence . . . . . . . . . . . . . . . . . . . . . . . 93

6.4 Algorithmes de gradient . . . . . . . . . . . . . . . . . . . . . . . 95

6.4.1 Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6.4.2 L'algorithme de gradient a pas optimal . . . . . . . . . . . 96

6.4.3 Algorithme de gradient a pas constant . . . . . . . . . . . 98

6.4.4 Taux de convergence de l'algorithme du gradient en di-

mension nie . . . . . . . . . . . . . . . . . . . . . . . . . 98

6.4.5 Algorithme de gradient reduit . . . . . . . . . . . . . . . . 102

6.5 Algorithmes de gradient conjugue . . . . . . . . . . . . . . . . . . 105

6.5.1 Exemple en dimension 2 . . . . . . . . . . . . . . . . . . . 105

6.5.2 Algorithme de directions conjuguees . . . . . . . . . . . . 106

6.5.3 Algorithme du gradient conjugue . . . . . . . . . . . . . . 109

6.5.4 Un exemple en dimension 3 . . . . . . . . . . . . . . . . . 115

6.6 Descente pseudo-conjugue . . . . . . . . . . . . . . . . . . . . . . 117

6.7 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.8 Algorithmes d'optimisation avec contraintes . . . . . . . . . . . . 123

6.8.1 Le gradient avec projection . . . . . . . . . . . . . . . . . 123

6.8.2 Penalisation des contraintes . . . . . . . . . . . . . . . . . 125

6.8.3 Algorithme d'Uzawa . . . . . . . . . . . . . . . . . . . . . 127

7 Introduction a la discretisation 129

7.1 Les dierences nies . . . . . . . . . . . . . . . . . . . . . . . . . 129

7.2 Les elements nis . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

CONTENTS5

8 Resume 139

8.1 Resultats d'existence . . . . . . . . . . . . . . . . . . . . . . . . . 139

8.1.1 Theoreme de Weierstrass . . . . . . . . . . . . . . . . . . 139

8.1.2 Cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . 140

8.2 Rappels de calcul dierentiel . . . . . . . . . . . . . . . . . . . . 140

8.2.1 Derivees premieres . . . . . . . . . . . . . . . . . . . . . . 141

8.2.2 Derivees secondes . . . . . . . . . . . . . . . . . . . . . . . 141

8.2.3 Formules de Taylor . . . . . . . . . . . . . . . . . . . . . . 141

8.3 Caracterisation des extrema . . . . . . . . . . . . . . . . . . . . . 143

8.3.1 Equation d'Euler, cas general . . . . . . . . . . . . . . . . 143

8.3.2 Inequation d'Euler, cas convexe . . . . . . . . . . . . . . . 143

8.3.3 Multiplicateurs de Lagrange, cas general . . . . . . . . . . 145

8.3.4 contraintes egalites . . . . . . . . . . . . . . . . . . . . . . 145

8.3.5 contraintes inegalites . . . . . . . . . . . . . . . . . . . . . 146

8.4 Lagrangien et point selle . . . . . . . . . . . . . . . . . . . . . . . 149

8.4.1 Point selle . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

8.4.2 Theorie de Kuhn et Tucker . . . . . . . . . . . . . . . . . 150

8.5 Methodes de descente. Problemes sans contraintes . . . . . . . . 151

8.5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

8.5.2 Methode de relaxation . . . . . . . . . . . . . . . . . . . . 152

8.5.3 Methode du gradient . . . . . . . . . . . . . . . . . . . . . 152

8.6 Estimations et convergence dans le cas quadratique . . . . . . . . 153

8.6.1 Methode a pas optimal . . . . . . . . . . . . . . . . . . . 153

8.6.2 Methode de gradient a pas constant . . . . . . . . . . . . 154

8.7 Methode du gradient conjugue . . . . . . . . . . . . . . . . . . . 154

8.7.1 Principe de la methode . . . . . . . . . . . . . . . . . . . 154

8.7.2 Ecriture comme algorithme de descente . . . . . . . . . . 155

8.7.3 Analyse de convergence . . . . . . . . . . . . . . . . . . . 155

8.8 Methodes pour les problemes avec contraintes . . . . . . . . . . . 156

8.8.1 Methode de gradient projete a pas variable . . . . . . . . 156

8.8.2 Algorithme d'Uzawa . . . . . . . . . . . . . . . . . . . . . 157

6CONTENTS

Chapter 1

Introduction et exemples

1.1 Introduction

Le but de ce cours est d'introduire quelques unes des methodes de la theorie de l'optimisation. La methode employee dans ce cours consiste essentiellement a presenter une suite (non exhaustive) d'exemple simples issu en majeure partie de la physique et de l'economie pour mettre en valeur une question que l'on se pose dans le cadre de l'optimisation: trouver la meilleure quantite ou le meilleur choix pour un probleme lie a la physique ou a l'economie. Ce cours presentera peu de resultats (les theoremes principaux sont peu nombreux). Nous avons essaye de traiter explicitement ici des exemples modeles simples, qui peuvent nous permettre d'introduire des notions et de pouvoir les generaliser. Les theories liees a l'optimisation sont tres variees. On rencontre par exem- ple (et cela est le plus courant) des problemes de minimisation sons contraintes, des resolutions d'equations aux derivees partielles sous forme variationnelle, des problemes de contr^ole, des problemes de commande. Elles ont en commun la minimisation d'uncritere, c'est-a-dire d'une fonction chargee de mesurer leco^utd'un probleme, en fonction de variables dites d'etat (caracterisant la position d'une particule par exemple) et de variables dites de commande (qui modelisent les parametres par lesquels on peut agir sur un systeme). Nous evoquerons ainsi dans le cours la notion de commande optimale, dans les cas ou, a partir de variables d'etatxet de commandesu, on souhaite soit minimiser un critere, soit atteindre un etat xe. Un des atouts de l'optimisation est la facilite d'obtention d'algorithmes numeriques qui convergent, et nous en aborderons certains: algorithmes d'optimisation sans contrainte, comme un algorithme ou on recherche un optimum surNvari- ables en resolvant, a chaque etape,Nalgorithmes d'optimisation sur chaque variable, des algorithmes dit de gradient (a pas xe ou a pas optimal, c'est a dire une generalisation de la methode de Newton de recherche de zeros), des algorithmes de minimisation avec contraintes, l'algorithme d'Uzawa. Pour l'instant, nous allons donner une liste non exhaustive d'exemples, provenant des references [2], [3], [1]. Certains pourront ^etre resolus dans cette introduction sans utiliser de theoremes nouveaux, d'autres non, et nous voulons, dans la suite de ce cours, pouvoir resoudre les problemes abordes ici. 7

8CHAPTER 1. INTRODUCTION ET EXEMPLES

Les exemples abordes dans cette introduction peuvent ^etre lus apres le cours correspondant, ils sont faits pour motiver les theoremes du cours d'optimisation et de calcul des variations. On peut, tres sommairement, diviser les resultats en conditions necessaires et en conditions necessaires et susantes d'optimalite. Par exemple,x2est minimum enx= 0, ou sa derivee s'annule, mais la derivee de 1x2est dans le m^eme cas, alors que 1x2est maximum enx= 0. La condition \la derivee s'annule" est une condition necessaire de minimum, mais n'est pas une condition susante.

1.2 Description du cours

Cours 1: calcul fonctionnel, distance a un convexe, derivee de 1/2(Ax,x) -(b, x) et resultats generaux (euler, legendre), Cours 2: contraintes egalite et x de Lagrange pour une deuxieme seance et debut de contraintes inegalite Cours 3: n des contraintes inegalite et alpha convexite. Inegalite de Poincare. Cours 4: le programme convexe, jusque au theoreme de Kuhn et Tucker : Cours 5: algorithmes de gradient (sans la preuve de convergence sauf dans le cas pas constant): pas constant, pas optimal, gradient conjugue eteventuellement relaxation.

Ce polycopie presente deux parties:

le cours proprement dit (dont seulement certains chapitres seront traites, et pas forcement comme ils le sont ici), un resume de cours.

1.3 Exemples

1. Resolution d'un systeme matriciel.

SoitAune matrice symetriqueNNdenie positive etbun vecteur de IR N. La solution du systeme lineaireAx=best donnee par le point de minimum suivant inf x2IRN12 (Ax;x)(b;x) PreuveOn designe parx0la solution deAx=b. On verie alors que 12 (A(xx0);xx0) =12 (Ax;x)12 (b;x)12 (Ax;x0) +12 (b;x0): Comme (Ax;x0) = (x;tAx0) = (x;Ax0) = (x;b) carAest symetrique 12 (Ax;x)(b;x) =12 (b;x0) +12 (A(xx0);xx0):

1.3. EXEMPLES9

On diagonaliseAqui est symetrique denie positive, on ecritx=x0+P iyiei, ou leseisont les vecteurs orthonormes qui diagonalisentA, alors 12 (Ax;x)(b;x) =12 (b;x0) +12 i=NX i=1 iy2i: L'expression ci-dessus est minimum lorsque tous lesyisont nuls, car tous lesisont strictement positifs, donc lorsquex=x0. Le resultat est demontre. RemarqueLorsque la matriceAn'est pas symetrique, l'expression ci- dessus existe. La matriceApeut alors ^etre remplacee par~A=12 (A+tA) et ce sont les proprietes de ~Aqui sont importantes et non celles deA.

On resume dans:

PropositionLe minimum de la fonction12

(Ax;x)(b;x)est unique et atteint enx0= (12 (A+At))1bsi12 (A+At)est denie positive

2. Projection sur un convexe.

SoitKun ensemble convexe ferme dans un espace de HilbertV. On appelle projection deu0surK, et on notep(u0), le point deKle plus proche deu0, soitjjp(u0)u0jj= infv2Kjjvu0jj. On note que, de la relation8v2K;jjvu0jj2 jjp(u0)u0jj2, et, plus precisement de

8v2K;82]0;1[;jjv+ (1)p(u0)u0jj2 jjp(u0)u0jj2, on tire

2jjvp(u0)jj2+ 2(vp(u0);p(u0)u0)0:

Divisant paret faisant tendrevers 0, on en deduit l'inegalite (vp(u0);p(u0)u0)08v2K: Dans le plan, cette egalite implique que (vp(u0);u0p(u0))0, c'est- a-dire l'angle entre les vecteurs joignant la projection au0et a un element quelquonque deKest obtus. Reciproquement, si cette inegalite est veriee, alors jjvu0jj2=jjvp(u0)jj2+jjp(u0)u0jj2+2(vp(u0);p(u0)u0) jjvp(u0)jj2: Il y a unicite de la projection. En eet, si on designe parv0une autre projection, on a (vv0;u0v0)0;(vp(u0);u0p(u0))0: Dans la premiere inegalite on considerev=p(u0) et dans la deuxieme on considerev=v0. Alors

10CHAPTER 1. INTRODUCTION ET EXEMPLES

(p(u0)v0;u0v0)0;(v0+p(u0);u0+p(u0))0:

Additionnant les deux egalites, on obtient

(p(u0)v0;p(u0)v0)0 ce qui impliquev0=p(u0). Il y a unicite de la projection sur un convexe. Ceci est la redemonstration du theoreme de Hahn-Banach.

On resume dans

PropositionSiKest un convexe ferme, le minimum de la distance de xaKest atteint en un unique pointp(x), qui s'appelle la projection de xsurKet qui est caracterise par l'inegalite

8y2K;(yp(x);xp(x))0:

3. Un exemple simple avec contraintes.

On veut trouver min(

12 v2cv) sous la contraintevb. Pour cela, on voit que, sibc, minvb(12 v2cv) = (12 v2cv)jv=bet sib > c, min vb(12 v2cv) = (12 v2cv)jv=c. Dans le premier cas, la contrainte est saturee, dans le deuxieme cas elle est insaturee.

4. Minimisation quadratique dans IR

2. Cet exemple est caracteristique des

methodes qui seront developpees dans le cours: il aborde les contraintes de type egalite ainsi qu'inegalite en dimension nie, dans le cas ou les expressions sont tres simples. Il aborde aussi des methodes qui seront developpees sous le nom de gradient reduit.

On introduit la fonctionnelleJ(y1;y2) =12

(y21+y22)b1y1b2y2et on cherche a resoudre les deux problemes infJ(y);a:y=a1y1+a2y2= 0 infJ(y);a1y1+a2y20 Dans le premier cas, on a plusieurs methodes a notre disposition. La plus evidente est de supposera16= 0, ainsiy1=a2a

1y2, et on se ramene a

inf 12 (1 +a21a

22)y21b2a1b1a2a

1y2 qui est atteint au pointy2=a1b2a1b1a2a

21+a22et doncy1=a2b2a1b1a2a

21+a22.

On peut simplier les expressions en veriant que, dansy2, le coecient deb2s'ecrit aveca21=(a21+a22), ainsi

1.3. EXEMPLES11

(y1;y2) = (b1;b2)a1b1+a2b2a

21+a22(a1;a2):

Cette methode n'est pas instructive, mais son resultat l'est: le minimum est obtenu au pointb+a. Le reelest nul lorsquea:b= 0. Distinguons les casb:b= 0 eta:b6= 0. Notons avant cela que le minimum absolu de la fonctionnelle se situe au pointb. Sibest dans la contrainte, alors ce minimum absolu est atteint sur la contrainte, et donc le probleme infJ;a:y= 0 admet comme solutiony=b, de m^eme que le probleme infJ;a:y0: Sibn'est pas dans la contrainte egalite, on designe parb0la projectionquotesdbs_dbs29.pdfusesText_35

[PDF] Exercices de gestion des ressources humaines-2 - Numilog

[PDF] Mecanique quantique Cours et exercices corriges - Numilog

[PDF] Correction de l 'examen de probabilités et statistiques - Julian Tugaut

[PDF] Examen final corrigé (janvier 2013)

[PDF] Série d 'exercices Finance Internationale - ResearchGate

[PDF] Cours de gestion financière (M1) Exercices corrigés Le cas

[PDF] Exercice n°1

[PDF] Réseaux de Petri

[PDF] Examen professionnel Informatique, système d 'information

[PDF] Graphes exercices et correction

[PDF] Correction examen théorie des jeux 2009-2010 - Ceremade

[PDF] Exercice n° HU 0601 - Corrigé

[PDF] 10

[PDF] 14

[PDF] Examen d analyse personnel technique (ANT) - carrieres gouv