[PDF] Travaux dirigés. 1 Optimisation & Analyse convexe Séance 6

View - Download Travaux dirigés. 1 Optimisation & Analyse convexe Séance 6

Previous PDF

Next PDF

Travaux dirig´es.1Optimisation & Analyse convexe S´eance 6 : Algorithmes pour l"optimisation avec contraintes Exercice 1 (Algorithme d"Uzawa : Cas de contraintes d"´egalit´e et in´egalit´e). SoitAune matricen×nsym´etrique d´efinie positive, et soitJune fonctionnelle d´efinie sur IR npar :

J(v) =12

(Av,v)-(b,v) o`ubest un vecteur donn´e de IRn. On consid`ere aussi deux matricesCE?IRp×netCI? IR m×n, ainsi que deux vecteursfE?IRp,fI?IRm. On note (P) le probl`eme d"optimisation sous contrainte : forme suivante : pourρ >0, ?λ?IF, Au+CTλ=b,(1a)

λ=PIF(λ+ρ(Cu-f)),(1b)

o`uC=?CE C I? ,f=?fE f I?

, et IF est un ensemble `a pr´eciser.3.Pour calculer une approximation de (1), nous consid`erons l"algorithme suivant :

(a)On choisit :λ0?IRp,ρ >0, etη >0.

On calculeu0solution deAu0=b-CTλ0.(b)Tant que?λk-λk-1?> ηou?uk-uk-1?> η, on d´efinit (uk+1,λk+1) parλ

k+1=PIF? k+ρ(Cuk-f)? ;u k+1est solution deAuk+1=b-CTλk+1.

Montrer que

2?C?2-2ρλmin(A)?

?uk-u?22. En d´eduire que si 0< ρ <2λmin(A)?C?2, alors il existeγ >0 tel que : ?λk-λ?22- ?λk+1-λ?22? Conclure que la suiteukconverge vers l"unique solutionude (P).

A-t on la convergence de la suiteλk?

2Travaux dirig´es.Exercice 2 (Algorithme d"Uzawa modifi´e).

SoitAune matrice sym´etrique d´efinie positive, et soitJune fonctionnelle d´efinie sur IRn par :

J(v) =12

(Av,v)-(b,v) o`ubest un vecteur donn´e de IRn. On cherche `a approcher la solution unique du probl`eme : (P) Trouveru?K:={v?IRn|Cv=f}tel queJ(u) = infv?KJ(v).

o`uCest une matricem×netf?IRm. On consid`ere le m´ethode it´erative suivante :(a)(uo,λo) donn´es dans IRn×IRm(b)(uk,λk) ´etant connus, calcul de (uk+1,λk+1) par :

u k+1=uk-ρ1?Auk-b+CTλk? k+1=λk+ρ1ρ2?Cuk+1-f?

o`uρ1, ρ2sont des param`etres strictement positifs.1.Rappeler pourquoi le minimiumuexiste et est unique, et pourquoi il existeλ?Rm

t.q.Au+CTλ=b.2.Montrer que siρ1>0 est suffisamment petit, alors

β:=?I-ρ1A?2<1,

o`u? · ?2d´esigne la norme matricielle induite par la norme euclidienne.3.On choisit le param`etreρ1pour que l"in´egalit´eβ <1 ait lieu. Montrer que si le

param`etreρ2est suffisamment petit, il existe une constanteγ >0 ind´ependante de l"entierktelle que :

2+β?uk-u?2n)-(?λk+1-λ?2mρ

2+β?uk+1-u?2n).

(? · ?net? · ?md´esignent respectivement les normes euclidiennes dans IRnet IRm.)4.En d´eduire que pour de tels choix de param`etresρ1etρ2, on a limk→+∞uk=u.5.Que peut on dire de la suite (λk) lorsque rang(C) =m?

Corrig´e 2 .1.Le probl`eme (P) admet une solution uniqueu?KpuisqueK?=∅est convexe ferm´e etJest une fonction continue, strictement convexe et "infinie `a l"infini" (car la matriceAest sym´etrique d´efinie positive). De plus la convexit´e deJimplique que le minimumuest caract´eris´epar ?λ?IRmtel que??J(u) +CTλ= 0

Cu=fou encore?Au+CTλ=b

Cu=f.

Travaux dirig´es.32.Comme la matriceI-ρ1Aest sym´etrique, d"apr`es la proposition B.0.2 de l"annexe

du poly, on a β=?I-ρ1A?2= sup{|μ|:μvaleur propore deI-ρ1A}. propres deI-ρ1Asont D"o`uβ= max{|1-ρ1λn|,|1-ρ1λ1|}. Donc si

0< ρ1<2λ

n, on aβ <1.3.On a : ??λk+1-λ??2 m=??λk-λ??2 m+ρ21ρ22??Cuk+1-f??2 m+ 2ρ1ρ2?λk-λ,Cuk+1-f? ??λk-λ??2 m+ρ21ρ22??C(uk+1-u)??2 m+ 2ρ2ρ1?CT(λk-λ),uk+1-u? ??λk-λ??2 m+ρ21ρ22??C(uk+1-u)??2 m-2ρ2?uk+1-u+ (I-ρ1A)(uk-u),uk+1-u? ??λk-λ??2 m+ρ2(ρ21ρ2??C??2-2)??uk+1-u??2 n+ 2ρ2β??uk-u??n??uk+1-u??n m+ρ2(ρ21ρ2??C??2-2)??uk+1-u??2 n+ρ2β??uk+1-u??2 n+ρ2β??uk-u??2 n. Si on poseγ= 2-2β-ρ21ρ2??C??2, il vient alors ??λk+1-λ??2 mρ ?λk-λ??2 mρ

2+β?uk-u?2n-γ?uk+1-u?2n.

Pour un choix fix´e deρ1tel queβ <1, il est possible de choisirρ2assez petit de mani´ere `a garantir queγ >0.4.La suite ??λk-λ??2 mρ

2+β?uk-u?2n?

k est d´ecroissante et minor´ee, donc conver-

gente. Il en r´esulte que?uk-u?n-→0.5.Si rang(C) =m,Cest surjective, doncC?est injective, ce qui implique que la

matriceCC?est inversible. Or d"apr`es l"algorithme, on a C ?λk=ρ-11(uk-uk+1) +b-Auk, donc en multipliant `a gauche parC, puis par (CC?)-1, on obtient k= (CC?)-1C(ρ-11(uk-uk+1) +b-Auk). Puisqueuk→u, le membre de droite converge vers (CC?)-1C(b-Au) =λ, par un calcul analogue, donc la suite (λk) converge versλ.

4Travaux dirig´es.Exercice 3 .SoitAune matriceN×Nsym´etrique d´efinie positive,b?RNetf?IRN.

On utilise ici la notationx≥ypour des vecteursx,y?IRNsixi≥yipour tout i= 1,...,N. On notera aussi par?·,·?le produit sacalaire dans IRN. Montrer l"´equivalence entre les assertions suivantes :1.uest solution du probl`eme ?Au≥b, u≥g?Au-b,u-g?= 0(2)2.uv´erifie u?K,et?Au-b,v-u?≥0?v?K.(3) avecK:={v?IRN, v≥g}.3.uest la solution du probl`eme min v?KJ(v) :=12 (v, Av)-(b, v).(4)4.uest solution de min(Au-b,u-g) = 0. Corrig´e 3 .Montrons d"abord l"´equivalence [(a)??(b)]. Supposons queu?IRNest solution de (2), doncu?K. De plus pourv?Kquelconque, on a : ?Au-b,u-g?= 0 =??Au-b,(u-v) + (v-g)?= 0 =??Au-b,v-u?=?Au-b,v-g?(5) CommeAu-b≥0 etv-g≥0, alors de (5) on conclut que (Au-b,v-u)≥0. D"o`u : uv´erifie bien (3). Inversement, siuest solution de (3), alorsu≥g. De plus, si pouri= 1,...,N, on prendvi?Kle vecteur d´efini par : v ij=? u jsii?=j

1 +ujsii=j

on a aussi : (Au-b,u-g)≥0. D"o`u (Au-b,u-g) = 0. Pour l"equivalence [(b)??(c)], il suffit de remarquer que (3) est la condition d"opti- malit´e du probl`eme (4). Cette condition est n´ecessaire et suffisante puisque la fonctionJ est convexe. Commentaires :Les probl`emes (2) et (4) sont ´equivalents donc ils mod´elisent le mˆeme probl`eme physique. Nous avons d´eja vu (pc4, exo4) que la valeurJ(v) est une approximation de l"energie potentielle

J(V) :=12

1 0 |?V(x)|2dx-? 1 0 f(x)V(x),dx

Travaux dirig´es.5o`ufest la fonction d´efinie parf(x) = 1, etVest un champs v´erifiant :V(xi) =vi. Le

probl`eme (4) est donc une approximation de la minimisation de l"energie potentielle de champsVsous la contrainteV≥G. Exercice 4 .SoitJune fonction continue, strictement convexe de IRndans IR, et "infinie `a l"infini" : lim?v?→+∞J(v) = +∞.(2) appelleUl"ensemble : x min v?UJ(v) (4)

admet une solution unique que l"on noterau.2.On introduit la fonctionJε: IRn-→IR d´efinie par :

J

ε(v) =J(v) +12ε?

??max?Cv-f; 0????2 m,(5) o`u l"on d´esigne par max ?Cv-f; 0?le vecteur de composantes max?? jC ijvj-fi; 0?? i=1,···,m.(a)Montrer que la fonctionG:v?-→??max?Cv-f; 0???2

mest convexe, continue.(b)Montrer queGest d´erivable sur IRnet que pour toutv?IRn, le gradient deG

envest :?G(v) = 2CTmax?Cv-f; 0?.(c)Montrer que, pour toutε >0, le probl`eme : min v?IRnJε(v) (6) admet une solution unique que l"on noterauε.3.On veut montrer maintenant que : lim

6Travaux dirig´es.4.On suppose maintenant que la fonctionJest continˆuement diff´erentiable. Montrer

que, pour toutε >0, la condition n´ecessaire d"optimalit´e deuεs"´ecrit : ?J(uε) +CTλε= 0,(8) o`uλεest un vecteur `a pr´eciser. Cette condition est - elle suffisante?

Expliquer pourquoiCTλεest born´ee ind´ependamment deε.5.On supposera dans toute la suite, que la matriceCest de rangm.(Rappel : SiC

est de rangmalorsCTest injective etCCTest inversible dans IRm.)(a)Montrer que la suite (λε) est born´ee.(b)En d´eduire qu"il existe un uniqueλ?IRmtel que :

Corrig´e 4 .

1.L"ensembleUest clairement convexe (carv?→Cvest lin´eaire donc convexe), et

ferm´e (carv?→Cvest continue). Existence du minimum : La fonctionJest continue et infinie `a l"infini (par hy- poth`ese) et l"ensembleUest ferm´e : en vertu du th´eor`eme 2.2.2, il existe une solution au probl`eme (4). Unicit´e du minimum : La fonctionJest strictement convexe (par hypoth`ese), et l"ensembleUest convexe, donc par le th´eor`eme 2.3.1, la solution du probl`eme (4) est unique. Il existe donc une unique solution au probl`eme (4), not´eeu.2.On notera queG=F◦A, avec A: IRn→IRm, v?→Cv-fetF: IRm→IR, x?→m? i=1max(xi;0)2. (a)La fonction IR→IR,x?→max(x;0) est convexe (faire un dessin), `a valeurs dans IR +. La fonctionx→x2est convexe et croissante sur IR+. Donc la compos´ee x?→max(x;0)2est convexe, et doncFaussi. CommeAest une application affine etFune application convexe, alors la compos´ee F◦Aest convexe : en effet, il suffit de remarquer que

AinsiG=F◦Aest convexe.

Enfin,Gest continue comme compos´ee d"applications continues (car on notera que x?→max(x;0) est continue). (b)L"applicationx?→max(x;0)2est d´erivable sur ]0,+∞[, de d´eriv´ee 2x, et sur

]-∞,0[, de d´eriv´ee nulle. Comme on a continuit´e de la d´eriv´ee en z´ero, on en d´eduit

quex?→(x,0) est d´erivable sur IR, de d´eriv´ee

2max(x;0).

Travaux dirig´es.7(On notera quex?→max(x;0) n"est pas d´erivable en z´ero, d"o`u l"int´erˆet de prendre

le carr´e!) On obtient alors ?F(x) =?2max(xi;0)? DoncGest diff´erentiable comme compos´ee d"applications diff´erentiables, et la for- mule de composition des diff´erentielles donne, pour touth?IRn,

DG(v)h=DF(A(v))DA(v)h

=??F(A(v)),Ch? =?C?2max(Cv-f;0),h?, et donc ?G(v) = 2C?max(Cv-f;0). (c)On a, pourε >0 etv?IRn, J

ε(v) =J(v) +12εG(v).

Existence du minimum : la fonctionJεest continue, carJetGle sont, et on a J ε≥J. CommeJest infinie `a l"infini,Jεaussi, doncJεadmet un minimum sur IRn (Th. 2.2.2). Unicit´e :Jest strictment convexe, comme somme d"une fonction strictement convexe (J) et d"une fonction convexe (12εG). Le minimum deJεsur IRnest donc unique (Th.quotesdbs_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