Eléments danalyse et doptimisation convexe.
Dans ce chapitre nous présentons quelques propriétés remarquables des fonctions convexes. Elle permettront de construire des algorithmes de minimisation dans
Optimisation convexe
Nous verrons qu'en pratique certains algorithmes d'analyse convexe peuvent s'appliquer `a des fonctions F non convexes mais que le résultat de ces algorithmes
´Eléments danalyse convexe
L'enveloppe convexe de E est l'intersection de tous les sous-ensembles convexes de Rd qui contiennent E. On la note co E : co E = ?{. C ? C (Rd) ?? E ? C}
Diagnostics différentiels des ECG avec un susdécalage du segment
Une forme convexe en haut est plus en faveur d'une pathologie coronarienne surtout en cas d'atteinte inférieure. Les définitions de l'élévation du segment ST
Fonctions convexes
Soit I un intervalle de R et f : I ? R une application. Notons Cf sa courbe représentative. Définition géométrique : f est dite convexe (resp. concave).
Analyse convexe et quasi-convexe; applications en optimisation
17 mai 2002 Pour l' ?etude des fonctions quasi-convexes deux approches sont adopt?ees : une approche analytique via un sous-diff?erentiel g?en?eralis?e
Optimisation des fonctions convexes
TH5 : Soit ? un ouvert convexe de IRn et f une fonction de ? sur IR. 1) Si f est différentiable sur ? alors f est convexe si et seulement si
J . -. ~.
flexion en T.T.A. ;. - que lorsqu'on mobilise une surface convexe. (mobile) sur une surface concave (fixe) le glissement qui s'induit est en sens inverse du.
Cours Apprentissage - ENS Math/Info Analyse Convexe
17 oct. 2014 aspects seront vus dans le cours d'apprentissage : l'analyse convexe (propriétés des fonctions et probl`emes d'optimisation convexes) et ...
COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin
On appelle fonction elliptique une fonction f : IRn ? IR de classe C1 et fortement convexe. 15. Page 16. 2.2.2 Exemples des fonctions convexes strictement
[PDF] Chapitre1 : Fonctions convexes
Alors f est convexe si et seulement si : (2) Tout arc de sa courbe C est sous la corde correspondante Démonstration : La traduction rigoureuse de la condition
[PDF] Fonctions convexes
Soit I un intervalle de R et f : I ? R une application Notons Cf sa courbe représentative Définition géométrique : f est dite convexe (resp concave)
[PDF] Fonctions convexes 1 Dimension 1
Une fonction f est dite (strictement) concave si ?f est (strictement) convexe – Le nombre ?x + (1 ? ?)y ? ? [0 1] est une combinaison convexe de x et y
[PDF] Eléments danalyse et doptimisation convexe
19 fév 2020 · Dans ce chapitre nous présentons quelques propriétés remarquables des fonctions convexes Elle permettront de construire des algorithmes de
[PDF] Analyse Convexe Cours M1 (4M057) - » Tous les membres
L'objectif de ce cours de fournir les fondements de l'analyse convexe ses implications en méthodes algorithmiques et ses applications vers le traitement des
[PDF] Fonctions convexes - Irif
Une fonction f : R ? R est dite convexe sur [a b] si la corde prise entre a et b est au-dessus du graphe de f sur tout l'intervalle [a b]
[PDF] Chapitre 12 Ensembles convexes polytopes et poly`edres
Ensembles convexes polytopes et poly`edres 12 1 Propriétés algébriques Définition 12 1 (Ensemble convexe) Un sous-ensemble C de Rn est dit convexe si
[PDF] CONVEXITÉ - maths et tiques
I Fonction convexe et fonction concave Vidéo https://youtu be/ERML85y_s6E Définitions : Soit une fonction f dérivable sur un intervalle I
[PDF] Convexité en optimisation convexité forte
Rappelons que toute fonction convexe possède une régularité minimale en dimension finie • Si f est une fonction convexe définie sur un ouvert convexe ? de
[PDF] CONVEXITÉ - Christophe Bertault
Fonction convexe : On dit que f est convexe si son graphe est situé en-dessous de toutes ses cordes i e si : ?x y ? I ?? ? [0 1] f (1 ? ?) x + ?y ?
![COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin](https://pdfprof.com/Listes/17/57779-17cours-optim-M1-sitn.pdf.pdf.jpg)
COURS OPTIMISATION
Cours en Master M1 SITN
Ionel Sorin CIUPERCA
1Table des matières
1 Introduction 4
2 Quelques rappels de calcul différentiel, analyse convexe et extremum 5
2.1 Rappel calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Quelques Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Quelques rappels sur le calcul différentiel . . . . . . . . . . . . . . . 6
2.1.3 Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 Quelque rappels sur le matrices carrées réelles . . . . . . . . . . . . 11
2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Fonctions convexes, strictement convexes, fortement convexes . . . . 11
2.2.2 Exemples des fonctions convexes, strictement convexes et fortement
convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.3 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Conditions nécéssaires et suffisantes de minimum . . . . . . . . . . . . . . 17
2.4 Existence et unicité d"un point de minimum . . . . . . . . . . . . . . . . . 21
3 Optimisation sans contraintes 23
3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1 Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2 Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 27
3.2 Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Méthodes de gradient à pas optimal . . . . . . . . . . . . . . . . . . 29
3.2.2 Autres méthodes du type gradient . . . . . . . . . . . . . . . . . . . 30
3.3 La méthode des gradients conjugués . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.2 Cas d"une fonctionJquelconque . . . . . . . . . . . . . . . . . . . 38
4 Optimisation avec contraintes 39
4.1 Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . 40
4.2 Optimisation sous contraintes d"inégalités . . . . . . . . . . . . . . . . . . . 41
4.2.1 Conditions d"optimalité de premier ordre : multiplicateurs de Karush-
Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.2 Théorie générale du point selle . . . . . . . . . . . . . . . . . . . . . 49
24.2.3 Applications de la théorie du point selle à l"optimisation . . . . . . 51
4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 53
4.3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.2 Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.3 Méthodes de pénalisation exterieure . . . . . . . . . . . . . . . . . . 59
4.3.4 Méthode d"Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3Chapitre 1
Introduction
En généraloptimisersignifie le fait de chercher une configuration optimale d"un sys-tème, c"est à dire, chercher la meilleure configuration parmi tous les configurations possibles
du système et ceci, par rapport à un critère donné. Pour décrire (et éventuellement résoudre) un problème d"optimisation nous utilisons la modélisation mathématique. La démarche de modélisation comporte 3 étapes : Etape 1.Choisir lesvariables de décision, qui sont les composantes du système sur lesquelles on peut agir. On supposera dans ce cours qu"il y a un nombre finit notén2INde variables de décision, chacune de ces variables étant un nombre réel. Alors les variables
de décision seront représentés par un vecteurx= (x1;x2;xn)T2IRn(vecteur colonne). Etape 2.Décrirel"étatdu système, étant donnée une configuration des variables de décision. Ceci revient mathématiquement à se donner une fonctionJ:IRn!IRqui s"appellefonction objectifoufonction coûtet que nous voulons rendre la plus petite possible ou la plus grande possible. Etape 3.Décrire lescontraintesque les variables de décision satisfont. Ceci revient à définir un ensemble de contraintesUIRnet imposer d"avoirx2U. Pour résumer on peut dire que pour décrire un problème d"optimisation on se donne1. Une fonctionJ:IRn7!IR(fonction coût)
2. Un ensembleUIRn(ensemble des contraintes)
On cherche à minimiserJsurU, c"est à dire, on cherchex2Utel queJ(x) = minx2UJ(x)
ou équivalentJ(x)J(x);8x2U:
Motivation et exemples pratiques :en classe
4Chapitre 2
Quelques rappels de calcul différentiel,
analyse convexe et extremum2.1 Rappel calcul différentiel
2.1.1 Quelques Notations
1. Pour toutn2IN;IRndésigne l"espaceeuclidienIRIRIR( "produitnfois").
En général un vecteurx2IRnsera notéx= (x1;x2;xn)T(vecteur colonne).2. On notee1;e2;enles éléments de labase canoniquedeIRn, oùeiest le vecteur
deIRndonné par : (ei)j=ij=0sij6=i1sij=i;8i;j= 1;2n(2.1)
(ij=symboles deKronecker).3. Pour tousx;y2IRnon note par< x;y >2IRleproduit scalairedexety, qui
est donné par < x;y >=nX i=1x iyi: Deux vecteursx;y2IRnsontorthogonaux(on noterax?y) si< x;y >= 0.4. Pour toutx2IRnon note parkxk 0lanorme euclidiennedex, donnée par
kxk=p< x;x >=v uutn X i=1x 2i: Rappellons lespropriétés d"une norme(donc aussi de la norme euclidienne) : i)kxk=jjkxk 82IR;8x2IRn ii)kx+yk kxk+kyk 8x;y2IRn iii)k0k= 0etkxk>0six2IRn f0g. 55. Pour tousx2IRnetr >0on notera parB(x;r)laboule ouvertedu centrexet
rayonr, donnée parB(x;r) =fy2IRn;kyxk< rg:
6. Si x(k) k2INest une suite dansIRnetxest un élément deIRnon dit quex(k) convergeversx(notéex(k)!x) sikx(k)xk !0. Rappellons que nous avons :x(k)!xsi et seulement six(k) i!xienIRoùx(k) i(respectivementxi) est lai-ème composante dex(k)(respectivementx).7. SoitUIRn.
- On définitl"intérieurdeUcomme l"ensemble des élémentsx2Upour lesquels il exister >0tel queB(x;r)U. - On dit queUestouvertsi8x2U9r >0tel queB(x;r)U. - On dit queUestfermési pour tout suitefx(k)g Utel quex(k)!x2IRnon ax2U.8. Sia;b2IRnon note[a;b]le sous-ensemble deIRndonné par
[a;b] =fa+t(ba)(1t)a+tb; t2[0;1]g: L"ensemble[a;b]est aussi appelléle segmentreliantaàb.Remarques :
[a;b] = [b;a](Exo!) Sia;b2IRaveca < bon retrouve la notation[a;b]pour l"intervalle des nombres x2IRtels queaxb.9. Rappellons aussi l"inégalité de Cauchy-Schwarz :
j< x; y >j kxk kyk 8x;y2IRn:2.1.2 Quelques rappels sur le calcul différentiel
On considère dans cette partiemetndeux nombres deN(très souvent dans ce cours on auram= 1).1. SoitUun sous-ensemble deIRnetf:U7!IRm.
On dit quefestcontinueenx2Usif(x(k))!f(x)pour toute suitex(k)U telle quex(k)!x. On dit quefest continue surUsifest continue en tout pointx2U. Remarque :Sif= (f1;f2;fm)avecf1;f2;fm:U!IRalorsfest continu enx2Usi et seulement sif1;f2;fmsont continues enx.Pour tous les poins suivants on va supposer que
est un ouvert de IRnetfest une fonctionf: !IRm. 62. Pour toutx2
eth2IRnon note (quand9) @f@h (x) = limt7!01t [f(x+th)f(x)] (c"est ladérivée directionnelledefenxdans la directionh).Remarques :
i)@f@0(x) = 0: ii)Sif= (f1;f2;fn)T2IRnavecf1;f2;fm: !IRalors @f@h (x) =@f1@h (x);@f2@h (x);@fm@h (x) T3. Pour toutx2
et touti2 f1;2;;ngon note (quand9) @f@x i(x) =@f@e i(x) = limt7!01t [f(x+tei)f(x)] (c"est ladérivée partielledefenxpar rapport à la variablexi.)En particulier, sin= 1on notef0(x) =@f@x
1(x) = limt!01t
[f(x+t)f(x)] = lim y!x1yx[f(y)f(x)]4. Pour toutx2
on note (quand9)Jf(x) =lamatrice Jacobiennedefenxqui est un élément deMm;n(IR)définie par (Jf(x))ij=@fi@x j(x)2IR8i= 1;m;8j= 1;n: Legradientdefenxest défini comme la transposée de la matrice Jacoblenne de fenx: rf(x) = (Jf(x))T2 Mn;m(IR): Remarque importante :Dans le cas particulierm= 1(doncf: !IR) alors en considérant tout élément deMn;1comme un vector colonne deIRn, on va dire que rf(x)est le vecteur colonne rf(x) =@f@x 1@f@x2;@f@x
n T 2IRn:Rappellons la formule :
@f@h (x) =8h2IRn:
5. Sif:
!IR(icim= 1) on dit qu"un pointx2 est unpoint critiquepour la fonctionfsirf(x) = 0. 76. Pour toutx2
eti;j2 f1;2;ngon note (quand9) 2f@x i@xj(x) =@@x i @f@x j (x)2IRm dérivée partielle à l"ordre 2.Notation :pouri=jon écrira@2f@
2xi(x)à la place de@2f@x
i@xi(x).7. Dans le casm= 1on note pour toutx2
(quand9)r2f(x) =la matrice carrée 2 M n(IR)donnée par r2f(x) ij=@2f@x i@xj(x);8i;j= 1;2;n: (r2f(x)s"appelle aussila matrice Hessiennedefenx).8. On dit quefest de classeCpsur
(on noteraf2Cp( )) pourp= 1oup= 2 si les dérivées partielles desfjusqu"à l"ordrepexistent et sont continues sur . Par extension on dit quefest de classeC0sur sifest continue sur9. On a le Théorème de Schwarz : sif2C2(
)alors 2f@x i@xj(x) =@2f@x j@xi(x)8x2 ;8i;j= 1;n (c"est à dire, la matricer2f(x)est symmétrique).10. (Lien entrer;Jfetr2) : Sif:
!IRest de classeC2alors r2f(x) =Jrf(x) =rJf(x)8x2
(la matrice Hessienne defest le Jacobien du gradient defou le gradient de laJacobienne def).
11. (Composition) Soient
IRn; UIRmavec
;Uouvertsf: !IRm; g:U! IR pavecp2INetf( )U. Considérons la fonction composéegf: !IRp. i)Sifetgsont continues alorsgfest continue. ii)Sifetgsont de classeC1alorsgfest de classeC1et on a l"égalité matricielle J gf(x) =Jg(f(x))Jf(x)8x2Conséquences :
i)Sim=p= 1alors r(gf)(x) =g0(f(x))rf(x): i)Sin=p= 1alors (gf)0(x) =Proposition 2.1.Nous avons
r2f(x)h=r8x2
;8h2IRn: où le premier gradient dans le membre de droite de l"égalité est considéré par rapport à la
variablex.Démonstration.On a :
@@x i1. Sif:IRn!IRmest une fonctionconstantealorsrf= 0etJf= 0. On a aussi
évidementr2f= 0dans le casm= 1.
2. Soitf:IRn!IRmdéfinie par
f(x) =Ax8x2IRn oùA2 Mm;n(IR)est une matrice donné (c"est à dire,fest une fonctionlinéaire).Il est facile de voir qu"on a
J f(x) =A8x2IRn (la matrice Jacobienne est constante). Dans la cas particulierm= 1une fonction linéaire générale peut être écrite sous la forme f(x) =< a; x >8x2IRn oùa2IRnest un vecteur donné. Il est clair alors que rf=a et r2f= 0:
3. Soitf:IRn!IRdonnée par
f(x) =< Ax; x >8x2IRn; oùA2 Mn(IR)est un matrice carrée, réelle, de taillen(c"est à dire,fest laforme quadratiqueassociée à la matriceA). Alors pour unp2 f1;2;ngfixé, on peutécrire
f(x) =nX i;j=1A ijxixj=Appx2p+nX j=1;j6=pA pjxpxj+nX i=1;i6=pA ipxixp+nX i;j=1;i6=p;j6=pA ijxixj 9 ce qui nous donne @f@x p= 2Appxp+nX j=1;j6=pA pjxj+nX i=1;i6=pA ipxi=nX j=1A pjxj+nX i=1A ipxi= (Ax)p+(ATx)p:Nous avons donc obtenu :
rf(x) = (A+AT)x;8x2IRn:En utilisant la formuler2f=Jrfon déduit
r2f(x) =A+AT;8x2IRn
(donc la hessienne defest constante). Remarque :En particulier, siAestsymmétrique(c"est à direA=AT) alors r< Ax; x >= 2Ax;8x2IRn: r2< Ax; x >= 2A;8x2IRn:
2.1.3 Rappel formules de Taylor
Proposition 2.2.(sans preuve)
SoitIRnouvert,f:
7!IR;a2
eth2IRntels que[a;a+h] . Alors :1. Sif2C1(
)alors i)f(a+h) =f(a) +R10 dt
(formule de Taylor à l"ordre 1 avec reste intégral). ii)f(a+h) =f(a)+2. Sif2C2(
)alors i)f(a+h) =f(a)+0(1t) dt
(formule de Taylor à l"ordre 2 avec reste intégral). ii)f(a+h) =f(a)+2.1.4 Quelque rappels sur le matrices carrées réelles
Soitn2INetA2 Mn(IR)une matrice carrée réelle.1. SoitC=l"ensemble des nombres complexes. On rappelle que2Cest unevaleur
propredeAs"il existex2Cnavecx6= 0tel queAx=x; on appellexvecteur propredeAassocié à la valeur propre.2. On dit que la matriceAestsemi-définie positivesi< Ax;x >0;8x2IRn.
On dit queAestdéfinie positivesi< Ax;x > >0;8x2IRnavecx6= 0.3. Rappellons que siAest symétrique alors toutes les valeurs propres deAsont réelles;
en plus il existenvecteurs propres deAappartenant àIRnformant une base ortho- normée enIRn.4. Supposons que la matriceAest symétrique. Alors
< Ah; h >minkhk2;8h2IRn oùmin2IRest la plus petite valeur propre deA. Rémarquons que l"inégalité précédente devient égalité sihest un vecteur propre associé à la valeur propremin.5. Supposons queAest symétrique. AlorsAest semi-définie positive si et seulement si
min0etAest définie positive si et seulement simin>0.6.Abréviation :La notation SDP pour une matrice carrée rélle signifie "matrice sy-
métrique et définie positive" (elle ne signifie pas "matrice semi-définie positive" !).2.2 Convexité
2.2.1 Fonctions convexes, strictement convexes, fortement convexes
Définition 2.3.Un ensembleUIRnest ditconvexesi8x;y2Uon a[x;y]U (quelque soit deux points dansU, tout le segment qui les unit est dansU). Définition 2.4.SoitUIRnun ensemble convexe etf:U!IRune fonction.1. On dit quefestconvexesurUsi
f(ty+ (1t)x)tf(y) + (1t)f(x);8x;y2U;8t2[0;1]2. On dit quefeststrictement convexesurUsi
f(ty+ (1t)x)< tf(y) + (1t)f(x);8x;y2Uavecx6=y;8t2]0;1[:3. On dit quefestfortement convexesurUs"il existe >0tel que
f(ty+ (1t)x)tf(y) + (1t)f(x)t(1t)kyxk2;8x;y2U;8t2[0;1] 114. On dit quefestconcave(respectivementstrictement concave, respectivement
fortement concave) sifest convexe (respectivement strictement convexe, res- pectivement fortement convexe). Remarque :Il est facile de voir qu"on a : fortement convexe=)strictement convexe =)convexe. Les réciproques ne sont pas vraies en général; par exemple une application affinef(x) =Ax+best convexe (et aussi concave) mais elle n"est pas strictement convexe (ni strictement concave) donc elle n"est pas fortement convexe (ni fortement concave).On a le résultat utile suivant :
Proposition 2.5.SoitUIRnun ensemble convexe,p2IN,f1;f2;;fp:U!IR des fonctions convexes et 1; 2;; ndes constantes strictement positives.Posonsf=
1f1+ 2f2+ pfp. Alors on a :1. La fonctionfest convexe (donc toute combinaison linéaire avec des coefficients stric-
tement positifs de fonctions convexes est convexe).2. Si au moins l"une des fonctionsf1;;fpest strictement convexe alorsfest stric-
tement convexe.3. Si au moins l"une des fonctionsf1;;fpest fortement convexe alorsfest fortement
convexe.Démonstration.Laissée en exercice!Il est en général difficile de vérifier la convexité d"une fonction en utilisant uniquement
la définition (essayez avecf(x) =x2ou avecf(x) =x4!) Les propositions suivantesdonnent des critères de convexité, convexité stricte et convexité forte, plus faciles à utiliser
que les définitions respectives. Proposition 2.6.(caractérisation de la convexité) SoitIRnouvert,U
avecUconvexe etf:7!IR une fonction de classeC1.
Alors a)Les 3 propositions suivantes sont équivalentes :1.fest convexe surU
2. f(y)f(x)+3.rfestmonotone surU, c"est à dire
1) =)2) :Supposonsfconvexe; la définition de la convexité peut s"écrire
f(x+t(yx))f(x)t[f(y)f(x)] En fixantx;yen divisant partet en faisantttendre vers 0 (ce qui est possible cart2[0;1]) on obtient 2).2) =)3) :De 2) on déduit
f(y)f(x)+3) =)1) :Soientx;y2Ufixés. On introduit la fonctiong:I!IRdéfinie par
t2I!g(t) =f(ty+ (1t)x)2IRquotesdbs_dbs33.pdfusesText_39[PDF] primitive terminale sti2d
[PDF] tableau dérivée sti2d
[PDF] calcul primitive ti 82
[PDF] ti 89 probabilité
[PDF] loi normale ti 89
[PDF] equation differentielle t.i 89
[PDF] règle de dérivation
[PDF] fonction valeur absolue dérivable en 0
[PDF] primitive valeur absolue
[PDF] dérivation linguistique
[PDF] dérivation définition
[PDF] le dernier jour d'un condamné analyse chapitre par chapitre
[PDF] le dernier jour dun condamné résumé chapitre par chapitre en arabe
[PDF] le dernier jour dun condamné séquence pédagogique pdf