[PDF] Corrige Examen 2016-17 Exercice 1. (sur environ 12

View - Download Corrige Examen 2016-17

Previous PDF

Next PDF

Optimisation, algorithmique (MML1E31)(M1 Maths, 2016-2017)

Examen du mercredi 4 janvier 2017

Corrigé

Les documents suivants sont autorisés :

P olycopiésdis tribuésen cours et notes de cours manuscrites corr espondantes, Sujets de TP i mpriméset notes manuscrites corr espondantes. La consultation de tout autre document (livres, etc.) et l"utilisation de tout appareil élec- tronique sont interdites.

Exercice 1.(sur environ 12 points)

Rappel sur les fonctionnelles quadratiques :On rappelle qu"une fonctiong:Rn!Rest une fonctionnelle quadratique s"il existe une matrice carrée symétriqueA2 Mn(R), un vecteur b2Rnet une constantec2Rtels que

8x2Rn; g(x) =12

hAx;xi hb;xi+c (et alors la matriceA, le vecteurbet la constantecsont uniques). Fonctionnelle des moindres carrés :Soientn;p2Ndeux entiers non nuls. SoientA2 M p;n(R)une matrice rectangulaire,b2Rpun vecteur. On définit la fonctionf:Rn!Rpar f(x) =12 kAxbk2: Attention on utilisera la même notation pour la norme et le produit scalaire dansRnet dansRp, mais les vecteurs ne sont a priori pas de la même taille! 1. Montrer quefestunefonctionnellequadratiqueetpréciserlamatricecarréeA02 Mn(R), le vecteurb02Rnet la constantec02Rassociés àf. 2. Donner l"e xpressiondu gradient rf(x)et de la matrice hessienner2f(x)defen tout

pointx2Rn(on pourra se référer à un résultat du cours plutôt que de faire les calculs).

3.

Montrer que fest convexe.

4. Montrer que fest fortement convexe si et seulement siker(A) =f0g. 5. Soit x2Rntelquerf(x)6= 0.Rappelerladéfinitiond"unedirectiondedescented2Rn au pointxet montrer qued2Rnest une direction de descente si et seulement si hAxb;Adi<0 (en particulierAd6= 0). 1

6.Soit x2Rntel querf(x)6= 0etdune direction de descente au pointx. Montrer que le

problème d"optimisation inft2Rf(x+td) admet une unique solution donnée par t ?=hrf(x);dikAdk2:(1) Algorithme de gradient conjugué pour les moindres carrés :On suppose désormais que ker(A) =f0g. On rappelle ci-dessous le pseudo-code de l"algorithme du gradient conjugué afin de minimiser une fonctionnelle quadratique g(x) =12 hA0x;xi hb0;xi+c0

lorsqueA0est symétrique définie positive (ce qui revient à résoudre le système linéaireA0x=

b

0). On rappelle que, par convention, pour cet algorithme ce sont les vecteurs opposésd(k)qui

sont des directions de descente.Algorithme 1 :Algorithme du gradient conjuguéDonnées :Un point initialx(0)2Rn, un seuil de tolérance" >0

Résultat :Un pointx2Rnproche dex?

Initialiserx:

x x(0); k 0;

Première itération :

1.

Calculer d(0)=rg(x)(d(0)=rg(x(k)))

2. Calculer le pas de desc enteoptimal t(0)dans la direction de descented(0) 3.

Mettre à jour x:

x x(1)=x(0)t(0)d(0); (attention c"est bien un signe) k k+ 1; tant quekrf(x)k2> "2faire1.Calculer d(k)=rg(x(k)) +krg(x(k))k2krg(x(k1))k2d(k1). 2. Calculer le pas de descente optimal t(k)dans la direction de descented(k) 3.

Mettre à j ourx:

x x(k+1)=x(k)t(k)d(k); (attention c"est bien un signe) k k+ 1; fin7.En utilisant l"équation ( 1), donner l"expression des pas de descentet(0)ett(k),k>1, pour la fonctionf(x) =12 kAxbk2en fonction derf(x(0)),Aetd(0)pourt(0)etrf(x(k)), Aetd(k)pourt(k)(en faisant attention à la convention sur les directions de descentes). 2

8.Ecrire une fonction scilab

function x = grad_conj_moindres_carres(A, b, x0, eps) qui applique l"algorithme du gradient conjugué à la fonctionnellef(x) =12 kAxbk2en partant du pointx0et avec une tolérance"pour le critère d"arrêt. On pourra introduire une fonction intermédiaire qui calcule le gradient def(non obligatoire).

Solution de l"exercice 1.

1. f(x) =12 kAxbk2 12 hAxb;Axbi 12 hAx;Axi hb;Axi+12 hb;bi 12 hATAx;xi hATb;xi+12 kbk2:

Doncfest quadratique avec

A

0=ATA; b0=ATb; c=12

kbk2: 2. D"après les e xpressiondu gradient et de la matrice hessienne des fonctionnelles quadra- tiques, rf(x) =A0xb0=AT(AxB) et r

2f(x) =A0=ATA:

3.

Pour tout h2Rn,

hr

2f(x)h;hi=hATAh;hi=kAhk2>0:

Donc la matrice hessienne defest positive en tout pointx2Rn,fest donc convexe. On peut également justifier quefest convexe car c"est la composée de l"application affine x7!Axbet de la fonction convexey7! kyk2. 4. Supposons que fsoit fortement convexe. Alors il existem >0tel que

8h2Rn;hr2f(x)h;hi>mkhk2:

Orhr2f(x)h;hi=kAhk2. D"où,kAhk2>mkhk2pour touth2Rn, en particulier, h6= 0impliqueAh6= 0, doncker(A) =f0g. Supposons queker(A) =f0g. AlorsA0=ATAest une matrice réelle symétrique définie positive. Elle admet une valeur propre minimale >0et on a hATAh;hi>khk2; doncfest fortement convexe pourm=. 3

5.d2Rnest unedirection de descenteau pointxsihrf(x);di<0. Ainsidest une

direction de descente ssi hAT(Axb);di<0 soit ssi hAxb;Adi<0: 6. La fonction ':t7!f(x+td)est un trinôme du second degré pour la variablet. En effet, on a '(t) =f(x+td) =f(x) +thAT(Axb)|{z} =rf(x);di+t22 kAdk2: Cette fonction est minimale au pointttel que'0(t) = 0, soit hrf(x);di+tkAdk2= 0 d"où l"expression det?. 7.

On en appli quantl"équation (

1 ) avecd=d(0)=rf(x(0)), t (0)=kd(0)k2kAd(0)k2: t (k)=hrf(x(x));d(k)ikAd(k)k2: 8. function x = grad_conj_moindres_carres(A, b, x0, eps) x = x0 k = 0 gfx = A" *(A*x-b) sqngfx = gfx" *gfx d = gfx;

Ad = A

*d; t = sqngfx/(Ad" *Ad) x = x - t *d sqngfxold = sqngfx gfx = A" *(A*x - b) sqngfx = gfx" *gfx k = k+1 while(sqngfx>eps^2 & k < 1000) d = gfx + sqngfx/sqngfxold *d

Ad = A

*d; t = gfx" *d/(Ad"*Ad) x = x - t *d sqngfxold = sqngfx gfx = A *x - b sqngfx = gfx" *gfx k = k+1 4 disp([k,sqngfx]); end endfunction

Exercice 2.(sur environ 9 points)

Soitn>2un entier. On notee1;e2;:::;enles vecteurs de la base canonique deRn. On notekxk=phx;xila norme euclidienne usuelle deRnet kxk1= maxi2f1;:::;ngjxij: Dans la suite de l"exercice,f:Rn!Rdésigne une fonction deux fois différentiable sur R net fortement convexe telle que

8x;h2Rn; mkhk26hr2f(x)h;hi6Mkhk2

avec0< m6M. On notex?le point oùfatteint son minimum global etp?=f(x?)la valeur minimale def. Le but de l"exercice est d"étudier la convergence d"un algorithme de descente qui prend pour direction de descente à l"étapekle vecteur d (k)=@f@x i(x(k))ei oùiest le plus petit indice pour lequel@f@x i(x(k))=krf(x(k))k1: Plus précisément, on considère l"Algorithme 2

ci-dessous. Algorithme 2 :Algorithme de descente selon la dérivée partielle maximaleDonnées :Un point initialx(0)2Rn, un seuil de tolérance" >0

Résultat :Un pointx2Rnproche dex?

Initialiserx:

x x(0); k 0; tant quekrf(x)k> "faire1.Déterminer l eplus petit indice itel que@f@x i(x(k))=krf(x(k))k1 2. Déterminer un pas de descente t(k)>0par la méthode exacte pour la direction de descented(k)=@f@x i(x(k))ei (ou par la méthode de rebroussement de paramètreset). 3.

Mettre à jour x:

x x(k+1)=x(k)+t(k)d(k); k k+ 1; fin5 Implémentation de l"Algorithme2 a vecla méthode de r ebroussementOn suppose que les fonctions function fx = f(x)etfunction gfx = gradf(x) sont définies dans scilab. On rappelle qu"en Scilab siuest un vecteuru= (u1;:::;un), alors -abs(u)renvoie le vecteur(ju1j;:::;junj). -[v,i] = max(u)renvoie la valeur maximalev= maxiuides coordonnées deu ainsi que le plus petit indiceitel queui=v= maxiui. 1.

Ecrire une fonction scilab

function x = desc_der_partielle_max(x0, eps, alph, bet) qui prend en entrées un point initialx(0)2Rn, un seuil de tolérance" >0, et deux paramètreset, et renvoie le pointxcalculé par l"algorithme de descente selon la dérivée partielle maximale utilisant la méthode de rebroussement pour le calcul du pas de descente (avec les paramètres2[0;12 [et2]0;1[).

Etude de la convergence de l"Algorithme

2 a vecla méthode exacte Le but de la fin de l"exercice est de démontrer la convergence de l"Algorithme 2 a vecla méthode e xactepour le calcul du pas de descente. On rappelle que la forte convexité defimplique que pour tout x2Rn, krf(x)k2>2m(f(x)p?): On suppose qu"à l"étapekde l"Algorithme2 le point x(k)est différent dex?. On noteile plus petit indice tel que@f@x i(x(k))=krf(x(k))k1et on posed(k)=@f@x i(x(k))ei. 2. Montrer que hrf(x(k));d(k)i=krf(x(k))k21(ce qui montre qued(k)est bien une direction de descente pour le pointx). 3.

Montrer que pour tout t >0,

krf(x(k))k21: 4.

En déduire que

f(x(k+1))6f(x(k))12Mkrf(x(k))k21: 5.

Démontre rque pour tout x2Rn,kxk21>1n

kxk2. 6. Montrer ,à l "aidedes deux questions précédentes, que f(x(k+1))p?6 1mnM f(x(k))p?: 7.

Conclure s urla con vergencede l"Algorithme

2

Solution de l"exercice 2.

1. 6 function x = desc_der_partielle_max(x0, eps, alph, bet) x=x0; gfx=gradf(x); sqngfx = gfx" *gfx; while(sqngfx > eps^2) [ninfgfx,i] = max(abs(gfx)); d = zeros(gfx); d(i) = -gfx(i); t=1; xk = x; fxk = f(xk); x = xk + t *d; fx = f(x); while(fx > fxk - alph *t*ninfgfx^2) // ou fxk + alph *t*gfx"*d sans utiliser la question 2) t = bet *t; x = xk + t *d; fx = f(x); end gfx=gradf(x); sqngfx = gfx" *gfx; disp(fx) end endfunction // Test: function fx = objectif(x,A,b) fx = sum(exp(A *x + b)); endfunction function gfx = grad_obj(x,A,b) gfx = A" *exp(A*x + b); endfunction // Attention : Besoin de definir les variables A et b avant d"appeler ces fonctions deff("fx=f(x)","fx = objectif(x,A,b)"); deff("gfx=gradf(x)","gfx = grad_obj(x,A,b)"); // Definition de la fonctionnelle

A = [ 1 3 ; 1 -3 ; -1 0 ]

b = [ -0.1 ; -0.1 ; -0.1 ] x0 = [-2 ; 3] eps = 10^(-8) alph = 0.4; bet = 0.8; 7 // Solution [xstar, vg_min] = fsolve(x0, gradf) pstar = f(xstar) x = desc_der_partielle_max(x0, eps, alph, bet) 2. On a hrf(x(k));d(k)i=@f@x i(x(k))2=krf(x(k))k21: 3. P ardéfinit ionde la méthode e xactepour le calcul du pas de descente, f(x(k+1)) = mint>0f(x(k)+td(k)); donc pour toutt >0, on a bien f(x(k+1))6f(x(k)+td(k)): D"après la formule de Taylor-Maclaurin, il existez2[x(k);x(k)+td(k)]tel que f(x(k)+td(k)) =f(x(k)) +thrf(x(k));d(k)i+t212 hr2f(z)d(k);d(k)i:

Or par hypothèse,

hr

2f(z)d(k);d(k)i6Mkd(k)k2=M@f@x

i(x(k))2=Mkrf(x(k))k21; d"où la deuxième inégalité. 4. On choisitlet >0quiminimisel"expressionf(x(k))tkrf(x(k))k21+t2M2 krf(x(k))k21.

Il est donné pourttel que

krf(x(k))k21+tMkrf(x(k))k21= 0 soit t=1M

Pour cette valeur deton a

f(x(k))tkrf(x(k))k21+t2M2 krf(x(k))k21=f(x(k))12Mkrf(x(k))k21:

Ainsi, on a bien

f(x(k+1))6f(x(k))12Mkrf(x(k))k21: 5. Soit x2Rn. Alors pour touti2 f1;:::;ng,x2i6kxk21, d"où kxk2=nX i=1x

2i6nkxk21:

Donc on a bienkxk21>1n

kxk2. 8

6.On a

krf(x(k))k21>1n krf(x(k))k2>2mn (f(x)p?); d"où f(x(k+1))p?6f(x(k))p?12Mkrf(x(k))k216 1mnM f(x(k))p?: 7.

P arrécurrenc eimmédiate on a

f(x(k))p?6 1mnM kf(x(0))p? et1mnM

2[0;1[donc l"Algorithme2 con vergelinéairement.

9quotesdbs_dbs7.pdfusesText_13

[PDF] optimisation convexe exercices corrigés

[PDF] fonction strictement convexe

[PDF] optimisation quadratique sous contrainte linéaire

[PDF] optimisation convexe pdf

[PDF] fonction convexe plusieurs variables

[PDF] modélisation et simulation d'un moteur ? courant continu matlab

[PDF] modélisation mcc

[PDF] simulation mcc simulink

[PDF] asservissement et regulation de vitesse d'un moteur a courant continu

[PDF] modélisation d'un moteur ? courant continu

[PDF] equation differentielle moteur courant continu

[PDF] schéma bloc moteur ? courant continu

[PDF] commande pid d'un moteur ? courant continu pdf

[PDF] modélisation machine asynchrone simulink

[PDF] onduleur triphasé matlab