[PDF] Cours dOptimisation numérique

View - Download Cours dOptimisation numérique

Previous PDF

Next PDF

Universite Montpellier 2 (2016-2017) - M1 Mathematiques statistique et applications - Optimisation Numerique

Cours d'Optimisation numerique

Notes redigees par Terence Bayen

Table des matieres

1 Introduction a l'optimisation4

2 Calcul dierentiel, espaces de Hilbert, convexite 6

2.1 Un peu de calcul dierentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2 Fonctions semi-continue inferieurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.3 Brefs rappels sur les espaces de Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.4 Convexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.4.1 Proprietes generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.4.2 Fonctions convexes de classeC1etC2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12

2.4.3 Un peu de sous-dierentiabilite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.5 Quelques resultats d'existence et d'unicite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.6 Lemme de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3 Conditions d'optimalite18

3.1 Optimisation sans contraintes et condition d'Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.2 Theoreme de Fritz-John et Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.3 Criteres de qualication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.3.1 Condition de Mangasarian-Fromowitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

3.3.2 Qualication et c^one de Bouligand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.3.3 Preuve de KKT par le lemme de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.3.4 Cas des contraintes anes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.3.5 Contraintes convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.3.6 Condition de qualication pour les contraintes d'inegalite . . . . . . . . . . . . . . . . . . . . .

25

3.3.7 Cas des contraintes d'egalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.3.8 Cas general (contraintes d'egalites et d'inegalites) . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.4 Resume des conditions de qualication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.5 Theoreme de Karush-Kuhn-Tucker en dimension innie . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.5.1 Cas des contraintes d'egalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.5.2 Cas des contraintes d'inegalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.6 Conditions d'optimalite au second ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

3.7 Dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.7.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.7.2 Points selles de Lagrangien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.7.3 Problemes convexes et dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.7.4 Exemple de saut de dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

3.7.5 Preuve de la condition necessaire au second ordre par dualite . . . . . . . . . . . . . . . . . . .

36

4 Algorithmes numeriques39

4.1 Algorithmes de descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.1.1 Regle d'Armijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.1.2 Regle de Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.1.3 Conditionnement pour la methode de gradient a pas optimal . . . . . . . . . . . . . . . . . . .

42

4.1.4 Gradient projete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.1.5 Algorithme d'Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44
2

TABLE DES MATI

ERES3

4.2 Methode du gradient conjugue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.3 Algorithme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.3.1 Methode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.3.2 Methode de quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

5 Exercices51

5.1 Exercices sur la convexite et les espaces de Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

5.2 Exercices sur l'optimisation sans contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

5.3 Demonstration du lemme de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

5.4 Exercices autour du theoreme de KKT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

5.5 Conditions d'optimalite en dimension inni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

5.6 Exercices autour de la dualite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

5.7 Exercices autour des algorithmes numeriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

5.8 TP sous matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

6 Sujets d'examen66

6.1 Session 2015-2016 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

6.1.1 Partiel (1h) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

6.1.2 Examen nal (2h) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

6.2 Session 2016-2017 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

6.2.1 Partiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

6.3 Devoir Maison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

6.3.1 Devoir Maison sur l'algorithme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

Chapitre 1

Introduction a l'optimisation

Un probleme d'optimisation met en evidence des variables d'etat (parametres) et des contraintes. Le but est de

minimiser une fonctionfdansC: infx2Cf(x):(1.0.1)

Icifest une fonction deni sur l'ensembleC(un sous-ensemble d'un espace vectoriel norme) a valeurs reelles.

L'ensembleCs'appelle ensemble de contraintes : il s'agit d'une restriction sur les parametres admissibles.

On ne s'interessera pas dans ce cours a des problemes multi-criteres: inf x2CF(x);

ouF(x) := (f1(x);:::;fm(x)) sontmfonctions a valeurs reelles denies surC. Ce type de probleme multi-objectif (i.e.

qui consiste a vouloir minimiser simultanement plusieurs objectifs parfois antagonistes) est plus dicile et depasse

le cadre de ce cours.

Les dierentes questions relatives a (1.0.1) que l'on est amene a se poser en optimisation sont les suivantes :

- 1. Existence d'une solution. - 2. Conditions necessaires d'optimalite (du type \f0(x) = 000). - 3. Conditions susantes d'optimalite. - 4. Algorithmes numeriques pour trouver une solution. - 5. Analyse qualitative de la solution lors d'une perturbation des parametres.

On etudiera principalement les points 1,2,3 et 4 (partiellement). Citons quelques exemples de problemes bien etudies

dans la litterature:

Probleme isoperimetrique: parmi les courbes fermeesCdu plan et de longueur 1, trouver celle d'aire maximale:

max

C;L(C)=1A(C):

Il s'agit d'un probleme geometrique a transformer analytiquement. Le probleme du voyageur de commerce: on a un graphe avecnpoints (les villes) etn(n1)2 ar^etes de co^utcij telles quecij=cji. On posexij= 1 si on va du noeudiau noeudjet 0 sinon. On cherche a minimiser: min x2Rn2X

1i;jnc

ijxij; sous les contraintes Pn j=1xij=Pn i=1xij= 1 etP i2Ixij jIj 1 pour tout sous-ensembleI&f1;:::;ng. Ce

probleme modelise comment un voyageur de commerce peut passer dans toutes les villes une et une seule fois

sans cyclage. Son but est de minimiser son co^ut de trajet total possible (i.e. de trouver le meilleur chemin

possible). Il s'agit d'un exemple de probleme lineaire mais dont la complexite est tres elevee (grand nombre de

contraintes). 4 5

Probleme de la cha^nette : il s'agit de trouver la forme prise par une cha^nette accrochee a deux points du mur:

ceci revient a etudier un probleme de calcul des variations: inf y2C1([a;b];R) y(a) =aa;y(b) =ybZ b a y(x)p1 +y02(x)dx:

En eet, la courbe optimale (dite cha^nette) minimise son energie potentielle de pesanteur. Ainsi, ce probleme

exprime la minimisation de cette energie parmi toutes les courbes possible.

Le probleme de Newton consiste a trouver parmi tous les objets convexes de hauteur donnee et de base donnee,

celui qui tombe le plus rapidement, c.a.d., celui qui en tombant minimise la resistance de l'air. Sous certaines

hypotheses, ce probleme se ramene a un probleme de calcul des variations du m^eme type que le precedent (mais

c'est un probleme tres dicile a resoudre). Parmi les solutions d'un systeme lineaireAx=bavecA2Mmn(R) (avecm < n), on cherche celle qui minimise la semi-normekxk0qui mesure le nombre de composantes non-nulles: min x Ax=bkxk0:

Trouver une solution au systeme ayant le plus de composantes nulles est tres utile dans le domaine du traitement

du signal. La diculte est que la fonction a minimiser n'est pas reguliere.

Le cours suivra les grandes lignes suivantes:

Existence de solutions en optimisation (proprietes de convexite convexite) Conditions necessaires et susantes d'optimalite, qualication (dimension nie et innie)

Theorie de la dualite

Methodes numeriques (algorithmes de descente et Newton). Optimisation en dimension innie (conditions d'optimalite) et calcul des variations.

Il serait possible d'etudier d'autres aspects de l'optimisation comme par exemple la programmation dynamique (en

horizon ni ou en horizon inni) et le contr^ole optimal. Certains aspects seront traites plus en details en M2 (comme

le contr^ole optimal qui constitue la continuation naturelle du calcul des variations).

References: Pour certaines sections, le cours s'est inspire entre autres des polycopies mentionnes ci-dessous. Merci

de me signaler tout oubli. Une liste plus exhaustive des diverses references (livres) ayant ete utilises pour ce polycopie

est donnee a la n du document. - Cours de G. Carlier (calcul dierentiel) :https://www.ceremade.dauphine.fr/carlier/calculdiff.pdf - Cours de G. Carlier (optimisation) :https://www.ceremade.dauphine.fr/carlier/progdyn.pdf - Cours de S. Delabriere :https://webusers.imj-prg.fr/sylvie.delabriere/AnaConv/ACPoly.pdf - Cours de P. Cardaliaguet :https://www.ceremade.dauphine.fr/cardalia/OptiPgrDyn15-16.pdf - Cours de Y. Privat :https://www.ljll.math.upmc.fr/privat/documents/optimAgreg.pdf - Cours de A. Rondepierre et P. Weiss :http://www.math.univ-toulouse.fr/rondep/CoursTD/polyGMM4.pdf - Cours, exercices, sujet d'examen par E. Trelat :https://www.ljll.math.upmc.fr/trelat/

Chapitre 2

Calcul dierentiel, espaces de Hilbert,

convexite

On commence par quelques rappels de calcul dierentiel qui seront utiles notamment pour l'optimisation en dimension

innie.

2.1 Un peu de calcul dierentiel

On introduit le calcul en dimension quelconque qui sert pour etudier des fonctionnelles ou bien pour le calcul des

variations: par exemple, on s'interessera a la regularite de la fonctionnelle

J(x) :=Z

1 0 `(t;x(t);x0(t))dt oul: [0;1]RnRn!Retx()2XouXest l'espace de BanachX:=C1([0;1];Rn) muni de la norme

kxk:= maxt2[0;1](jx(t)j+jx0(t)j). On s'interessera en particulier a la minimisation deJsurXet a caracteriser un

minimum. Denition 2.1.SoitXetYdeux espaces de Banach. La derivee directionnelle defau pointx2Xdans la directionh2Xest si elle existe la limite f

0(x;h) := limt#0f(x+th)f(x)t

Remarque 2.1.(i) Supposons quefadmette une derivee directionnelle enxdans la directionh. Alors on a f

0(x;th) =tf0(x;h)pourt >0i.e. la derivee directionnelle est positivement homogene.

(ii) On a aussi le developpement suivant:f(x+th) =f(x) +tf0(x;h) +o(t),t >0. Par exemplef(x) =jxjadmet enx= 0 une derivee directionnelle dans toute direction:f0(0;h) =jhj,h2R.

Denition 2.2.(i) La fonctionf:X!Yest dite G^ateaux-dierentiable enxsi la derivee directionnelle defau

pointxexiste pour touth2Xet sih7!f0(x)hest lineaire continue deXdansY. On note alorsDf(x)2 L(X;Y) sa derivee (au sens de G^ateaux) denie par:

Df(x)h=f0(x;h):

(ii) On dit quefest Frechet dierentiable enxsi elle est G^ateaux dierentiable enxet si f(x+h) =f(x) +Df(x)h+o(khkX):

On appelle alorsDf(x)la derivee au sens de Frechet defenx(appele egalement la dierentielle defenx). La

dierentielle enxest unique.

Remarque 2.2.Notons que sifest Frechet dierentiable enxalorsfest G^ateaux dierentiable enxavec la m^eme

derivee. 6

2.2. FONCTIONS SEMI-CONTINUE INF

ERIEUREMENT7

Propriete 2.1.Sifest Frechet dierentiable au pointxalorsfest continue au pointx.

La denition de \G^ateaux-dierentiable" ou \Frechet-dierentiable" depend du choix de la norme sur les espaces

consideres. Cependant, on peut montrer que pour deux normes equivalentes, on est conduit a la m^eme denition.

Remarque 2.3.(i) Soit la fonctionf:R2!Rdenie parf(x1;x2) := 1six1>0etx2=x21etf(x1;x2) = 0sinon.

Alorsfn'est pas continue en(0;0). De plusf0((0;0);h) = 0pour touth2R2, doncfest G^ateaux dierentiable en

(0;0). Commefn'est pas continue en(0;0)alorsfn'est pas Frechet dierentiable en(0;0).

(ii) Une fonction peut admettre des derivees directionnelles en un point sans ^etre Gateaux dierentiable en ce point.

Considerons la fonctionf:R2!Rdenie parf(x1;x2) =x2 1x

22+jx1jsi(x1;x2)6= (0;0)etf(0;0) = 0. Alors, on peut

montrer quef0((0;0);h)existe pour touth2R2maish7!f0(0;0)hn'est pas lineaire (en eet:f0((0;0);h) = 0si

h= (0;h2),h22Retf0((0;0);h) =jh1jsih= (h1;h2)avech16= 0). Denition 2.3.On dit quef:X!Rest de classeC1surXsifest Frechet dierentiable en tout point deXet six7!Df(x)est continue deXdansX, le dual topologique deX.

Dans la denition precedente,Df(x) est donc une application continue deXa valeur dans l'espace des formes

lineaires continues surX. Exercice 2.1.1) Montrer queA2Mn(R)7!A2est G^ateaux-dierentiable en tout pointA2Mn(R).

2) Soitf:Mn(R)!Rdenie parf(A) :=eTr(A)A. Montrer quefest Gateaux-dierentiable, Frechet dierentiable

et de classeC1. SoitXest un espace de Banach. On noteXl'ensemble des formes lineaires continue deXdansR(dual topologique). On rappelle queXest muni de la norme: kLkX:= sup kxk1jL(x)j:

2.2 Fonctions semi-continue inferieurement

Les resultats d'existence de solutions a un probleme d'optimisation s'enoncent dans le cas ou la fonction objectiff

est continue, mais on peut egalement considerer le cas plus general oufest semi-continue inferieurement.

SoitXun espace de Banach etKXun sous-ensemble non vide. Denition 2.4.1) On dit quef:X!Rest semi-continue inferieurement enx0si et seulement si:

8" >09r >08x2H;kxx0k r)f(x)f(x0)"

2) On dit quefest semi-continue inferieurement (s.c.i.) surHsi et seulement si elle est semi-continue inferieurement

en tout point deX. Propriete 2.2.Une fonction fonctionf:X!Rest s.c.i. enx0ssi pour tout suite(xn)2HNtelle quexn!x0, alors: f(x0)liminfxn:

Preuve.Supposonsfs.c.i. enx0. Soit'l'extraction correspondant a liminfxn. Supposons par l'absurde que

limx'(n)< f(x0). Donc il existe" >0 tel que limx'(n)f(x0)". Commefest s.c.i. on applique la denition

avec"=2 et donc il exister >0 tel que sinest assez grand, alorsf(x'(n))f(x0)"=2. D'ou une contradiction.

Supposons maintenant quefne soit pas s.c.i. enx0. Alors il existe" >0 tel que pour toutr >0 il existex2H,

tel quekxx0k ravecf(x)< f(x0)". On prendr= 1=n. Donc il existexn2Htel quekx0xnk 1=net

f(xn)< f(x0)". Ainsi liminff(xn)< f(x0)".En d'autres termes, la fonctionf:H!Rest s.c.i. si pour tout2R, le sous-ensemble de niveau:

fx2H;f(x)g; est ferme dansH.

Exemple: la longueur d'une courbe decrite par une fonctionf,f7!L(f) est semi-continue inferieurement. Les

8CHAPITRE 2. CALCUL DIFFERENTIEL, ESPACES DE HILBERT, CONVEXITEcourbes decrites par les fonctionsfkont toutes la m^eme longueuret donc le segmentfde longueur 1 est bien tel

que:

L(f)

Un certain nombre de resultats standards qui suivent concernant l'existence d'une solution a un probleme d'optimisation

sont ecrits dans le cas ou la fonctionfa minimiser est continue, mais ils peuvent ^etre etendus au casfs.c.i.

2.3 Brefs rappels sur les espaces de Hilbert

Dans la suite, les espaces vectoriels consideres sont denis surR.

Denition 2.5.SoitHun espace vectoriel. On appelle produit scalaire surHune forme bilineaire symetriqueh;i

deHHdansR,(u;v)7! hu;viet denie positive: hu;ui 08u2H;hu;ui= 0()u= 0: Un produit scalaire denit surHune structure d'espace vectoriel norme pour la normeu7! hu;ui12

Denition 2.6.On dit queXest un espace de Hilbert ssiXest un espace vectoriel norme muni d'un produit scalaire

h;iqui rend complet l'espaceXpour la norme associee.

De tels espaces constituent les exemples les plus simples d'espace vectoriels de dimension innie et sont fondamen-

taux dans le domaine de l'analyse (equations dierentielles, equations aux derivees partielles). Citons les exemples

suivants:

Rnmuni du produit scalaire usuel.

l2l'espace des suites reelles telles queP+1 n=0jxnj2<+1muni du produit scalairehx;yi=P+1 n=0xnyn. L'espace de LebesgueL2((0;T) ;R) des applications mesurablesf: (0;T)!Rtelles queRT

0f2(t)dt <+1,

muni du produit scalairehf;gi=RT

0f(t)g(t)dt, (voir [9]). MaisC0([0;T] ;R) muni de la m^eme structure est

seulement prehilbertien (considerer l'application ane denie sur [0;1] parfn(t) = 1 sur [0;1=2] etfn(t) = 0

sur [1=2 + 1=n;1]). Soit un ouvert deRn. L'espaceL2( ) :=fv: !R;vmes:R v2<+1gest un espace de Hilbert pour la norme issue du produit scalairehu;vi=R uvouu;v2L2( ), (voir [9] p.58). Soit un ouvert deRn. L'espaceH1( ) :=fv: !R;v2L2( ) etrv2L2( )g1est un espace de Hilbert pour la norme issue du produit scalairehu;vi=R (ru rv+uv) ouu;v2H1(

L'espaceH10(

) :=fv2H1( ) ;v= 0 sur@ gest un espace de Hilbert pour la normeH1( Propriete 2.3.SoitXun espace de Hilbert. Alors on a: - L'inegalite de Cauchy-Schwarz:8x;y2X;jhx;yij kxkkyk: - L'egalite de la mediane:8x;y;a;b2X;kxak2+kxbk2= 2kxa+b2 k2+ 2kab2 k2: - L'egalite du parallelogramme :8x;y2X,kxyk2+kx+yk2= 2(kxk2+kyk2).

Exercice 2.2.Pouru2L2([0;1];R), on notekuk2:= (R1

0u2)12

. Montrer l'inegalite de Poincare en dimension 1: u2H10([0;1];R)) kuk22 ku0k22: En deduire queH10([0;1];R)peut-^etre muni du produit scalairehu;vi:=R1

0u0v0.1

On denit l'espace de SobolevH1(

) comme l'ensemble des fonctionsu2L2( ) telles qu'il existev= (v1;:::;vn)2L2( )nveriantR u@'@x i=R 'vipour toute fonction'2C1c( ), 1in. On notera alorsru:=v.

2.3. BREFS RAPPELS SUR LES ESPACES DE HILBERT9

On rappelle le theoreme de projection sur un ensemble convexe ferme. Theoreme 2.1.SoitCun ensemble convexe ferme non-vide d'un espace de HilbertH. Alors pour toutx2Hil existe un uniquep(x)2Htel que:kxp(x)k= inffkxyk;y2Cg. Le pointp(x)est caracterise par:

8y2Chxp(x);yp(x)i 0:

De plus on a:

8(x;y)2HH;hxy;p(x)p(y)i 0 etkp(x)p(y)k kxyk:

On rappelle le theoreme de separation suivant.

Theoreme 2.2.SoitHun espace de Hilbert,Cun convexe ferme non-vide, etx02Htel quex0=2C. Alors il existep2Het" >0tel que:

8y2C;hp;x0i hp;yi ":(2.3.1)

Preuve.On denit un ensemble convexe fermeKpar:K:=Cx0=fyx0;y2Cg. On a 0=2K. Soitpla projection de 0 surK. On ap6= 0 car 0=2K. Le pointpest caracterise par: hp;zpi 08z2K:

D'ou pour toutz2K,hp;zi kpk2>0 et le resultat en remplacantzparyc0,y2C.On rappelle le theoreme de representation de Riesz permettant d'identierHa son dual topologique.

Theoreme 2.3.SoitX0le dual deX. Alors pour toutL2X0il existe un uniquey2Xtel que

8x2XhL;xiX0;X=hy;xi:

Preuve.SoitF= Ker(L) etx02Htel queL(x0) = 1. On a doncFRx0=H(utiliser le theoreme de projection pour verier cette egalite

2). Commex0=2Ker(L) on ay0:=x0PKer(L)(x0)6= 0. Posonsx=x0y0kx0y0k22F?.

Verions queL(u) =hx;uipour toutu2H. Siu2F, alors on a bienhx;ui= 0. Supposons maintenantu2Rx0 de sorte queu=x0,2R. On aL(u) =L(x0) =ethx;ui=D x

0;x0y0kx0y0kE

=, d'ou le resultat.Tout espace de Hilbert peut donc ^etre identie avec son dual. On denit maintenant une nouvelle topologie sur

Hdite topologie faible qui est la topologie la moins ne rendant continue les formes lineairesx7! hf;xi,f2H.

Denition 2.7.On dit qu'une suite(xn)deHconverge faiblement versxsi et seulement si pour touty2H, on a

hxn;yi ! hx;yilorsquen!+1.

On notera qu'en dimension nie, toute suite (xn) deHconverge faiblement vers un pointxsi et seulement si

(xn) converge fortement versx.

Les proprietes suivantes decoulent de resultats classiques en analyse fonctionnelle comme le theoreme de Banach-

Steinhaus (voir [9]).

Propriete 2.4.SoitHun espace de Hilbert.

(i) Soit(xn)une suite deHqui converge faiblement versx2H. Alors on a la propriete de semi-continuite:

kxkHliminfn!+1kxnkH: (ii) Si une suite(xn)deHest bornee, alors il existe une sous-suite(xnk)qui converge faiblement. (iii) Toute suite deHqui converge faiblement est bornee. Propriete 2.5.Si(xn)converge faiblement versxetkxnk ! kxklorsquen!+1, alors(xn)converge fortement versx.2

SiFHest un sous-espace vectoriel ferme, alorsFF?=H. On utilise le theoreme de projection et le fait queFest un espace

vectoriel.

10CHAPITRE 2. CALCUL DIFFERENTIEL, ESPACES DE HILBERT, CONVEXITE

Remarque 2.4.La preuve de (i) est tres simple en developpantkxnxk2. La preuve de (ii) et (iii) utilise des

resultats d'analyse fonctionnelle (voir [9]) comme le theoreme de Banach-Steinhaus. Neanmoins, on peut demontrer

(iii) par l'absurde (voir exercice suivant). Exercice 2.3.On souhaite montrer que toute suite(xn)deHqui converge faiblement est bornee.

1) Montrer que pour tout2H,M()<+1ouM() := supnh;xni. On raisonne par l'absurde dans toute la

suite.

2) Montrer qu'il existen1ete12Hunitaire tel quehe1;xn1i 1. SoitV1l'orthogonal deV ect(e1;xn1).

3) Montrer que la suitePV1(xn)n'est pas bornee (raisonner par l'absurde en supposant qu'elle bornee).

4) Montrer qu'il existee22Hunitaire etxn2tel quejhe2;xn2ij 2(2 +M(e1)).

5) Etablir par recurrence qu'il existe une famille de vecteurs unitaires(ek)k0et une suite extraite(xnk)k0veriant:

e n?V ect(e1;:::;en1;xn1;:::;xnk1) etjhek;xnkij k(k+M(e1) +12

M(e2) +:::+1k1M(ek1)):

6) Soitf:=P

Ke kk . Calculerkfket montrer que pour toutkhf;xnki k. Conclure.

Remarque 2.5.A l'aide du lemme de Riemann-Lebesgue, montrer queun(t) := cos(nt)converge faiblement mais

pas fortement vers la fonction nulle dansL2([0;2];R)(phenomene d'oscillation). On peut mentionner aussi le

phenomene de concentration et d'evanescence (a l'inni). La propriete suivante est proposee en exercice (voir che d'exercice).

Propriete 2.6.Dans un espace de Hilbert, toute suite decroissante de convexes fermes bornes non-vide est d'intersection

non-vide.

Preuve.Voir preuve en exercice.Pour la theorie Hilbertienne (base Hilbertienne...) et le theoreme de Lax-Milgram on se reporte a [9]

2.4 Convexite

2.4.1 Proprietes generales

SoitXun espace de Hilbert etf:H!R.

Denition 2.8.(i) On dit quefest convexe si

8t2[0;1]8x2X8y2X f(tx+ (1t)y)tf(x) + (1t)f(y):

(ii) On dit quefest strictement convexe si

8t2(0;1)8x2X8y2X x6=y)f(tx+ (1t)y)< tf(x) + (1t)f(y):

(iii) On dit quefest fortement convexe de parametresi il existe >0tel que:

8t2[0;1]8x2X8y2X f(tx+ (1t)y)tf(x) + (1t)f(y)t(1t)2

kxyk2: Remarque 2.6.La convexite forte implique la convexite stricte qui implique la convexite. Plus generalement on est amene a denir des fonctions convexes a valeurs dansR[+f1g. Denition 2.9.Soitf:H!R[+f1gune fonction convexe. On appelle domaine defl'ensemble deni par: dom(f) :=fx2H;f(x)<+1g. A titre d'exemple, la fonction indicatrice d'un ensemble convexe fermeKHnon vide et denie par: 1

K(x) :=0 six2K

+1six =2K(2.4.1)

est convexe. Pour ce qui est de la continuite des fonctions convexes, on commence par le lemme suivant.

2.4. CONVEXIT

E11 Lemme 2.1.SoitHun espace de Hilbert etf:H!] 1;+1]une fonction convexe. Soitx02Dom(f). Soit >0. On suppose que:= supf(B(x0;))<+1. Alors:

82[0;1]8x2B(x0;);jf(x)f(x0)j (f(x0)):(2.4.2)

Preuve.Soitx2B(x0;). En posantx= (1)x0+x(1)x0

on a par convexite: f(x)f(x0)(1)f(x0) +fx(1)x0 f(x0) = f x 0+xx0 f(x0) (f(x0)):

De m^eme en posantx0=x1++1+(1+)x0x

on obtient par convexite: f(x0)f(x) =fx1 ++1 +(1 +)x0x f(x)1 + f x 0+x0x f(x)

1 +(f(x)):

D'ou l'on obtientf(x0)f(x)1+(f(x0) +f(x0)f(x)) qui entra^ne f(x0)f(x)(f(x0));

d'ou le resultat.Proposition 2.1.SoitHun espace de Hilbert etf:H!]1;+1]une fonction convexe. Soitx02Dom(f). On

suppose quefest bornee au voisinage dex0. Alorsfest continue enx0. Preuve.Il existe >0 tel que:= supf(B(x0;))<+1. Pour2]0;1[ etx2B(x0;) on ajf(x)f(x0)j

(f(x0)) d'ou le resultat.Remarque 2.7.On peut montrer l'equivalence entre la continuite defenx0et le fait quefsoit bornee au voisinage

dex0(voir par exemple [3] pour plus de details sur la question).

Exercice 2.4.Redemontrer la proposition 2.1 en dimension1(i.e. pour une fonction convexef:I!Ren utilisant

la propriete des pentes croissantes: (x;y;z)2I3; x < y < z)f(y)f(x)yxf(z)f(x)zxf(z)f(y)zy: (pour tout" >0petit on af(x)f(xr)r f(x+")f(x)" f(x+r)f(x)r et conclure). On peut egalement montrer qu'une fonction convexe admet une minorante ane Proposition 2.2.Soitf:H!Rune fonction convexe continue sur un ensemble convexe fermeC. Alors: 9y2H9

2R8x2C f(x) hx;yi+

Preuve.Voir che d'exercice pour la preuve (cela utilise le theoreme de Hahn-Banach).Proposition 2.3.Soitf:H!R[ f+1gune fonction convexe s.c.i. Soit(xn)une suite qui converge faiblement

versxsurH. Alors: f(x)liminfn!+1f(xn): Preuve.Pour tout2Rtel que l'ensembleA:=fx2H;f(x)gsoit non-vide,Aest un ensemble convexe

ferme, donc il est faiblement ferme pour la topologie faible (voir le lemme ci-dessous 2.2 et pour plus de details on se

refere a [9]). Orfest s.c.i. si et seulement si pour tout2Rtel queA6=;, alorsAest (fortement) ferme. Donc

fest faiblement s.c.i. puisque tout sous-niveau defest faiblement ferme. D'ou le resultat.Lemme 2.2.SoitCun sous-ensemble convexe non-vide deH. Alors,Cest fortement ferme si et seulement siC

est faiblement ferme.

12CHAPITRE 2. CALCUL DIFFERENTIEL, ESPACES DE HILBERT, CONVEXITE

Preuve.Supposons queCsoit faiblement ferme. Soit alors (xn)2Cnetx2Htelle quexn!xlorsquen!+1.

Alors (xn) converge faiblement versx, et commeCest faiblement ferme, on a doncx2C. Donc,Cest fortement

quotesdbs_dbs33.pdfusesText_39

[PDF] optimisation mathematiques pdf exercices

[PDF] cours optimisation master

[PDF] exercices corrigés de convexité et optimisation

[PDF] exercices corrigés doptimisation pdf

[PDF] cours doptimisation pour économistes

[PDF] cours optimisation sans contrainte

[PDF] resume cours optique geometrique

[PDF] cours de physique optique cours et exercices corrigés pdf

[PDF] examen corrigé optique ondulatoire

[PDF] résumé cours optique ondulatoire

[PDF] physique optique cours complet

[PDF] controle optique 1ere s

[PDF] orientation scolaire et professionnelle définition

[PDF] oxydoréduction cours bac pro

[PDF] programme daeu b physique