[PDF] LICENCE 3 MATHEMATIQUES – INFORMATIQUE

View - Download LICENCE 3 MATHEMATIQUES – INFORMATIQUE

Previous PDF

Next PDF

LICENCE 3 MATHEMATIQUES - INFORMATIQUE.

MATHEMATIQUES GENERALES.

L3MiMG.

Expédition dans la semaine n°EtapeCode UEN° d'envoi de l'UE

92L3MATSMI5U4T5

Nom de l'UE : Analyse numériqueet optimisation

Le cours contient 3 chapitres (systèmes linéaires, systèmes non linéaires, optimisation). Pour chaque semaine, il est

proposé d'étudier une partie du cours, de faire des exercices (corrigés) et, éventuellement, de réaliser un TP en

python. Les TP sont fortement conseillés mais non obligatoires. Deux devoirs sont à rendre afin de bénéficier d'une

note de contrôle continu. note finale=max(note-examen, 1/3(2 note-examen + note-contrôle-continu)). - Contenu de l'envoi : Polycopié, chapitre 3 (optimisation) - Guide du travail à effectuer

Semaine 1 :

Etudier les paragraphes 3.1 et 3.2 (optimisation sans contrainte) et 3.4 (optimisation avec contrainte)

Ces paragraphes font aussi partie du cours de calcul différentiel et optimisation

Exercices proposés (avec corrigés) :

110 (exemples), 112 (fonctions quadratiques) et 115 (complément de Schur)

Semaine 2 :

Etudier les paragraphes 3.3.1 (méthodes de descente) et 3.3.2 (algorithme du gradient conjugué, GC)

Exercices proposés (avec corrigés) :

117 (exemple), 118 (algorithme du gradient à pas optimal) et 119 (Jacobi et optimisation)

Semaine 3 :

Etudier le paragraphe 3.3.3 (Newton)

Exercice proposé (avec corrigé) : 127 (Polak-Ribière)

Semaine 4 :

Etudier les paragraphe 3.4 et 3.5 (optimisation avec contrainte) Exercice proposé (avec corrigé) : 139 (Uzawa)

Le corrigé du deuxième devoir sera, à la fin du mois de mars, sur le site du télé-enseignement et sur

site web indiqué ci-dessous-Coordonnées de l'enseignant responsable de l'envoi T. Gallouet, CMI, 39 rue Joliot Curie, 13453 marseille cedex 13 email : thierry.gallouet@univ-amu.fr Vous pouvez aussi consulter la page web:http://www.i2m.univ-amu.fr/~gallouet/tele.d/anum.d et me poser des questions par email

A i x M a r s e i l l e U n i v e r s i t é - C e n t r e d e T é l é - E n s e i g n e m e n t S c i e n c e sCase 35. 3, place Victor Hugo. 13331 Marseille Cedex 03.

http://www.ctes.univ-provence.fr P o u r r a p p r o c h e r l a c o n n a i s s a n c e

Chapitre 3Optimisation3.1 Définitions et rappels3.1.1 Extrema, points critiques et points selle.L"objectif de ce chapitre est de rechercher des extrema, c"est-à-dire des minima ou des maxima d"une fonction

f?C(IRn,IR)avec ou sans contrainte. Notons que la recherche d"un minimum ou d"un maximum implique que

l"on ait une relation d"ordre, pour pouvoir comparer les valeurs prises parf. On insiste donc bien sur le fait que

la fonctionfest à valeurs dansIR(et non pasIRn, comme dans le chapitre précédent). Rappelons tout d"abord

quelques définitions du cours de calcul différentiel. Définition 3.1(Extremum d"une fonction).SoitEun espace vectoriel normé etf:E→IR. On dit que¯xest un minimum local defs"il existe un voisinageVde¯xtel que De même, on dit que¯xest un maximum local defs"il existe un voisinageVde¯xtel que f(¯x)≥f(x),?x?V. On dit que¯xest un extremum local defsi c"est un minimum local ou un maximum local.

On dit que¯xest un minimum global defsi

De même, on dit que¯xest un maximum global defsi f(¯x)≥f(x),?x?E. On dit que¯xest un extremum global defsi c"est un minimum global ou un maximum global. Le problème d"optimisation sans contrainte s"écrit : ?Trouver¯x?IRntel que : Le problème d"optimisation avec contrainte s"écrit : ?Trouver¯x?Ktel que : 207

3.1. DÉFINITIONS ET RAPPELSCHAPITRE 3. OPTIMISATION

oùK?IRnetK?= IRnL"ensembleKoù l"on recherche la solution est donc l"ensemble qui représente les

contraintes. Par exemple, si l"on cherche un miminum d"une fonctionfdeIRdansIRet que l"on demande que les

points qui réalisent ce minimum soient positifs, on auraK= IR+.

Si¯xest solution du problème (3.1), on dit que¯x?argminIRnf, et si¯xest solution du problème (3.2), on dit que

¯x?argminKf.

Vous savez déjà que si un point¯xréalise le minimum d"une fonctionfdérivable deIRdansIR, alorsf?(

x) = 0.

On dit que c"est un point critique (voir définition 3.2). La réciproque est évidemment fausse : la fonctionx?→x3

est dérivable surIR, et sa dérivée s"annule en 0 qui est donc un point critique, mais 0 n"est pas un extremum (c"est

un point d"inflexion).Nous verrons plus loin que de manière générale, lorsque la fonctionnellefest différentiable,

les extrema sont des points critiques def, au sens où ils annulent le gradient.

Définition 3.2(Point critique).SoitEun espace vectoriel normé etf:E→IRdifférentiable. On dit quex?E

est un point critique defsiDf(x) = 0. Pour illustrer un cas de point critique qui n"est pas un maximum ni un minimum, prenons un exemple en dimension 2, avec f(x1,x2) =x21-x22.

On a alors

Df(x1,x2)(h1,h2) = 2(x1h1-x2h2)etDf(0,0) = 0.

Le point(0,0)est donc un point critique def. Si on trace la surface x?→x21-x22, on se rend compte que le point(0,0)est minimal dans une direction et maximal dans une direction indépendante de la première. C"est ce qu"on appelle un point selle

Définition 3.3(Point selle).SoitEun espace vectoriel normé etf:E→IR. On dit que¯xest un point selle def

s"il existeFetGdes sous espaces vectoriels deEtels queE=F?Get un voisinageVde¯xtel que f(¯x+z)≥f(¯x),?z?G; ¯x+z?V.

3.1.2 Convexité

Définition 3.4(Convexité).SoitEun espace vectoriel (surIR) etf:E→IR. On dit quefest convexe si

On dit quefest strictement convexe si

f(tx+ (1-t)y)< tf(x) + (1-t)f(y)pour tout(x,y)?E2t.q.x?=yett?]0,1[.

Proposition 3.5(Première caractérisation de la convexité).SoitEun espace vectoriel normé (surIR) etf?

C

1(E,IR)alors :

Analyse numérique I, télé-enseignement, L3208Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.1. DÉFINITIONS ET RAPPELSCHAPITRE 3. OPTIMISATION

1. la fonctionfest convexe si et seulement sif(y)≥f(x) +Df(x)(y-x), pour tout couple(x,y)?E2,

2. la fonctionfest strictement convexe si et seulement sif(y)> f(x) +Df(x)(y-x)pour tout couple

(x,y)?E2tel quex?=y.

DÉMONSTRATION-Démonstration de 1.

(?) Supposons quefest convexe : soit(x,y)?E2; on veut montrer quef(y)≥f(x) +Df(x)(y-x). Soitt?[0,1],

Commefest différentiable,f(x+t(y-x)) =f(x) +Df(x)(t(y-x)) +tε(t)oùε(t)tend vers 0 lorsquettend vers

0. Donc en reportant dans (3.3),

En faisant tendretvers 0, on obtient alors :

f(y)≥Df(x)(y-x) +f(x).

(?) Montrons maintenant la réciproque : Soit(x,y)?E2, ett?]0,1[(pourt= 0ou= 1on n"a rien à démontrer). On

f(y)≥f(z) +Df(z)(y-z), etf(x)≥f(z) +Df(z)(x-z).

En multipliant la première inégalité par1-t, la deuxième partet en les additionnant, on obtient :

(1-t)f(y) +tf(x)≥f(z) + (1-t)Df(z)(y-z) +tDf(z)(x-z) (1-t)f(y) +tf(x)≥f(z) +Df(z)((1-t)(y-z) +t(x-z)). Et comme(1-t)(y-z) +t(x-z) = 0, on a donc(1-t)f(y) +tf(x)≥f(z) =f(tx+ (1-t)y).

Démonstration de 2

(?) On suppose quefest strictement convexe, on veut montrer quef(y)> f(x) +Df(x)(y-x)siy?=x. Soit donc

(x,y)?E2,x?=y. On posez=1

2(y-x), et commefest convexe, on peut appliquer la partie 1. du théorème et écrire

quef(x+z)≥f(x) +Df(x)(z).On a doncf(x) +Df(x)(y-x entraîne quef(x) +Df(x)(y-x

2)<12(f(x) +f(y)), d"où le résultat.

(?) La méthode de démonstration est la même que pour le 1. Proposition 3.6(Seconde caractérisation de la convexité).SoitE= IRnetf?C2(E,IR). SoitHf(x)la hessienne defau pointx, i.e.(Hf(x))i,j=∂2i,jf(x). Alors

1.fest convexe si et seulement siHf(x)est symétrique et positive pour toutx?E(c.à.d.Hf(x)t=Hf(x)

etHf(x)y·y≥0pour touty?IRn)

2.fest strictement convexe siHf(x)est symétrique définie positive pour toutx?E. (Attention la réciproque

est fausse.)

DÉMONSTRATION-Démonstration de 1.

(?) Soitfconvexe, on veut montrer queHf(x)est symétrique positive. Il est clair queHf(x)est symétrique car∂2i,jf=

2j,ifcarfestC2. Par définition,Hf(x) =D(?f(x))et?f?C1(IRn,IRn).Soit(x,y)?E2, commefest convexe

et de classeC1, on a, grâce à la proposition 3.5 : f(y)≥f(x) +?f(x)·(y-x).(3.4) Soit??C2(IR,IR)définie par?(t) =f(x+t(y-x)).Alors : f(y)-f(x) =?(1)-?(0) =? 1 0 ??(t)dt= [??(t)(t-1)]10-? 1 0 ???(t)(t-1)dt, c"est-à dire :f(y)-f(x) =??(0) +?1

0???(t)(1-t)dt.Or??(t) =?f(x+t(y-x))·(y-x),et

??(t) =D(?f(x+t(y-x))(y-x)·(y-x) =Hf(x+t(y-x))(y-x)·(y-x).

On a donc :

f(y)-f(x) =?f(x)(y-x) +? 1 0 H f(x+t(y-x))(y-x)·(y-x)(1-t)dt.(3.5)

Analyse numérique I, télé-enseignement, L3209Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.1. DÉFINITIONS ET RAPPELSCHAPITRE 3. OPTIMISATION

Les inégalités (3.4) et (3.5) entraînent :?1

0Hf(x+t(y-x))(y-x)·(y-x)(1-t)dt≥0?x,y?E. On a donc :?

1 0 H f(x+tz)z·z(1-t)dt≥0?x,?z?E.(3.6) En fixantx?E, on écrit (3.6) avecz=εy,ε >0,y?IRn. On obtient : 2? 1 0 H f(x+tεy)y·y(1-t)dt≥0?x,y?E,?ε >0,et donc : 1 0

Hf(x+tεy)y·y(1-t)dt≥0?ε >0.

Pour(x,y)?E2fixé,Hf(x+tεy)tend versHf(x)uniformément lorsqueε→0, pourt?[0,1]. On a donc :?1

0 H f(x)y·y(1-t)dt≥0,c.à.d.1

2Hf(x)y·y≥0.

Donc pour tout(x,y)?(IRn)2,Hf(x)y·y≥0doncHf(x)est positive.

(?) Montrons maintenant la réciproque : On suppose queHf(x)est positive pour toutx?E. On veut démontrer que

fest convexe; on va pour cela utiliser la proposition 3.5 et montrer que :f(y)≥f(x) +?f(x)·(y-x)pour tout

(x,y)?E2. Grâce à (3.5), on a : f(y)-f(x) =?f(x)·(y-x) +? 1 0 H f(x+t(y-x))(y-x)·(y-x)(1-t)dt.

OrHf(x+t(y-x))(y-x)·(y-x)≥0pour tout couple(x,y)?E2, et1-t≥0sur[0,1]. On a doncf(y)≥

f(x) +?f(x)·(y-x)pour tout couple(x,y)?E2. La fonctionfest donc bien convexe.

Démonstration de 2.

(?) On suppose queHf(x)est strictement positive pour toutx?E, et on veut montrer quefest strictement convexe.

On va encore utiliser la caractérisation de la proposition 3.5. Soit donc(x,y)?E2tel quey?=x. Alors :

f(y) =f(x) +?f(x)·(y-x) +? 1 0 H f(x+t(y-x))(y-x)·(y-x)? >0six?=y(1-t)???? ?=0sit?]0,1[dt. Doncf(y)> f(x) +?f(x)(y-x)six?=y, ce qui prouve quefest strictement convexe.

Contre-exemplePour montrer que la réciproque de 2. est fausse, on propose lecontre-exemple suivant : Soit

n= 1etf?C2(IR,IR), on a alorsHf(x) =f??(x). Sifest la fonction définie parf(x) =x4, alorsfest strictement convexe maisf??(0) = 0.

3.1.3 Exercices (extrema, convexité)

Exercice 110(Vrai / faux).corrigé en page 212

1. L"applicationx?→ ?x?∞est convexe surIR2.

2. L"applicationx?→ ?x?∞est strictement convexe surIR2.

3. L"application deIR2dansIRdéfinie parF(x,y) =x2-2xy+ 3y2+yadmet un unique minimum.

4. SoitA?Mn,m(IR),b?IRn, l"applicationx?→ ?Ax-b?2admet un unique minimum.

Exercice 111(Minimisation dansIR).Corrigé en page 212 OnconsidèrelesfonctionsdéfiniesdeIRdansIRparf0(x) =x2,f1(x) =x2(x-1)2,f2(x) =|x|,f3(x) = cosx, f

4(x) =|cosx|,f5(x) =ex. On poseK= [-1,1]. Pour chacune de ces fonctions, répondre aux questions

suivantes :

1. Etudier la différentiabilité et la (stricte) convexité éventuelles de la fonction,; donner l"allure de son graphe.

2. La fonction admet elle un minimum global surIR; ce minimum est-il unique? Le cas échéant, calculer ce

minimum.

Analyse numérique I, télé-enseignement, L3210Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.1. DÉFINITIONS ET RAPPELSCHAPITRE 3. OPTIMISATION

3. LafonctionadmetelleunminimumsurK; ceminimumest-ilunique?Lecaséchéant,calculerceminimum.

Exercice 112(Fonctions quadratiques).

1. Montrer que la fonctionfdeIR2dansIRdéfinie parf(x,y) =x2+ 4xy+ 3y2n"admet pas de minimum

en(0,0).

2. Trouver la matrice symétriqueStelle quef(x) =xtSx, pourf1(x) = 2(x21+x22+x23-x1x2-x2x3),

puis pourf2(x) = 2(x21+x22+x23-x1x2-x1x3-x2x3)Etudier la convexité des fonctionsf1etf2.

3. Calculerles matriceshessiennesdeg1etg2définiespar:g1(x,y) =1

4x4+x2y+y2etg2(x,y) =x3+xy-x

et étudier la convexité de ces deux fonctions. Exercice 113(Convexité et continuité).Suggestions en page 211.

1. Soitf: IR→IRune fonction convexe.

(a) Montrer quefest continue. (b) Montrer quefest localement lipschitzienne.

2. Soitn≥1etf: IRn→IR. On suppose quefest convexe.

m Rsi la norme dexest inférieure ou égale àR). (b) Montrer quefest continue. (c) Montrer quefest localement lipschitzienne.

(d) On remplace maintenantIRnparE, e.v.n. de dimension finie. Montrer quefest continue et quefest locale-

ment lipschitzienne.

3. SoientEun e.v.n. de dimension infinie etf:E→IR. On suppose quefest convexe.

(a) On suppose, dans cette question, quefest bornée supérieurementsur les bornés. Montrer quefest continue.

(b) Donner un exemple d"e.v.n. (notéE) et de fonction convexef:E→IRt.q.fsoit non continue.

Suggestions pour les exercices

Exercice 113 page 211 (Convexité et continuité)

1.(a) Pour montrer la continuité en0, soitx?= 0,|x|<1. On posea=sgn(x) (=x

|x|). Ecrirexcomme une combinaison convexe de0etaet écrire0comme une combinaison convexe dexet-a. En déduire une majoration de|f(x)-f(0)|. (b) Utiliser la continuité defet la majoration précédente.

2.(a) Faire une récurrence surnet pourx= (x1,y)tavec-R < x1< Rety?IRn-1(n >1), majorerf(x)en

utilisantf(+R,y)etf(-R,y). (b) Reprendre le raisonnement fait pourn= 1. (c) Se ramener àE= IRn.

3.(a) reprendre le raisonnement fait pourE= IR.

(b) On pourra, par exemple choisirE=C([0,1],IR)...

Analyse numérique I, télé-enseignement, L3211Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.2. OPTIMISATION SANS CONTRAINTE CHAPITRE 3. OPTIMISATION

Corrigés des exercices

Exercice 110 page 210 (Minimisation dansR)

1. Vrai.

2. Faux. L"application est convexe mais pas strictement convexe. Si on fixev1= (1,0)etv2= (1,1), alors

pour toutt?[0,1], ?tv1+ (1-t)v2?∞=?(1,1-t)?∞= 1 =t?v1?∞+ (1-t)?v2?∞.

3. Vrai. PosonsX= (x,y)t, on reconnait la fonctionnelle quadratiqueF(x,y) =1

2(AX,X)-(b,X)avec

A=?1-1

-1 3? etb=?01? . La matriceAune matrice symétrique définie positive. Le cours nous dit alors queFadmet un unique minimum.

4. Contre-exemple. SoitA=?1 00 0?

etb=?00? . Alors?Ax-b?2=x21et toute la droitex1= 0réalise le minimum def.

Exercice 111 page 210 (Minimisation dansIR)

1. La fonctionf0est différentiable surIR, et strictement convexe.Elle admet un minimum unique surIRet sur

Ket son minimum est réalisé en¯x= 0, et on af0(¯x) = 0.

2. La fonctionf1est différentiable surIR, et non convexe. La fonctionf1admet un maximum local en¯x=1

2, et on af(¯x) =1

16.Elle admet un minimum global non unique, réalisé en 0 et 1, et dont la valeur est 0.

3. La fonctionf2est différentiablesurIR\{0},et convexe,mais pas strictement convexe.La fonctionf2admet

unminimumuniquesurIRet surKet son minimumest réalisé en¯x= 0, et on af2(¯x) = 0, mais la fonction

f

2n"est pas différentiable en 0.

4. La fonctionf3est différentiable surIR, et non convexe.La fonctionf3admet un minimum, qui est -1, et qui

n"est pas unique car il est réalisé pour les points(2k+ 1)π,k?ZZ.

5. La fonctionf4est différentiable surIR, et non convexe. La fonctionf4admet un minimum, qui est 0, et qui

n"est pas unique car il est réalisé pour les points(2k+ 1)π

2,k?ZZ. La fonctionf4n"est pas différentiable

en ces points.

6. La fonctionf5est différentiable et strictement convexe. Elle n"admet pas de minimum. On af5(x)→0

lorsquex→ -∞maisf(x)>0pour toutx?IR.

3.2 Optimisation sans contrainte

3.2.1 Définition et condition d"optimalité

Soitf?C(E,IR)etEun espace vectoriel normé. On cherche¯xminimum global def, c.à.d. : ou un minimum local, c.à.d. : Proposition 3.7(Condition nécessaire d"optimalité).

SoitEun espace vectoriel normé, et soientf?C(E,IR), et¯x?Etel quefest différentiable en¯x. Si¯xest

solution de (3.8) alorsDf(¯x) = 0.

Analyse numérique I, télé-enseignement, L3212Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.2. OPTIMISATION SANS CONTRAINTE CHAPITRE 3. OPTIMISATION

alors si|t|<α

?z?, on a¯x+tz?B(¯x,α)(oùB(¯x,α)désigne la boule ouverte de centre¯xet de rayonα) et on a donc

f(¯x+tz) =f(¯x) +Df(¯x)(tz) +|t|εz(t),

oùεz(t)→0lorsquet→0. On a doncf(¯x) +tDf(¯x)(z) +|t|εz(t)≥f(¯x). Et pourα

?z?> t >0, on aDf(¯x)(z) + z(t)≥0. En faisant tendretvers 0, on obtient que

Df(¯x)(z)≥0,?z?E.

On a aussiDf(¯x)(-z)≥0?z?E, et donc :-Df(¯x)(z)≥0?z?E.

On en conclut que

Df(¯x) = 0.

Remarque 3.8.Attention, la propositionprécédente donne une condition nécessaire mais non suffisante. En effet,

Df(¯x) = 0n"entraîne pas quefatteigne un minimum (ou un maximum) même local, en¯x. Prendre par exemple

E= IR,

x= 0et la fonctionfdéfinie par :f(x) =x3pour s"en convaincre.

3.2.2 Résultats d"existence et d"unicité

Théorème 3.9(Existence).SoitE= IRnetf:E→IRune application telle que (i)fest continue, (ii)f(x)→+∞quand?x? →+∞. DÉMONSTRATION- La condition(ii)peut encore s"écrire ?A?IR,?R?IR;?x? ≥R?f(x)≥A.(3.9)

On écrit (3.9) avecA=f(0). On obtient alors :

?R?IRtel que?x? ≥R?f(x)≥f(0). donc il existe¯x?BRtel quef(¯x) = infBRfet doncf(¯x) = infIRnf.

Remarque 3.10.

1. Le théorème est faux siEest un espace de Banach (c"est-à-dire un espace vectoriel normé complet) de

dimension infinie car, dans ce cas, la boule ferméeBRn"est pas compacte.

2. L"hypothèse(ii)du théorème peut être remplacée par

(ii)??b?IRn,?R >0tel que?x? ≥R?f(x)≥f(b).

3. Sous les hypothèses du théorème il n"y a pas toujours unicité de¯xmême dans le casn= 1, prendre pour

s"en convaincre la fonctionfdéfinie deIRdansIRparf(x) =x2(x-1)(x+ 1).

Théorème 3.11(Condition suffisante d"unicité).SoitEun espace vectoriel normé etf:E→IRstrictement

Analyse numérique I, télé-enseignement, L3213Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.2. OPTIMISATION SANS CONTRAINTE CHAPITRE 3. OPTIMISATION

DÉMONSTRATION- Soitfstrictement convexe, supposons qu"il existe¯xet¯¯x?Etels quef(¯x) =f(¯¯x) = infIRnf.

Commefest strictement convexe, si¯x?=¯¯xalors f(1

2¯x+12¯¯x)<12f(¯x) +12f(¯¯x) = inf

IRnf, ce qui est impossible; donc¯x=¯¯x.

Ce théorème ne donne pas l"existence. Par exemple dans le casn= 1la fonctionfdéfinie parf(x) =exn"atteint

pas son minimumn; en effet,infIRnf= 0etf(x)?= 0pour toutx?IR, et pourtantfest strictement convexe. Par

contre, si on réunit les hypothèses des théorèmes 3.9 et 3.11, on obtient le résultat d"existence et unicité suivant :

Théorème 3.12(Existence et unicité).SoitE= IRn, et soitf:E→IR. On suppose que : (i)fcontinue, (ii)f(x)→+∞quand?x? →+∞, (iii)fest strictement convexe; alors il existe un unique¯x?IRntel quef(¯x) = infIRnf.

L"hypothèse(i)du théorème 3.12 est en fait inutile car une fonction convexedeIRndansIRest nécessairement

continue.

Nous donnons maintenant des conditions suffisantes d"existence et d"unicité du minimum pour une fonction de

classeC1. Proposition 3.13(Condition suffisante d"existence et unicité).Soitf?C1(IRn,IR). On suppose que : ?α >0;(?f(x)- ?f(y))·(x-y)≥α|x-y|2,?(x,y)?IRn×IRn,(3.10)

Alors :

1.fest strictement convexe,

2.f(x)→+∞quand|x| →+∞,

et en conséquence, il existe un unique¯x?IRntel quef(¯x) = infIRnf.

DÉMONSTRATION-

1. Soit?la fonction définie deIRdansIRnpar :?(t) =f(x+t(y-x)). Alors

f(y)-f(x) =?(1)-?(0) =? 1 0 ?f(x+t(y-x))·(y-x)dt,

On en déduit que

f(y)-f(x)- ?f(x)·(y-x) =? 1 0 (?f(x+t(y-x))·(y-x)- ?f(x)·(y-x))dt, c"est-à-dire : f(y)-f(x)- ?f(x)·(y-x) =? 1 0 (?f(x+t(y-x))- ?f(x))·(y-x)? ≥αt|y-x|2dt. Grâce à l"hypothèse (3.10) surf, ceci entraîne : f(y)-f(x)- ?f(x)·(y-x)≥α? 1 0 t|y-x|2dt=α

2|y-x|2>0siy?=x.(3.11)

Analyse numérique I, télé-enseignement, L3214Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.2. OPTIMISATION SANS CONTRAINTE CHAPITRE 3. OPTIMISATION

On a donc, pour tout(x,y)?E2,f(y)> f(x) +?f(x)·(y-x); d"après la première caractérisation de la

convexité, voir proposition 3.5, on en déduit quefest strictement convexe.

2. Montrons maintenant quef(y)→+∞quand|y| →+∞. On écrit (3.11) pourx= 0:f(y)≥f(0) +?f(0)·

y+α

2|y|2. Comme?f(0)·y≥ -|?f(0)|(y), on a donc

f(y)≥f(0) +|y|?α

2|y| - |?f(0)|?

→+∞quand|y| →+∞.

La fonctionfvérifie donc bien les hypothèses du théorème 3.30, et on en déduit qu"il existe un unique¯xqui minimisef.

Remarque 3.14(Généralisationà un espacede Hilbert).Le théorème3.12reste vrai siEest un espace deHilbert;

on a besoin dans ce cas pour la partie existence des hypothèses(i),(ii)et de la convexité def.

Proposition 3.15(Caractérisation des points tels quef(¯x) = infEf).SoitEespace vectoriel normé etfune

fonction deEdansIR. On suppose quef?C1(E,IR)et quefest convexe. Soit¯x?E. Alors : f(¯x) = infEf?Df(¯x) = 0. En particulier siE= IRnalorsf(¯x) = infx?IRnf(x)? ?f(¯x) = 0.

Démonstration

(?) Supposons quef(¯x) = infEfalors on sait (voir Proposition 3.7) queDf(¯x) = 0(la convexité est inutile).

(?) Sifest convexe et différentiable, d"après la proposition 3.5,on a :f(y)≥f(¯x) +Df(¯x)(y-x)pour tout

y?Eet comme par hypothèseDf(¯x) = 0, on en déduit quef(y)≥f(¯x)pour touty?E. Doncf(¯x) = infEf.

Cas d"une fonction quadratiqueOn appelle fonction quadratique une fonction deIRndansIRdéfinie par x?→f(x) =1

2Ax·x-b·x+c,(3.12)

oùA?Mn(IR),b?IRnetc?IR. On peut vérifier facilement quef?C∞(IRn,IR).Calculons le gradient de

fet sa hessienne : on a f(x+h) =1

2A(x+h)·(x+h)-b·(x+h) +c

1 =f(x) +1

2(Ax·h+Ah·x)-b·h+12Ah·h

=f(x) +1

2(Ax+Atx)·h-b·h+12Ah·h.

?f(x) =1

2(Ax+Atx)-b.(3.13)

SiAest symétrique, on a donc?f(x) =Ax-b.Calculons maintenant la hessienne def.D"après (3.13), on a :

?f(x+h) =1

2(A(x+h) +At(x+h))-b=?f(x) +12(Ah+Ath)

et doncHf(x) =D(?f(x)) =1

2(A+At).On en déduit que siAest symétrique,Hf(x) =A. Dans le cas oùA

est symétrique définie positive,fest donc strictement convexe.

Analyse numérique I, télé-enseignement, L3215Université d"Aix-Marseille, R. Herbin, 29 janvier 2018

3.2. OPTIMISATION SANS CONTRAINTE CHAPITRE 3. OPTIMISATION

De plus on af(x)→+∞quand|x| →+∞. (On note comme d"habitude| · |la norme euclidienne dex.) En

effet, Ax·x≥α|x|2oùαest la plus petite valeur propre deA,etα >0. Donc f(x)≥α

2|x|2- |b·x| - |c|;

f(x)≥ |x|?α|x|

2- |b|?

- |c| -→+∞quand|x| →+∞.

On en déduit l"existence et l"unicité de

¯xqui minimisef. On a aussi :

?f(¯x) = 0?f(¯x) = infIRnf et donc

¯xest l"unique solution du systèmeAx=b.

On en déduit le théorème suivant, très important, puisqu"ilva nous permettre en particulier le lien entre certains

algorithmes d"optimisation et les méthodes de résolution de systèmes linéaires vues au chapitre 1.

Théorème 3.16(Minimisation d"une fonction quadratique).Soitfune fonction deIRndansIRdéfinie par(3.12)

oùA?Mn(IR)est une matrice symétrique définie positive etb?IRn. Alors il existe un unique¯x?IRnqui

minimisef, et¯xest l"unique solution du système linéaireAx=b.

3.2.3 Exercices (optimisation sans contrainte)

Exercice 114(Maximisation).Suggestions en page 218

SoitEun espace vectoriel normé etf:E→IR. En utilisant les résultats de la section 3.2.2, répondre aux

questions suivantes :

1. Donner une condition suffisante d"existence de¯x?Etel quef(¯x) = supx?Ef(x).

2. Donner une condition suffisante d"unicité de¯x?Etel quef(¯x) = supx?Ef(x).

3. Donner une condition suffisante d"existence et unicité de¯x?Etel quef(¯x) = supx?Ef(x).

Exercice 115(Complément de Schur).Corrigé en page 218

Soientnetpdeux entiers naturels non nuls. Dans toute la suite, siuetvsont deux vecteurs deIRk,k≥1, le

produit scalaire deuetvest notéu·v. SoientAune matrice carrée d"ordren, inversible, soitBune matricen×p,

Cune matrice carrée d"ordrep, et soientf?IRnetg?IRp. On considère le système linéaire suivant :

M ?x y? =?f g? ,avecM=?A B B tC? .(3.14)

1. On suppose dans cette question seulement quen=p= 1, etA=?a?, B=?b?,C=?c?

(a) Donner une condition nécessaire et suffisante sura,b,etcpour queMsoit inversible.

(b) Donner une condition nécessaire et suffisante sura,b,etcpour queMsoit symétrique définie positive.

On définit la matriceS=C-BtA-1B, qu"on appelle "complément de Schur".

2. CalculerSdans le casA=?1 10 1?

,B=?1 10 1? ,C=?1 00 1?

3. Montrer qu"il existe une unique solution au problème (3.14) si et seulement si la matriceSest inversible. Est-ce

quotesdbs_dbs18.pdfusesText_24

[PDF] exercices corrigés analyse complexe l3

[PDF] exercices corrigés atomistique mpsi

[PDF] exercices corrigés audit comptable et financier

[PDF] exercices corrigés base de données pdf

[PDF] exercices corrigés bilan et cpc pdf

[PDF] exercices corrigés biostatistiques pcem1

[PDF] exercices corrigés budget des ventes

[PDF] exercices corrigés calcul littéral seconde

[PDF] exercices corrigés calculs commerciaux bac pro commerce

[PDF] exercices corrigés chimie minérale pdf

[PDF] exercices corrigés chimie terminale s pdf

[PDF] exercices corrigés ciel gestion commerciale

[PDF] exercices corrigés cinématique du point terminale s

[PDF] exercices corrigés cinématique du solide indéformable

[PDF] exercices corrigés circuit magnétique bobine