[PDF] Table des matières 1 Calcul différentiel

View - Download Table des matières 1 Calcul différentiel

Previous PDF

Next PDF

Master 1 - Math. Fondamentales, CSMI

QUELQUES EXERCICES CORRIGÉS D"OPTIMISATIONYannick PRIVAT- yannick.privat@unistra.fr

Table des matières

1 Calcul différentiel

1

2 Analyse des problèmes d"optimisation sans contrainte

4

3 Analyse des problèmes d"optimisation sous contrainte

9

4 Algorithmes numériques pour les problèmes d"optimisation

12

1 Calcul différentielExercice 1.

1.

Montrer que la fonction f:R2!R2définie par

f(x,y) =( y2x six6=0 ysix=0 admet des dérivées partielles au point(0,0), mais n"est pas continue en(0,0). 2. Soit E, unR-espace vectoriel muni d"un produit scalaireh,i. Montrer la continuité, puis la

différentiabilité et calculer la différentielle de l"application " produit scalaire »F:E2!R

définie parF(x,y) =hx,yipour tous(x,y)2E2. 3.

Soit A2 Mn,m(R), avec(n,m)2N2.

(a) Montrer que l"application J:Rm!Rdéfinie parJ(X) =kAXk2, où la notationk k désigne la norme euclidienne deRn, est différentiable et calculer sa différentielle. (b) Soit f2 C1(R). Montrer que l"applicationG:Rm!Rdéfinie parG(X) =f(J(X))est différentiable et calculer sa différentielle.

Correction.

1.

On a pou rtou tt2R,f(t,0)f(0,0) =02t

=0, ce qui montre que limt!0f(t,0)f(0,0)t =0,

2.L "applicationFétant bilinéaire, sa continuité surE2est équivalente à sa continuité en(0,0). De

plus, d"après l"inégalité de Cauchy-Schwarz,jF(x,y)j kxk kykpour tous(x,y)2E2, où kxk=phx,xi. Étudions la différentiabilité deF. Fixons(x,y)2E2et(h,k)2E2. On a :

F(x+h,y+k) =F(x,y) +F(x,k) +F(h,y) +F(h,k),

donc siL(h,k) =F(x,k) +F(h,y), on a kF(x+h,y+k)F(x,y)L(h,k)k=kF(h,k)k khk kkk=o(N(h,k)), en prenant par exempleN(h,k) =maxfkhk,kkkg. De plus,Lest linéaire et continue car jL(h,k)j kxk kkk+khk kyk N(x,y)N(h,k)!

N(h,k)!00,

en vertu de l"inégalité de Cauchy-Schwarz. On en déduit simultanément queFest différentiable,

et quedF(x,y)(h,k) =L(h,k) =hx,ki+hy,hi. 3. ( a) L "applicationX2Rn7! kXk2estC¥donc différentiable surRn, car polynômiale. L"ap- plicationX7!AXest linéaire, donc différentiable. Par conséquent, l"applicationJest dif- férentiable en tant que composée de fonctions qui le sont. De plus, pour toutX2Rm, on a

J(X) =hAX,AXi=hA>AX,Xi,

avecA>A2 Sm(R). On en déduit que la différentielle deJenXest l"application linéaire d

XJ:h2Rm7!2hA>AX,hi.

(b) Ut ilisonsle théorème de composition des dif férentielles.On obtient d

XG(h) =dJ(X)fdXJ(h) =2f0(J(X))A>Ah.

pour touth2Rm.Exercice 2.On considère la fonctionf:R2!Rdéfinie par f(x,y) =( x3+y3x

2+y2si(x,y)6= (0,0)

0 sinon.

La fonctionfest-elle continue surR2? de classeC1surR2? Correction.La fonctionfestC¥surR2nf(0,0)gen tant que produit, quotient ne s"annulant pas etc. de fonctions qui le sont. Reste à étudier la régularité en(0,0). On a

8(x,y)2R2nf(0,0)g,jf(x,y)j jxj3x

2+jyj3y

2=jxj+jyj !(x,y)!(0,0)0.

en(0,0). En effet, soitt6=0 et(x,y)6= (0,0). On a f(tx,ty)f(0,0)t =t3(x3+y3)t

3(x2+y2)!(x,y)!(0,0)x

3+y3x 2+y2.

Or, sifétait différentiable en(0,0), cette limite coïnciserait avecd(0,0)f(x,y)et serait en particulier

linéaire par rapport à(x,y)ce qui n"est pas le cas.Exercice 3.(examen, juin 2018)Soitf:R2!R, une fonction différentiable. Soitx02R2. On

noterf(x0)le gradient defenx0.

1.Soit d2R2, une direction non nulle telle quekrf(x0) +dk krf(x0)k.

Montrer quedest une direction de descente1defenx0. Trouver alors le pas optimalr2R minimisant la fonctionR3r7! krf(x0) +rdk. Exhiber une direction de descente qui n"appartient pas àvect(rf(x0))lorsquerf(x0)6=0. 2. Soit c2RetLc=fx2R2jf(x) =cg, la ligne de niveaucdef. On suppose qu"une représentation paramétrique deLcest donnée parx=g(t)avect2Roùg:R!R2est une fonction différentiable telle queg(0) =x0. Montrer querf(x0)est perpendiculaire au vecteur tangent àLcenx0. 3. Soit c2R. Les dessins de la figure ci-dessous représentent la ligne de niveaucd"une fonction quadratiquef:R2!R. Dans quels dessins (A ou B ou les deux) la directiondest-elle de descente au pointx? Une justification précise est attendue.Correction. 1.

Puisque krf(x0) +dk krf(x0)k, on élève chacun des membres de l"inégalité au carré et on

les développe. On obtientkrf(x0)k2+2hrf(x0),di2+kdk2 krf(x0)k2et par conséquent, hrf(x0),di2 12 kdk2<0. Par conséquent, f(x0+#d)f(x0)# =hrf(x0),di2+o(#) 12 kdk2+o(#). Par conséquent, le second membre est strictement négatif si#est assez petit et la conclusion s"ensuit. Pour trouver le pas optimal, posonsj(r) =krf(x0) +rdket remarquons que le problème inf Rjest équivalent au problème infRj2. Or,j2(r) =krf(x0)k2+2rhd,rf(x0)i+r2kdk2, donc le minimum est atteint enr=hd,rf(x0)ikdk2et vaut infRj=krf(x0)k2hd,rf(x0)i2kdk2. En particulier, tout vecteur de la formed=rf(x0) +#u, oùuest un vecteur unitaire et#2 ]0,krf(x0)k[est une direction de descente. 2. Le vecteur tangent au point x0est donné parg0(0). La relationf(x) =cs"écrit encoref(g(t)) =c

pour toutt2R. Dérivons cette relation en utilisant la composition des différentielles, il vient

hrf(x0),g0(0)i=0, autrement ditrf(x0)est perpendiculaire au vecteur tangent àLcenx0. 3. Notons d"abor dque deux lignes de niveaux cetc0avecc6=c0ne peuvent pas se croiser, car sinon, on auraitc=c0. Les lignes de niveau d"une fonction quadratique deR2sont des coniques (par

définition), des ellipses ici puisque les courbes sont fermées. Par conséquent, toutes les lignes

de niveau à l"intérieur de l"ellipse sont encore fermées donc sont des ellipses ayant toutes même

centre. Puisque l"opposé du gradient enypointe vers une direction de descente, on en déduit qu"une direction sortante de l"ellipse sera une direction de descente. Par conséquent,dest une

direction de descente dans le casAet pas dans le casB.1. autrement dit qu"il existe#0>0 tel quef(x0+#d)

2 Analyse des problèmes d"optimisation sans contrainte

Exercice 4.On considère la fonctionfdéfinie surR2par f(x,y) =x4+y42(xy)2. 1. Montrer qu"il existe (a,b)2R2+(et les déterminer) tels quef(x,y)ak(x,y)k2+bpour tous(x,y)2R2, où la notationk kdésigne la norme euclidienne deR2.

En déduire que le problème

inf(x,y)2R2f(x,y)(P) possède au moins une solution. 2.

La fonction fest-elle convexe surR2?

3. Déterminer les p ointscritiques de f, et préciser leur nature (minimum local, maximum local, point-selle, ...). Résoudre alors le problème(P).

Correction.

1.fest polynômiale donc de classeC¥(R2). En utilisant le fait quexy 12

(x2+y2), on écrit f(x,y)x4+y42x22y2+4xyx4+y24x24y2, pour tout(x,y)2R2. En utilisant le fait que pour tout(X,#)2R2,X4+#42#X20, il vient f(x,y)(2#4)x2+ (2#4)y22#4.

Choisissons par exemple#=3, on en déduit

f(x,y)2(x2+y2)162!k(x,y)k!+¥+¥,

ce qui prouve quefest coercive surR2qui est fermé et de dimension finie. D"après le théorème

du cours, le problème(P)admet au moins une solution. 2. Pour étudier la convexité de f(qui est de classeC2surR2), calculons sa matrice hessienne en tout point(x,y)deR2. On a Hessf(x,y) =43x21 1

1 3y21

Rappelons quefest convexe surR2si, et seulement si sa matrice hessienne est semi-définie positive en tout point. Or, on vérifie aisément que les valeurs propres de Hessf(0,0)sont 0 et

2. Par conséquent,fn"est pas convexe.

3. Les points critiques de fsont donnés par les solutions derf(x,y) = (0,0), autrement dit, les points critiques sont solutions du système : x3(xy) =0 y

3+ (xy) =0,x3+y3=0

y

3+ (xy) =0,y=x

x 32x=0
On en déduit quefadmet trois points critiques :O(0,0),A(p2,p2)etB(p2, p2).

fétant de classeC2, on va utiliser la caractérisation des points critiques à l"aide de la hessienne

calculée à la question précédente.

Point A: Hessf(A) =20 4

4 20 donc la trace de Hessf(A)vaut 40 et son déterminant 384. On en déduit que Hessf(A)possède deux valeurs propres strictement positives donc queA est unminimiseur localpourf. Point B: Hessf(B) =Hessf(A), donc la même conclusion que pour le pointAs"impose.

Point O: Hessf(O) =4 4

44
, donc la trace de Hessf(O)vaut8 et son déterminant est nul. Il vient que ses valeurs propres sont 0 et8. On ne peut donc rien conclure dans ce cas à l"aide de la matrice hessienne. En revanche, on peut donner un argument à la main : soit x2Rtel quejxj<2. On af(x,x) =2x48x2=2x2(4x4). Or,jxj<2 donc 4x2>0 et on en déduit quef(x,x)<0. De même, soitx2R. On af(x,x) =2x40. Puisque

les inégalités précédentes sont obtenues pour desxarbitrairement petits, on en déduit que le

point(0,0)est unpoint-sellepourf.

En conclusion, puisque le problème(P)possède une solution, la caractérisation des points cri-

tiques defnous assure que inf

(x,y)2R2f(x,y) =f(A) =f(B) =8.Exercice 5.(examen - juin 2018)On définit la fonctionJ:R2!RparJ(x,y) =y43xy2+x2.

1.

Déterminer les p ointscritiques de J.

2. Soit d= (d1,d2)2R2. En utilisant l"applicationR3t7!J(td1,td2), montrer que(0,0)est un minimum local le long de toute droite passant par(0,0). 3. Le p oint(0,0)est-il un minimum local de la restriction deJà la parabole d"équationx=y2? 4. Calculer la matrice hessienne de J. Quelle est la nature du point critique(0,0)?

Correction.

1.

On résout : rJ(x,y) =0()3y2+2x=0

4y36xy=0()x=32

y2 y

3=0()(x,y) = (0,0).

2. Soit t2R. On aJ(td1,td2) =t4d423t3d1d22+t2d21.Supposonsd16=0. Puisquey0(t) =4t3d42

9t2d1d22+2d21tety00(t) =12t2d4218td1d22+2d21, on ay0(0) =0 ety00(0) =2d21>0, donc 0 est

un minimum local dey. Sid1=0 etd26=0, alorsJ(0,td2) =t4d42et 0 est un minimum local de y. Enfin, le casd=0 est trivial. La conclusion attendue s"ensuit. 3. Soit (x,y)2R2tel quex=y2. Alors,J(x,y) =y4et il est alors clair queJ(x,y)Jà cette parabole. 4.

On a Hess J(x,y) =26y

6y12y26x

et HessJ(0,0) =2 0 0 0 . Puisqu"une valeur propre de la hessienne en(0,0)est nulle, on ne peut rien conclure de ce calcul. En revanche, les deux

questions précédentes prouvent que(0,0)est un point selle deJ.Exercice 6.(moindres carrés)SoitN2N. On considère un nuage de pointsf(ti,xi)g1iN, et

on cherche à mettre en oeuvre unerégression parabolique, autrement dit, on recherche la paraboleP

d"équationy=at2+bt+c, oùa,betcsont trois réels à déterminer, telle que la somme sur tous

les indicesivariant de 1 àNdu carré de la distance du point(ti,xi)au point de même abscisse sur

Psoit minimale.

1.

Écrire ce p roblèmecomme un p roblèmede minimisation quadratique, c"est-à-dire un p roblème

de la forme inf

X2RnJ(X)avecJ(X) =12

hAX,Xi hb,Xi, (Q) avecA2 Sn(R),b2Rn. On devra donc explicitern,Aetb.

On utilisera la notationSk=åNi=1tki.

2. Discuter de l"existence des solutions d"un tel p roblème. 3. On supp oseque la matrice Aest définie positive. Démontrer que(Q)possède une unique solution.

Correction.

1.

Le pr oblèmes"écrit

inf

X2R3J(X)avecX=0

@a b c1 A etJ(X) =Nå i=1(xiat2ibtic)2.

ÉcrivonsJ(X) =kMXkk2avecM=0

B @t 21t11
t

2NtN11

C

Aetk=0

B @x 1... x N1 C

A. D"après le cours sur la

méthode des moindres carrés, on a

J(X) =12

hAX,Xi hb,Xi avecn=3,A=M>M2 S3(R)etb=M>k2R3. On calculeA=0 @S 4S3S2 S 3S2S1 S 2S1N1 A 2. Ce pr oblèmeest équivalent au pr oblèmede minimiser la distance euclidienne de kau sous es- pace vectoriel (de dimension finie) Im(M). C"est donc un problème de projection orthogonale, et il admet une solution. 3. Dans ce cas, on sait que Hess J(X) =Aqui est définie positive. Par conséquent,Jest strictement convexe, etJpossède au plus un minimum dansRN. Comme on a vu qu"elle en possède au

moins un, on conclut à l"existence et l"unicité.Exercice 7.(moindres carrés)On considère la fonctionfdéfinie sur l"intervalle[1,1]parf(x) =

x

3. L"espaceC0([1,1])des fonctions continues sur[1,1]est muni du produit scalaire défini par

hh,gi=R1

1h(x)g(x)dxet on notek kla norme associée, définie parkhk=phh,hi, pour tous

(h,g)2(C0([1,1])2.

On souhaite déterminer le polynômePde degré inférieur ou égal à 1 qui approche le mieuxfau sens

des moindres carrés, c"est-à-dire qui minimisekfPk2parmi tous les polynômes de degré inférieur

ou égal à 1 (sous réserve qu"il existe et soit unique). 1.

Mettre ce p roblèmesous la fo rmed"un p roblèmede moindres ca rrésde dimension finie. Quelle

est cette dimension? 2. Étudier l"existence/l"unicité des solutions de ce p roblème. 3.

Résoudre ce p roblème.

Correction.

1. Le pr oblèmed"optimisation sous-jacent s"écrit inf (a,b)2R3J(a,b), avecJ(a,b) =Z 1

1(x3axb)2dx.

On calcule alors

J(a,b) =Z

1

1(x6+a2x2+b22ax42bx3+2abx)dx=12

hAX,Xi h˜b,Xi+c, avecX= (a,b)>,A=4/3 0 0 4

˜b=4/5

0 etc=27 . On s"est ainsi ramené à un problème d"optimisation de dimension 2.

2.Le pr oblèmed"optimisation précédent est un pr oblèmed"optimisation quadratique donc la ma-

trice hessienne associée est définie positive (cela se retrouve d"ailleurs en utilisant le formalisme

des problèmes de moindres carrés menant à l"équation normale). On en déduit que la fonctionJ

est coercive surR2qui est fermé et de dimension finie donc ce problème possède une solution unique. 3. L "équationnormale s"écrit AX=˜bqui se résout directement. On obtient :X=3/5

0Exercice 8.Soita2R. On définitfa:(x,y)7!x2+y2+axy2x2y.

1. P ourquelles valeurs de a, la fonctionfaest-elle convexe? Et strictement convexe? 2. Discuter en fonction des valeurs du pa ramètreade l"existence de solutions au problème d"op- timisationinfffa(x,y),(x,y)2R2g. 3. Lo rsquea2]2,2[, résoudre le problème précédent.

Correction.

1.

La fonction faestC¥surR2car polynômiale. Pour étudier la convexité def, calculons sa hes-

sienne : pour tous(x,y)2R2, hessf(x,y) =2a a2 . Cette matrice ne dépend pas dexet y. Etant symétrique réelle, elle est diagonalisable et on notel1etl2ses valeurs propres. On a tr(hessfa(x,y)) =l1+l2=4>0, doncfan"est jamais concave. De plus, det(hessfa(x,y)) = l si, et seulement sia2]2,2[et n"est ni convexe, ni concave sinon. 2. Souvenons-nous du cours sur l"optimisation de fonctions quadratiques : sia2]2,2[, hessfaest constante et appartient àS++n(R). Par conséquent,faest strictement convexe et coercive (cf. cours) surR2qui est fermé et de dimension finie. Par conséquent, le problème inf

R2faa une unique solution.

sia2Rn[2,2], la matrice hessfaa une valeur propre strictement négativem, et il existe une direction ~e2R2(vecteur propre associé àm) dans laquellef(t~e)! ¥quandt!+¥. Par conséquent, le problème inf

R2fan"a pas de solution.

Casa2 f2,2g. Dans ce cas, la matrice hessfaest semi-définie positive, mais pas définie positive. D"après le cours, le problème inf

R2faa une solution si, et seulement si(2,2)>2

Im(hessfa). Or, puisquea=2,

hessfah1 h 2 =2h1+ah2 ah 1+2h2 =h12 a +h2a 2 )Imhessfa=vect2 a Par conséquent, sia=2,(2,2)>2Im(hessfa)et le problème infR2faa une infinité de solutions. Sia=2,(2,2)>/2Im(hessfa)et le problème infR2fan"a pas de solution. 3.

Déterminons les points critiques de fa:

rfa(x,y) =0,2x+ay2

2y+ax2

=0,x y =22+a 1 1 D"après l"étude précédente, dans le cas considéré, le problème inf

R2faa une unique solution qui

est donc donnée parx=y=22+aet l"infimum vaut alors42+aExercice 9.SoitA2 S+n(R). On considère la fonctionf:Rnnf0Rng !Rdéfinie par

f(x) =hAx,xikxk2, oùh,iest le produit scalaire euclidien deRnetk kla norme induite. 1. Montrer que festC¥sur son ensemble de définition.

2.Montrer que les p roblèmesd"optimisation

inf x2Rnnf0Rngf(x)et supquotesdbs_dbs29.pdfusesText_35

[PDF] Extrait du support Outlook 2007 - Messagerie et Contacts - Office Doc

[PDF] Correction des exercices du fascicule d exercices de Biochimie

[PDF] MÉTABOLISME ÉNERGÉTIQUE - CORRIGÉ - EXERCICE #10

[PDF] Exercices résolus de Chimie Physique - 3ème édition

[PDF] Thermodynamique 2e année MP-MP*/PC-PC*/PSI-PSI*/PT-PT

[PDF] Physique Statistique Exercices de Travaux Dirigés

[PDF] FICHE EXERCICES SUPPLÉMENTAIRES

[PDF] Polynômes et fractions rationnelles

[PDF] Technologie des Systèmes Hydrauliques - Technologue pro

[PDF] Exercice 31 - Chapitre 3 : Les principes comptables - HEC Montréal

[PDF] Probabilités composées

[PDF] Programmation Fraisage CN Exercice N°3

[PDF] Corrige exercices propositions subordonnees

[PDF] Exercices Radioactivité et réactions nucléaires

[PDF] IE4 initiation au raisonnement déductif - Free