LICENCE 3 MATHEMATIQUES – INFORMATIQUE PDF

EXERCICE III (optimisation sans contrainte). On considère la fonction f définie sur Corrigé de l'exercice. 1. Le problème s'écrit inf. X?R3. J(X) avec.

OPTIMISATION CONTRAINTE

Quels sont les extremums de cette fonctions ? Corrigé de l'exercice 1.1. On doit résoudre un problème d'extremum pour une fonction de deux variables soumise à

Table des matières 1 Calcul différentiel

QUELQUES EXERCICES CORRIGÉS D'OPTIMISATION 2 Analyse des problèmes d'optimisation sans contrainte ... Soit A ? Mnm(R)

Optimisation Sans Contraintes

avec ou sans contraintes cependant on limite souvent l'optimisation à une Hiriart-Urruty

1 Les conditions de Kuhn-Tucker

Corrigés d'optimisation convexe et quadratique Exercices corrigés . ... Si on introduit des variables d'écart x dans les contraintes l'écriture des.

Optimisation sous contraintes

Un problème de recherche de minimum avec contraintes est donc celui pour une fonction définie sur la partie E = {x;g(x)=0} de Rn dépourvue de calcul

Corrigé type de la série des exercices 1 Optimisation sans contraintes

Corrigé type de la série des exercices 1. Optimisation sans contraintes -LMD- S5. Solution de l'exercice 1. Soit f : R2 ?? R la fonction définie f(x y) =.

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

Etudier les paragraphe 3.4 et 3.5 (optimisation avec contrainte). Exercice proposé (avec corrigé) : 139 (Uzawa). Le corrigé du deuxième devoir sera

Partiel du 26 Mars 2015—Corrigé “Optimisation et programmation

26 mars 2015 Exercice 1. ... Montrer que la contrainte est qualifiée en tout point. ... avec la condition d'exclusion ?g(x y

ANALYSE RÉELLE OPTIMISATION LIBRE ET SOUS CONTRAINTE

doivent être préparés : écouter le corrigé d'un exercice en ont un) avec toutes leurs hypothèses et vérifiez que ces hypothèses sont satisfaites avant ...

OPTIMISATION SOUS CONTRAINTES - HEC Montréal

3 Optimisation sous contrainte à variables multiples La fonction à optimiser peut souvent dépendre de plusieurs facteurs Par exemple les profits réalisés peuvent dépendre du coût des ressources du nombre d'employés du prix de vente

34 Optimisation sous contraintes

La contrainte (1) est représentée par le disque de centre ( r r) et de rayon 2 La contrainte (2) délimite le demi-espae sous la droite d’équation 1+ t 2? t= r La ontrainte (3) désigne les points à droite de l’axe 1= r Les courbes de niveau f(x)=constante sont des cercles de centre ( u t)

345 Exercices (optimisation avec contraintes) - univ-amufr

3 4 5 Exercices (optimisation avec contraintes) Exercice 125 (Sur l'existence et l'unicité) Corrigé en page 268 Etudierl'existenceetl'unicitédessolutionsduproblème (3 48)avecles donnéessuivantes: E = IR ;f : IR ! IR est dén ie par f (x ) = x 2 et pour les quatre différents ensembles K suivants : (i) K = fjx j 1g ; (ii) K = fjx j = 1 g

34 Optimisation sous contraintes - univ-amufr

Ce problèmeest un problèmede minimisationaveccontrainte (ou sous contrainte")au sens oùl'oncherche u qui minimise f en astreignant u a être dans K Voyons quelques exemples de ces contraintes (dén ies par l 'ensemble K ) qu'onva expliciter à l'aide des p fonctionscontinues gi 2 C (E; IR) i = 1 :::p 1 Contraintes égalités

ANALYSE RÉELLE OPTIMISATION LIBRE ET SOUS CONTRAINTE

Le but de l’UE est d’optimiser une fonction de deux variables : optimisation libre ou sous contrainte Documents et bibliographie En L1 de Sciences-Économiques toutes les universités françaises traitent à peu près le même programme de mathématiques mais la répartition sur les deux années la présentation (plus ou moins théorique)

Analyse 2: Optimisation avec contrainte

Analyse 2: Optimisation avec contrainte Minimisation avec contraintes Condition du remierp rdreo Lagrangien et conditions KKT Joseph Salmon Conditions de Karush-Khunn-Tucker (KKT) Théorème : KKT Si x est un minimum local du problème (P) que f;h i;g j sont dérivables avec des gradients continus sous des conditions de quali cation sur x il

Optimisation Continue ISTIL 2ème année Corrigé de la feuille 4

la contrainte C = cste alors ?(ab?)J ? Vect ?(ab?)C 4 Résolution du système La condition d’optimalité signi?e que les vecteurs ?(ab?)J et ?(ab?)C sont colinéaires ou encore que leur produit vectoriel est nul On a ?(ab?)J= 1 2 bsin? 1 2 asin? 1 2 abcos?

ANALYSE RÉELLE OPTIMISATION LIBRE ET SOUS CONTRAINTE

exercices doivent être préparés : écouter le corrigé d’un exercice sans avoir préalablement essayédelerésoudrecelanesertàrien Vousn’enretirerezaucunpro?tpuisquevousn’en aurezpassaisileséventuellesdi?cultés –Des sujets d’annales sont proposés dans le polycopié d’exercices Vous pouvez aussi les re-

Éléments de correction pour le TD d’optimisation sous

TD d’optimisation sous contrainte(s) d’égalité Exercice 1 DanstouslescasétudiéslesfonctionsetcontraintessontclairementC1etleursdomainesdedé?nition sontdesouverts 1 Traitéencours 2 Leseulpointcritiquedelafonction(x;y;z) 7!x2+y2 estl’originequinevéri?epaslacontrainteet

OPTIMISATION CONTRAINTE

§ 1 —Optimisation contrainte à deux variables Exercice1 1 On considère la fonction f(x;y) = x2+y24xysoumise à la contrainte x2+y2 = 8 Quels sont les extremums de cette fonctions? Corrigédel’exercice1 1 On doit résoudre un problème d’extremum pour une fonction de deux variables soumise à une contrainte donnée sous forme d

3104 Optimisation avec contraintes d’egalit´ e´

3 10 4 Optimisation avec contraintes d’egalit´ e ´ Dans de nombreux proble`mes on de´sire identi?er le point x maximisant ou minimisant une fonction f non pas parmi tous les xappartenant au domaine de de´?nition de f mais seulement parmi ceux qui ve´ri?ent une ou plusieurs con traintes du type gk(x)=0 pour tout k ?{12 ?}

Searches related to exercices corrigés doptimisation avec contrainte pdf filetype:pdf

Les coe cients s’appellent les coe cients de Kuhn-Tucker Il y en a autant que de contraintes Le coe cient j est associ e a la contrainte g j(x) b j Les conditions de Kuhn-Tucker sont des conditions n ecessaires qui sont r ea-

Comment calculer la minimisation avec contrainte ?

Soit E = IRn, soit f 2 C (E; IR) , et soit K un sous ensemble de E . On s'intéresse à la recherche de u 2 K tel que : ( u 2 K f (u ) = inf K f (3.53) Ce problèmeest un problèmede minimisationaveccontrainte (ou?sous contrainte")au sens oùl'oncherche u qui minimise f en astreignant u a être dans K .

Comment calculer la courbe de contrainte?

x3+ y + z2sous les contraintes x +y+z = 0 et x +y z = 0. Corrigé de l’exercice 2.2. Posons ’(x;y;z) = x +y+z et (x;y;z) = x +y z. Première étape : les fonctions f, ’et sont C2sur un certain ouvert U ˆR3. Puisque f, ’et 1sont des polynômes, elles sont C sur U = R3. Deuxième étape : la courbe de contrainte est régulière.

Comment calculer la contrainte d'un point ?

Chercher le(s) point(s) où f atteint son maximum ou son minimum sous la contrainte g = 1 . 3. Soient A 2 Mn(IR) symétrique, B 2 Mn(IR) s.d.p. et b 2 IRn. Pour v 2 IRn, on pose f (v) = (1 =2) Av v b v et g(v) = Bv v.

Comment calculer la contrainte d’une fonction?

— Pour chacune des deux questions suivantes on donnera deux méthodes : d’abord en explicitant la contrainte, puis en utilisant le lagrangien. 1. Soient les fonctions f et g dé?nies par : f(x,y) = xy, g(x,y) = 1 x + 1 y .

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?

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

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.quotesdbs_dbs14.pdfusesText_20

[PDF] LICENCE 3 MATHEMATIQUES – INFORMATIQUE

Comment calculer la minimisation avec contrainte ?

Comment calculer la courbe de contrainte?

Comment calculer la contrainte d'un point ?

Comment calculer la contrainte d’une fonction?

LICENCE 3 MATHEMATIQUES - INFORMATIQUE.

MATHEMATIQUES GENERALES.

L3MiMG.

92L3MATSMI5U4T5

Nom de l'UE : Analyse numériqueet optimisation

Semaine 1 :

Exercices proposés (avec corrigés) :

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

Semaine 2 :

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)

Semaine 4 :

On dit que¯xest un minimum global defsi

3.1. DÉFINITIONS ET RAPPELSCHAPITRE 3. OPTIMISATION

¯x?argminKf.

On a alors

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

3.1.2 Convexité

On dit quefest strictement convexe si

1(E,IR)alors :

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

DÉMONSTRATION-Démonstration de 1.

0. Donc en reportant dans (3.3),

En faisant tendretvers 0, on obtient alors :

Démonstration de 2

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

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

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

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

DÉMONSTRATION-Démonstration de 1.

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

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

On a donc :

3.1. DÉFINITIONS ET RAPPELSCHAPITRE 3. OPTIMISATION

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

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

2Hf(x)y·y≥0.

Démonstration de 2.

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.

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

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

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

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

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

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

1. Soitf: IR→IRune fonction convexe.

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

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

Suggestions pour les exercices

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

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

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

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

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

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

A=?1-1

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

Exercice 111 page 210 (Minimisation dansIR)