[PDF] [PDF] 4GMM Lundi 12/01/2015 Analyse convexe & optimisation Durée

View - Download [PDF] 4GMM Lundi 12/01/2015 Analyse convexe & optimisation Durée

Previous PDF

Next PDF

INSA de Toulouse - 4GMM Lundi 12/01/2015

Analyse convexe & optimisation

Durée approximative : 2h.

Seuls le polycopié et les notes de cours sont autorisés . Seuls le polycopié et les notes de cours sont autorisés . Exercice 1.Pour les ensemblesXsuivants, dites si l"ensemble est convexe et détermi- nez l"opérateur de projectionXpar la méthode de votre choix. Déterminer l"opérateur de projection signifie donner son expressionX(x)pour toutx. Note : pour cet exercice, seul le résultat final comptera, ce n"est donc pas la peine de trop justifier.

1.X=fx0gavecx02Rn.

Cet ensemble (singleton) est convexe etX(x) =x0pour toutx.

2.X=fx2R2;kxk21g.

Cet ensemble est un disque (convexe). On a

X(x) =xsix2X

xkxk2sinon:

3.X=fx2R2;pkxk21g.

Cet ensemble est le même que le précédent, tout est donc pareil.

4.X=fx2R2;kxk2= 1g.

Cet ensemble est un cercle (donc non convexe). La projection est donnée par :

X(x) =

xkxk2six6= 0

Xsix= 0:

Notez que la projection n"est pas unique pourx= 0. L"unicité n"est vraie que pour les ensembles convexes. Exercice 2.Sur un schéma dessiner proprement quelques lignes de niveau de la fonc- tionf(x1;x2) = 2jx1j+x22.

Correction

1 -2-1.5-1-0.500.511.52-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 1 2

0.5Figure1 - Lignes de niveau de la fonctionf(x1;x2) = 2jx1j+x22.

Exercice 3.Dans ce problème, on s"intéresse à la gestion numérique d"une contrainte affine. Ce type de contrainte apparaît abondamment dans les milieux industriels et aca- démiques. SoitA2Rmn,b2Im(A),X=fx2Rn;Ax=bget f(x) =X(x) =0six2X +1sinon: Le but de cet exercice est d"étudier la fonctionfen utilisant les outils d"analyse convexe vus en cours. On travaille avec la norme Euclidienne et les produits scalaires usuels notés k k

2eth;irespectivement.

Partie I :La première partie de cet examen est destinée à permettre une meilleure compréhension du problème. On commence donc par un exemple simple et on posen= 2, m= 1,A= [1;0],b= 1.

1. Dessiner l"ensembleX.

2. Dessiner le cône normalNX(x)au pointx=1

1

3. Déterminer la projectionX(x)du pointx=2

3 Correction :Le schéma de la figure 2 résume les résultats. 2 -1-0.500.511.522.53-2 -1 0 1 2 3 4 5 xy xΠ X(x) NX((1,1))Figure2 - EnsembleX, cône normalNX((1;1))et projectionX((2;3)). Partie II :Dans la deuxième partie de cet examen, on se propose d"étudier le problème d"un point de vue générique. La matriceAest arbitraire avec des lignes linéairement indépendantes etb2Im(A).

1. Montrer quefest convexe et fermée.

Correction :Soit2[0;1]et(x1;x2)2XX. On aA(x1+ (1)x2) = Ax

1+ (1)Ax2=b. L"ensembleXest donc convexe.

La fermeture est très simple dans l"absolu, mais difficile car les cours de topologie remontent à loin. Je donne ci-dessous une correction pour rafraîchir la mémoire des étudiants qui s"entraineraient pour un examen. Soit(xk)k2Nune suite de points dans Xqui converge versx. Il faut montrer que la limitex2X(c"est une des définitions de la fermeture). Commexk!x, on akxkxk1!0, donc toutes les composantes dexktendent vers celles dex. Soit(e1;:::;en)la base canonique deRn. On peut écrirexk=Pn i=1(i) kei etx=Pn i=1(i)eiavec(i) k!(i);8i. En notantA= (a1;:::;an), on a donc Ax kAx=Pn i=1((i) k(i))ai!0. CommeAxk=b, pour toutk, on en déduit queAx=b, doncx2X.

2. Montrer queX= x+ Ker(A)pour un certainxqu"on précisera.

Correction :Soitxun point qui satisfaitAx=b(par exempleA+b, oùA+est la pseudo-inverse deA). SoitY= x+ Ker(A). On souhaite montrer queX=Y. Soity2Y. On peut donc l"écrire sous la formey= x+y0oùy2Ker(A). Ainsi

Ay=Ax+Ay0=b. Doncy2X.

Réciproquement, soitx2X. Le vecteurxpeut être décomposé sous la forme x= x+x0oùx02Rn. Six0=2Ker(A), alorsAx06= 0etAx=Ax+Ax06=b. On a 3 donc bienx02Ker(A).

3. Soitx02X. En utilisant les remarques précédentes, montrer que

N

X(x0) = Ker(A)?:

Correction :Puisquex02X, il peut être décomposé sous la formex0= x+xker0avecxker02Ker(A). Le cône normal àXest défini par :

N

X(x0) =f2Rn;h;xx0i 0;8x2Xg

=f2Rn;h;x+xkerx0i 0;8xker2Ker(A)g =f2Rn;h;x+xker(x+xker0)i 0;8xker2Ker(A)g =f2Rn;h;xkerxker0i 0;8xker2Ker(A)g =f2Rn;h;xi 0;8x2Ker(A)g = Ker(A)?: Correction :Pourx0=2X, on aNX(x0) =;. Pour le montrer, on raisonne comme dans le cas précédent. On remarque d"abord quex0= x+x0avecx0=2Ker(A). On obtient ainsi : N

X(x0) =f2Rn;h;xx0i 0;8x2Xg

=f2Rn;h;xkerx0i 0;8xker2Ker(A)g =f2Rn;h;xi 0;8x2x0+ Ker(A)g L"objectif des questions suivantes est de calculer : x = Proxf(x0) = argmin x2Rnf(x) +12 kxx0k22:(1)

4. Que représentexgéométriquement?

Correction :On a

x = argmin x2X12 kxx0k22:

C"est donc la projection dex0surX.

5. Ecrire les conditions d"optimalité satisfaites par la solutionxdu problème (1).

Correction :En notantf(x) =12

kxx0k22+X(x)où

X(x) =0six2X

+1sinon, les conditions d"optimalité sont02@f(x). On a@f(x) =;pourx =2X, donc x

2X. De plus

@f(x) =xx0+NX(x) Les conditions d"optimalité sont donc02xx0+Ker(A)?etx2X. Ceci signifie bien quexest une projection orthogonale (le vecteurxx0est orthogonal à l"ensemble des contraintes).

6. Montrer queKer(A)?= Im(A).

4 Correction :C"est un exercice qui a été fait en 3MIC. C"est là encore pour les remettre les résultats qui me semblent importants en place. Le moyen le plus simple de le démontrer est le suivant. On commence par montrer queIm(A)?= Ker(A).

En effet :

x2Im(A)? ,hx;Ayi= 0;8y2Rm ,hAx;yi= 08y2Rm ,x2Ker(A): Pour conclure, on utilise le fait que pour tout sous-espaces vectorielsEetFtels queE=F, on aE?=F?. AinsiIm(A) = Im(A)??= Ker(A)?.

7. En déduire que les conditions d"optimalité peuvent se réécrire

xx0=Ay

A(x0+Ay) =b

Correction :D"après les questions précédentes, les conditions d"optimalité sont x2Xetxx02Ker(A)?. CommeKer(A)?= Im(A), on peut écrirexx0= A ypour un certainy2Rm. La conditionx2Xsignifie queAx=b, soit encore

A(x0+Ay) =b.

8. En déduire quex=x0+A(AA)1(bAx0).

Correction :L"équationA(x0+Ay) =bimplique quey= (AA)1(bAx0). Il suffit de l"injecter dans l"égalitéxx0=Aypour obtenir le résultat annoncé.

9. Justifier pourquoiAApeut-être inversée.

Correction :La matriceAApeut être inversée car on a supposé que les lignes deAsont linéairement indépendantes. La matriceAAest donc de rang plein. Note :la matriceA+=A(AA)1n"est rien d"autre que la pseudo-inverse deA. Le pointxaurait aussi pu être trouvé en utilisant des techniques d"algèbre linéaire. Partie III :Nous nous intéressons maintenant à un problème d"optimisation pratique. Soitg:Rn!Rune fonction convexe différentiable avec un gradientL-Lipschitz.

1. Ecrire un algorithme efficace pour résoudre le problème suivant :

min x2Rn;Ax=bg(x): Correction :On peut utiliser un algorithme de gradient projeté, ou mieux, un algorithme de gradient projeté accéléré. Le premier s"écrit ainsi : x 02X x k+1=X(xkrg(xk)): 5

On peut choisir=1L

Avec un algorithme accéléré :

y 02X x k=X(ykrg(yk)) y k=xk+k1k+ 2(xkxk1):

2. Quelle garanties théoriques de convergence pouvez-vous donner à cet algorithme?

Correction :Dans la descente de gradient projeté, le taux de convergence est de typeg(xk)g(x) =OLkx0xk22k Pour la descente accélérée,g(xk)g(x) =OLkx0xk22k 2 . Dans les deux cas, rien ne peut être dit sur la distance au minimiseur.

3. On suppose maintenant quegest-fortement convexe à gradientL-Lipschitz. Dé-

crire un algorithme de minimisation.

4. Quelles garanties théoriques de convergence pouvez-vous donner?

Correction :Les mêmes algorithmes peuvent être utilisés avec au moins les mêmes garanties. Cependant, la forte convexité permet d"obtenir des taux linéaires bien plus satisfaisants. Par exemple, l"algorithme de descente de gradient projeté avec=2+Lassure que kxkxk22=O Qg1Q g+ 1 k kx0xk2! et g(xk)g(x) =O L2 Qg1Q g+ 1 k kx0xk2! avecQg=L Pour la descente de gradient projetée accélérée, on obtient la même chose en rem- plaçantQ g1Q g+1 par pQ g1pQ g+1 dans les expressions ci-dessus. Notez que cette fois-ci on peut contrôler la distance au minimiseur. 6quotesdbs_dbs4.pdfusesText_8

[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

[PDF] cours de modélisation financière sous excel