Dans ce cours on se placera toujours sur des espaces vectoriels normés de On dit que le problème est convexe si f et U sont convexes Dans ce cours Enfin, on dit qu'un minimum x est global si pour tout y ∈ U, f(y) ⩾ f(x) admet donc au moins un minimum x⋆ ∈ U La notion de fonction coercive permet d' étendre ce
| Previous PDF | Next PDF |
[PDF] Optimisation dune fonction dune variable
Définition et propriétés d'une fonction convexe C Nazaret On dit que f admet un minimum (resp maximum ) global toujours vérifiée pour x = y et λ ∈]0;1[
[PDF] Optimisation des fonctions convexes
TH6 : Soit C un convexe de IRn, f une fonction convexe de C sur IR et a ∈ C, alors 1) un minimum local est un minimum global ; 2) si f est de classe C1 sur C et si
[PDF] Note de convexité
22 nov 2019 · Prouver que pour un entier n ∈ N∗ et une fonction convexe f on a ∀(x1, On a toujours l'inégalité de Alors f admet un minimum global
[PDF] LEÇON 219 - EXTREMUMS : EXISTENCE, CARACTÉRISATION
Fonctions convexes 8 4 2 fonction soit strictement convexe : cette propriété est d'ailleurs utilisé dans le premier x ÞÑ sinpxq admet un minimum global non strict en ¡π 2 La démonstration de ce théorème tient toujours si on rem-
[PDF] Fonctions convexes
Preuve En remplaçant éventuellement f par −f on peut toujours supposer f croissante 3) Soit f une fonction convexe sur l'intervalle I et a, b, c trois éléments de cet intervalle un minimum en un point a de l'intérieur de I est que f (a) = 0 L'intérêt de la proposition suivante réside surtout dans sa preuve qui est globale
[PDF] COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin
2 2 2 Exemples des fonctions convexes, strictement convexes et fortement convexes 2 3 Conditions nécéssaires et suffisantes de minimum 17 On dit que u∗ est un point de minumum absolu (ou global) de f sur U si f( u) ≥ f(u∗), ∀u Ces noms viennent du fait qu'on cherchera toujours à avoir ( entre
[PDF] Fonctions convexes 1 Dimension 1 - Institut de Mathématiques de
Tout ce que vous avez toujours voulu savoir sans jamais oser le demander Ainsi, une fonction est convexe si et seulement si la courbe Cf est située en- dessous de f admet des dérivées à gauche et à droite en tout point de I et on a De plus, par hypothèse 0 est un minimum local de ϕ et donc par l'inégalité des pentes
[PDF] OptiAlgo cours
Dans ce cours on se placera toujours sur des espaces vectoriels normés de On dit que le problème est convexe si f et U sont convexes Dans ce cours Enfin, on dit qu'un minimum x est global si pour tout y ∈ U, f(y) ⩾ f(x) admet donc au moins un minimum x⋆ ∈ U La notion de fonction coercive permet d' étendre ce
[PDF] Convexité en optimisation, convexité forte
Rappelons que toute fonction convexe possède une régularité minimale en dimension finie • Si f est 1 tout minimum local est un minimum global 2 si f est Démontrons à présent le théorème en admettant le lemme technique ci- dessus
[PDF] Fonctions convexes - Inria
est une partie de E, par le problème sans contrainte équivalent min{ ˜f(x) : x ∈ E}, En tout point où elle prend une valeur finie, une fonction convexe admet des différentiabilité directionnelle, qui est toujours vérifiée par les fonctions convexes, Comme souvent en analyse convexe, on obtient une propriété globale (la
[PDF] une fonction convexe n'a qu'un nombre fini de minima
[PDF] dérivabilité d'une fonction exercices corrigés
[PDF] montrer que f est dérivable sur r
[PDF] montrer qu'une fonction n'est pas dérivable en un point
[PDF] fonction continue sur un compact atteint ses bornes
[PDF] majoré minoré suite
[PDF] matrice diagonalisable exercice corrigé
[PDF] exemple dossier de synthèse bac pro sen tr
[PDF] rapport de stage terminal bac pro eleec pdf
[PDF] rapport de synthèse bac pro sen
[PDF] rapport de synthèse bac pro sen avm
[PDF] endomorphisme nilpotent exercice corrigé
[PDF] endomorphisme nilpotent problème
[PDF] etude de cas rapport de stage bac pro sen
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.frIntroduction
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 2Chapitre 1
Rappels et compléments de calculs
différentielsBOYD& 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. 3Dé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): 4Remarque.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 cetteapplication 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 r2f(x) =@2f@x
i@xj(x)16i;j6n:
Cette matrice est appeléematrice hessiennedefau pointx. On a alors pour tous vecteurs h;k2Rn, d2f(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 r2h(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 r2g(x) =ATr2f(Ax+b)A:
51.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: 6Chapitre 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 formeTrouverx?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, alors rf(x) = 0(ou encoredf(x) = 0):Exercice 2.4.
81.Prouv erle Théorème 2.3 en considérant l"application ':t7!f(x+th)pour un vecteur
h2Rnquelconque. 2. Montrer que la conclusion du théorème est f aussesi n"est pas un ouvert. 3. Montrer que la réciproque du théorème est f ausse: rf(x) = 0n"implique pas quexsoit un extremum local. On dit qu"un pointxest unpoint critiquede la fonctionnellefsirf(x) = 0.On s"intéresse maintenant aux conditions nécessaires et suffisantes faisant intervenir la dé-
rivée seconde. Théorème 2.5(Condition nécessaire de minimum local pour la dérivée seconde).Soitf: