[PDF] OptiAlgo cours Une fonction f est (strictement)

View - Download OptiAlgo cours

Previous PDF

Next PDF

Optimisation, algorithmique (MML1E31)

Notes de cours

Master 1 Mathématiques appliquées

Master 1 Ingénierie mathématique appliquée aux sciences du vivant (cours optionnel)

2016-2017

Bruno GALERNE

Bureau 812-F

bruno.galerne@parisdescartes.fr

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 à l"aide du logiciel Scilab. 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 2

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:

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:

1.2.2 Différentielle

Dans tout ce chapitre,

désigne unensemble ouvertdeRn. 3

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?

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): 4

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) :Rn R n!Rmqui se trouve être symétrique.d2f(x)est appelée la différentielle d"ordre deux de l"applicationfau pointx.festdeux fois différentiablesi elle est différentiable sur tout .f estdeux fois continûment différentiablesur , sifest deux fois différentiable et si l"application x7!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:

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ère une fonctionf: !Rune fonc- tion deux fois différentiable etg:R!Rune fonction deux fois dérivable. Alors,h=gf est 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:

5

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.6(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:

Preuve.On applique les formules de Taylor à la fonction'(t) =f(x+th),t2[0;1].Théorème 1.7(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- tiable enx2 , alors f(x+h) =f(x) +hrf(x);hi+12 hr2f(x)h;hi+khk2"(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 généralisée : Si f2 C1( )etfest deux fois différentiable sur]x;x+h[, alors jf(x+h)f(x) hrf(x);hij612 sup y2]x;x+h[kr2f(y)kMn(R)khk2: oùk kMn(R)désigne la norme subordonnée des matrices pour la norme euclidienne. (c)

F ormulede T aylor-Maclaurin: Si f2 C1(

)etfest deux fois différentiable sur]x;x+h[, alors il existe2]0;1[tel que f(x+h) =f(x) +hrf(x);hi+12 hr2f(x+h)h;hi: (d) F ormulede T aylora vecre steintégral : Si f2 C2( )alors f(x+h) =f(x) +hrf(x);hi+Z 1 0 (1t)hr2f(x+th)h;hidt: 6

Chapitre 2

Problèmes d"optimisation : Existence et

unicité des solutions La référence principale pour ce chapitre est le chapitre 8 de [

CIARLET].

2.1 Cadre et vocabulaire

On appelproblème d"optimisationtout problème de la forme

Trouverx?tel quex?2Uetf(x?) = minx2Uf(x);

oùUest une partie donnée deRnetf:Rn!Rest une fonction donnée que l"on appellefonc- tionnelledu problème d"optimisation. Le but de l"optimisation est de proposer des algorithmes permettant d"approcher les solutionsx?au sens où, partant d"un vecteur initialx(0)quelconque, on construit explicitement une suite de vecteurs(x(k))k>0convergeant vers une solutionx?. Le problème d"optimisation est ditsans contraintessiU=Rnetsous-contraintessinon. On dit que le problème estconvexesifetUsont convexes. et de dimension finie. On établira dans ce chapitre des conditions d"existence et d"unicité des solutions de pro-

blème d"optimisation. Dans les chapitres suivants, on s"intéressera à l"élaboration d"algorithmes

et de dimension finie.

Bien sûr, les méthodes développées dans ce cours permettent également de trouver les va-

leurs maximales de fonctionsf. Pour cela il suffit de remplacerfparfpuisque max x2Uf(x) = minx2Uf(x): Extremums des fonctions réellesSoitf:U!R, oùURn. On dit que la fonctionf admet en un pointx2Uunminimum local(respectivement unmaximum local) s"il existe un " >0tel que pour touty2U\B(x;"),f(y)>f(x)(resp.f(y)6f(x)). On dit que la fonction admet unextremum localenxsi elle admet soit un minimum soit un maximum local enx. Par abus de langage, on dira quexest un minimum local pour dire que la fonctionfadmet un minimum local enx. 7 On dit qu"un minimum localxest strict s"il existe un voisinage s"il existe un" >0tel que pour touty2U\B(x;"),f(y)> f(x). On définit de même la notion de maximum strict. Enfin, on dit qu"un minimumxestglobalsi pour touty2U,f(y)>f(x). SiWU, on dira qu"un minimumx2West global surWsi pour touty2W,f(y)>f(x). On défini de même la notion de maximum global.

2.2 Existencedesolutionspourlesfonctionscoercivesetconti-

nues La première question concernant un problème d"optimisation est celle de l"existence d"une solution. Si on cherche à minimiser une fonctionf:URn!R, alors il est bien connue que siUest compact (i.e.fermé et borné) la fonctionfest bornée et atteint ses bornes surU. Elle admet donc au moins un minimumx?2U. La notion de fonction coercive permet d"étendre ce type de raisonnement pour des fonctions définies sur des domaines non bornés. Définition 2.1(Fonctions coercives).Une fonctionf:Rn!Rest ditecoercivesi lim kxk!+1f(x) = +1: Théorème 2.2.SoientUune partie non vide fermée deRnetf:Rn!Rune fonction continue, coercive si l"ensembleUest non borné. Alors il existe au moins un élémentx?2U tel que f(x?) = infx2Uf(x): Preuve.Soitx0un point quelconque deU. La coercivité defentraîne qu"il existe un réelr >0 tel que kxk>r)f(x)> f(x0): Donc, infx2Uf(x) = inf x2U\B(0;r)f(x): Comme l"ensembleU\B(0;r)est fermé et borné et quefest continue,fest bornée et atteint ses bornes sur le compactU\B(0;r), ce qui assure l"existence d"un minimum dansU(qui est inclus dansU\B(0;r)).2.3 Extremums locaux et dérivabilité On va maintenant chercher à caractériser les minimums locaux des fonctions différentiables.

Dans toute la suite du chapitre

désigne un sous-ensemble ouvert deRn. Théorème 2.3(Condition nécessaire d"extremum local).Soitf: !Rune fonction à valeurs réelles. Si la fonctionfadmet un extremum local en un pointx2 et si elle est différentiable en ce point, alorsquotesdbs_dbs33.pdfusesText_39

[PDF] optimisation quadratique sous contrainte linéaire

[PDF] optimisation convexe pdf

[PDF] fonction convexe plusieurs variables

[PDF] modélisation et simulation d'un moteur ? courant continu matlab

[PDF] modélisation mcc

[PDF] simulation mcc simulink

[PDF] asservissement et regulation de vitesse d'un moteur a courant continu

[PDF] modélisation d'un moteur ? courant continu

[PDF] equation differentielle moteur courant continu

[PDF] schéma bloc moteur ? courant continu

[PDF] commande pid d'un moteur ? courant continu pdf

[PDF] modélisation machine asynchrone simulink

[PDF] onduleur triphasé matlab

[PDF] cours de modélisation financière sous excel

[PDF] modélisation financière pdf