[PDF] Optimisation cours

COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

Cité 2 fois — 4 2 3 Applications de la théorie du point selle à l'optimisation 51 4 2 4 Le cas convexe

Cours dOptimisation

2, on dira que la vitesse de convergence est quadratique Algorithmes de descente Les algorithmes 

Optimisation cours

ation (MML1E31) Notes de cours Master 1 Mathématiques et Modélisation (MM) 2017-2018

M1 MApI3 - UE OPTIMISATION Support de cours

??Fondamentaux de la recherche opérationnelle” du Master 2 MApI3 Algorithmique de l' 

Résumé dOptimisation

MI5 Master Pro 1`ere année Ceci un résumé des principaux résultats du cours d'optimisation

Cours Optimisation - université 8 Mai 1945 Guelma

PDF

Université Paris Dauphine Optimisation et - Ceremade

mention Mathématiques appliquées 1`ere année 2015-2016 Introduction L'objet de ce cours est de présenter quelques notions sur deux types de probl`emes d'optimisation :

Résumé du cours doptimisation

4 Méthodes de descente Problèmes sans contraintes 21 4 1 Principe

Correction de lexamen Master SICOM, Cours Optimisation Luc

ion de l'examen Master SICOM, Cours Optimisation Luc Pronzato, janvier 2007 PARTIE 1

[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

Optimisation (MML1E31)

Notes de cours

Master 1 Mathématiques et Modélisation (MM)

2017-2018

Bruno GALERNE

Bureau 812-F

bruno.galerne@parisdescartes.fr

Table des matières

1 Rappels et compléments de calculs différentiels

4

1.1 Cadre et notation

4

1.2 Différentielle et gradient

4

1.2.1 Applications linéaires et matrices associées

4

1.2.2 Différentielle

5

1.2.3 Gradient

5

1.2.4 Dérivation des fonctions composées

6

1.3 Différentielle d"ordre deux et matrice hessienne

6

1.4 Formules de Taylor

7

2 Problèmes d"optimisation : Existence et unicité des solutions

9

2.1 Cadre et vocabulaire

9

2.2 Existence de solutions pour les fonctions coercives et continues

10

2.3 Extremums locaux et dérivabilité

10

2.4 Ensembles convexes

12

2.5 Fonctions convexes

13

2.5.1 Définition et exemples

13

2.5.2 Caractérisation des fonctions convexes différentiables et deux fois dif-

férentiables 15

2.5.3 Problèmes d"optimisation convexes

17

2.6 Etude des fonctionnelles quadratiques

18

2.7 Exercices supplémentaires

19

3 Algorithmes de descente pour des problèmes sans contraintes

20

3.1 Forte convexité

20

3.2 Généralités sur les algorithmes de descente

22

3.2.1 Forme générale d"un algorithme de descente

22

3.2.2 Algorithmes de recherche de pas de descente

24

3.3 Algorithmes de descente de gradient

25

3.4 Méthode de Newton

29

4 Méthode du gradient conjugué

32

4.1 Description de l"algorithme et preuve de sa convergence

32

4.2 Implémentation de l"algorithme du gradient conjugué

34

4.3 Algorithme du gradient conjugué comme méthode itérative

37
2

Introduction

Ce cours est une introduction aux problèmes d"optimisation. Le cours se focalise essen- tiellement sur des problèmes d"optimisation sans contrainte en dimension finie. Après une in-

troduction des différentes notions mathématiques nécessaires (rappels de calcul différentiel,

conditions d"optimalité, convexité, etc.), une part importante est donnée à l"exposition des dif-

férents algorithmes classiques d"optimisation, l"étude théorique de leur convergence, ainsi que

la mise en oeuvre pratique de ces algorithmes. Le logiciel libre de calcul scientiffiqueOctave sera utilisé en séance de Travaux Pratiques (TP). Octave est téléchargeable gratuitement ici : https://www.gnu.org/software/octave/ Les principaux ouvrages de référence pour ce cours sont : CIARLET]Philippe G. C IARLET,Introduction à l"analyse numérique matricielle et à l"op- timisation, cinquième édition, Dunod, 1998 BOYD& VANDENBERGHE]Stephen B OYDand Lieven VANDENBERGHEConvex Opti- mization, Cambridge University Press, 2004.

Ouvrage téléchargeable gratuitement ici :

http://stanford.edu/~boyd/cvxbook/ ALLAIRE& KABER]Grégoire A LLAIREet Sidi Mahmoud KABER,Algèbre linéaire nu- mérique, Ellipses, 2002

La page web dédiée à ce cours est ici :

3

Chapitre 1

Rappels et compléments de calculs

différentiels

BOYD& VANDENBERGHE]

et le chapitre 7 de [ CIARLET]. Dans ce cours on se placera toujours sur des espaces vectoriels normés de dimensions finis que l"on identifie àRn,n>1.

1.1 Cadre et notation

netmsont des entiers supérieurs ou égaux à1. Par convention les vecteurs deRnsont des vecteurs colonnes. On noteh;ile produit scalaire canonique etk kla norme euclidienne associée. On noteMm;n(R)l"ensemble des matrices de taillemnà coefficients réelles et M n(R) =Mn;n(R)l"ensemble des matrices carrées de taillenn. La transposée d"une matriceAest notéeAT. On a donc pour tousx;y2Rn,hx;yi=xTyet par conséquent, pour toutA2 Mm;n(R),x2Rn,y2Rm, hy;Axi=hATy;xi: Remarque(Notation de la transposée).La notationATcorrespond plutôt à une convention

anglo-saxonne. Elle a été choisie pour ce polycopié car elle est plus simple à taper en L

ATEXet

est plus proche de l"opération transposée en octave, notéeA". Toutefois les étudiants sont libres

d"utiliser la notation classique tApour leurs prises notes et leurs copies d"examen.

1.2 Différentielle et gradient

1.2.1 Applications linéaires et matrices associées

On désigne parL(Rn;Rm)l"ensemble des applications linéaires deRndansRm. On iden- tifie un élément deL(Rn;Rm)à une matrice rectangulaire de taillemncorrespondant à la matrice de l"application dans les bases canoniques deRnetRm: si'2 L(Rn;Rm)alors pour toutx2Rn,'(x) =AxavecAla matrice dont les colonnes sont les images par'des vecteurs de la base canonique(e1;:::;en)de la base canonique deRn, '(x) =' nX k=1x kek! =nX k=1x k'(ek) ='(e1)'(en)0 B @x 1... x n1 C A=Ax: 4

1.2.2 Différentielle

Dans tout ce chapitre,

désigne unensemble ouvertdeRn.

Définition 1.1.Soitf:

!Rm. La fonctionfestdifférentiable au pointx2 si il existe une matricedf(x)2 Mm;n(R)telle que au voisinage dexon ait f(y) =f(x) + df(x)(yx) +kyxk"(yx) aveclimy!x"(yx) = 0,i.e.,kyxk"(kyxk) = oy!x(kyxk). Onappelledf(x)ladifférentielle defau pointx, ou encore la matrice jacobienne defau pointx. On dit quefestdifférentiable sifest différentiable en tout point de . On dit quefestcontinûment différentiablesifest différentiable et l"applicationx7!df(x)est continue. La fonction affinef(y) =f(x)+df(x)(yx)est l"approximation à l"ordre 1 defau point notef= (f1;:::;fm)Tles composantes def, alors pour tout(i;j)2 f1;:::;mgf1;:::;ng, (df(x))i;j=@fi@x j(x): Exercice 1.2.SoitAune matrice deMm;n(R)etb2Rm. Montrer que la fonctionf:Rn! R mdéfinie parf(x) =Ax+best différentiable surRnet calculer sa différentielle en tout point x2Rn. En déduire quefestC1(et mêmeC1) surRn.

1.2.3 Gradient

Dans ce cours on s"intéressera plus particulièrement à des fonctions à valeurs réelles, ce qui

correspond au casm= 1. La matrice jacobienne def: !Rest alors une matrice ligne de taille1n. La transposée de cette matrice est un vecteur deRnappelégradientdefau point xet notérf(x). Pour touth2Rn, df(x)h=rf(x)Th=hrf(x);hi:

Ainsi, pourf:

!R,fest différentiable si et seulement si il existe un vecteurrf(x)tel que f(y) =f(x) +hrf(x);yxi+kyxk"(yx)aveclimy!x"(yx) = 0: rf(x)s"interprète comme le vecteur de plus forte augmentation defau voisinage dex. En particulier,rf(x)est orthogonal au ligne de niveaux de la fonctionf. Exercice 1.3.SoitAune matrice deMn(R). Soitf:Rn!Rl"applicationf:x7!12 hAx;xi. 1. Montrer que fest différentiable surRnet déterminerrf(x)pour toutx. 2. Quelle est l"e xpressionde rfsiAest symétrique? 3.

Quel es tle gradient de l"application x7!12

kxk2? 5

1.2.4 Dérivation des fonctions composées

Théorème 1.4(Dérivation des fonctions composées).Soientf:Rn!Rmetg:Rm!Rp deux fonctions différentiables. Soith=gf:Rn!Rpla fonction composée définie par h(x) =g(f(x)). Alorshest différentiable surRnet pour toutx2Rn, dh(x) = dg(f(x))df(x):

Remarque.On peut énoncer une version locale du résultat précédent car, comme le suggère

la formuledh(x) = dg(f(x))df(x), pour quehsoit différentiable enx, il suffit quefsoit différentiable enxet quegsoit différentiable enf(x). Exemple 1.5.Déterminons le gradient de l"applicationg:Rn!Rdéfinie par g(x) =f(Ax+b) oùAest une matrice deMm;n(R),b2Rmetf:Rm!Rest une application différentiable. On ag(x) =fh(x)avech(x) =Ax+b. Commehest affine on adh(x) =Aen tout point x. On a donc d"après la règle de dérivation des fonctions composées dg(x) = df(h(x))dh(x) = df(Ax+b)A:

Doncrg(x) = dg(x)T=ATdf(Ax+b)T=ATrf(Ax+b).

1.3 Différentielle d"ordre deux et matrice hessienne

Danslecadregénéraloùf:

df:x7!df(x)est une application de l"ouvert vers l"espace vectorielL(Rn;Rm). Si cette application est elle-même différentiable enx, alors on obtient une différentielled(df)(x)() qui appartient àL(Rn;L(Rn;Rm))que l"on identifie à une application bilinéaired2f(x) : R nRn!Rmqui est symétrique d"après le théorème de Schwarz.d2f(x)est appelée la différentielle d"ordre deuxde l"applicationfau pointx.festdeux fois différentiablesi elle est différentiable sur tout .festdeux fois continûment différentiablesur , sifest deux fois dif- férentiable et si l"applicationx7!d2f(x)est continue. On noteC2( )l"ensemble des fonctions deux fois continûment différentiables.

Dans le cas oùm= 1, c"est-à-dire oùf:

!Rest à valeurs réelles,d2f(x)est une forme bilinéaire symétrique dont la matrice s"écrit r

2f(x) =@2f@x

i@xj(x)

16i;j6n:

Cette matrice est appeléematrice hessiennedefau pointx. On a alors pour tous vecteurs h;k2Rn, d

2f(x)(h;k) =hr2f(x)h;ki=kTr2f(x)h=hTr2f(x)k:

Pour ce cours on aura constamment besoin de calculer le gradient et la matrice hessienne de fonctionnellesf: !Rdeux fois différentiables. En pratique on utilise la proposition suivante. Proposition 1.6(La matrice hessienne est la différentielle du gradient).Soitf: !Rune fonction différentiable sur et deux fois différentiable au pointx2 . Alors, la matrice hes- sienner2f(x)defau pointxest la différentielle de l"application gradientx7! rf(x)au pointx. 6 Exercice 1.7.Démontrer la Proposition1.6 ci-dessus.

Il est difficile de donner une règle de dérivation des fonctions composées pour l"ordre deux.

Voici toutefois deux règles à connaître pour ce cours. Composition avec une fonction scalaire :On considèref: !Rune fonction deux fois différentiable etg:R!Rune fonction deux fois dérivable. Alors,h=gfest deux fois différentiable et r

2h(x) =g0(f(x))r2f(x) +g00(f(x))rf(x)rf(x)T:

Composition avec une fonction affine :Soitg:Rn!Rdéfinie par g(x) =f(Ax+b) oùAest une matrice deMm;n(R),b2Rmetf:Rm!Rest une application deux fois différentiable. Alorsgest deux fois différentiable et r

2g(x) =ATr2f(Ax+b)A;

formule qui s"obtient facilement en dérivant l"expressionrg(x) =ATrf(Ax+b)montrée précédemment.

1.4 Formules de Taylor

Les formules de Taylor se généralisent aux fonctions de plusieurs variables. On se limite aux fonctions à valeurs réelles. Théorème 1.8(Formules de Taylor pour les fonctions une fois dérivable).Soitf: !Rune fonction. (a)

Défini tionde la dif férentielle= F ormulede T aylor-Youngà l"ordre 1 : Si fest différentiable

enx2 , alors f(x+h) =f(x) +hrf(x);hi+khk"(h)aveclimh!0"(h) = 0. On considère maintenant un pointhfixé tel que le segment[x;x+h]soit inclus dans (b) F ormuledes accroissements finis : Si fest continue sur et différentiable sur]x;x+h[, alors jf(x+h)f(x)j6sup y2]x;x+h[krf(y)kkhk: (c) F ormulede T aylor-Maclaurin: Si fest continue sur et différentiable sur]x;x+h[, alors il existe2]0;1[tel que f(x+h) =f(x) +hrf(x+h);hi: (d) F ormulede T aylora vecreste intégral : Si f2 C1( )alors f(x+h) =f(x) +Z 1 0 hrf(x+th);hidt: 7

Preuve.On applique les formules de Taylor à la fonction'(t) =f(x+th),t2[0;1].Théorème 1.9(Formules de Taylor pour les fonctions deux fois dérivable).Soitf:

!R une fonction. (a) F ormulede T aylor-Youngà l"ordre 2 : Si fest différentiable dans et deux fois différen-quotesdbs_dbs9.pdfusesText_15