[PDF] 1 Exercice sur la fonctionnelle ROF 2 Méthode de gradient avec PDF Exo_04_08

2 Méthode de gradient avec projection à pas variable pour une fonc- tion quadratique elliptique On considère la problème de minimisation suivant : trouver

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

[PDF] Corrige Examen 2016-17

Corrigé Les documents suivants sont autorisés : — Polycopiés distribués en Algorithme de gradient conjugué pour les moindres carrés : On suppose désormais que Dans la suite de l'exercice, f : Rn → R désigne une fonction deux fois

[PDF] Optimisation

ordre (gradient conjugué, B F G S ) sera nécessaire pour obtenir 5 décimales 3 5 Exercices corrigés Minimisation unidirectionnelle La plupart des méthodes

[PDF] 1 Exercice sur la fonctionnelle ROF 2 Méthode de gradient avec

2 Méthode de gradient avec projection à pas variable pour une fonc- tion quadratique elliptique On considère la problème de minimisation suivant : trouver

[PDF] Algorithme du gradient conjugué • La lettre n désigne un entier

Algorithme du gradient conjugué Proposition de corrigé 1) La fonctionnelle J a bien un minimum car la matrice A est symétrique définie positive

[PDF] feuilles de travaux dirigés - Ceremade - Université Paris Dauphine

l'algorithme du gradient conjugué? Calculer alors explicitement les deux premiers itérés et vérifier la finie convergence de l'algorithme Exercice 24 ( exercice

[PDF] Exercices - Feuille 5

o`u Mq est triangulaire inférieure inversible carrée d'ordre q

[PDF] Optimisation Sans Contraintes - Université de Souk Ahras

1 5 Suggestions et Corrigés 3 2 2 Méthode de gradient conjugué dans le cas quadratique 39 3 2 3 Méthode du Exercice 01 Montrer qu'une

[PDF] Optimisation

La méthode du gradient conjugué a été découverte en 1952 par Hestenes et Exercice 76 (Gradient conjugué pour une matrice non symétrique) Corrigé

[PDF] 98 CHAPITRE 2 PRÉLIMINAIRES

On retrouve la formule utilisée dans l'exemple du tableau 3 1 pour le calcul du pas θ˚ Exercice 3 6 4 [Application de l'algorithme du gradient conjugué] Appliquez l

ENS Cachan2008-2009

M2 parcours MVA

Calcul des variations, Optimisation et Applications en Traitement d'image Examen écrit, le 6 janvier 2009 à 13h30, durée 1h30 Rédiger Exercice 1 et Problème 2 sur des feuilles séparées

1 Exercice sur la fonctionnelle ROF

Soit½R2un ouvert convexe borné à bordC1.

Soitfun élément deL2(). On considère la fonctionnelleF:W1;2()!Rdénie par :

F(u) =Z

(f¡u)2dx+Z jruj2dx(1) 1. Montrez queFadmet un unique minimiseur~usurW1;2(). 2. Montrez que~uest solution d'une Equation aux Dérivées Partielles que vous calculerez.

Indications :

On rappelle queuest un élément deW1;2()ssiuest dansL2()et sa dérivée au sens des distributions

dansL2(£). On rappelle queW1;2()s'injecte de manière compacte dansL2().

La personne peu à l'aise avec les espaces de dimensions innies pourra commencer par considérer le

problème en dimension nie.

2 Méthode de gradient avec projection à pas variable pour une fonc-

tion quadratique elliptique On considère la problème de minimisation suivant : trouver^utel queF(^u) = minu2UF(u);(2)

F(u) =1

2 hBu;ui ¡ hc;ui; B2RN£

N; c2RN;

U=fu2RN:Au=vg; v2RM;rank(A) =M < N;(3)

oùBest symétrique et dénie positive(donc toutes ses valeurs propres sont strictement positives).

SoitPUl'opérateur de projection surU. On considère l'itération u k +1=Gk(uk); k= 0;1;2;:::;(4) G k(u) =PU¡u¡½k(Bu¡c)¢: 1.

Soit la fonctionf:R+!Rdénie par

f(½) = max©j1¡½¸minj;j1¡½¸maxjª;

où¸minet¸maxsont la plus petite et la plus grande des valeurs propres deBetR+def=fr2R:r¸0g.

(a)

Pour¸ >0xé, calculerargmin½

j1¡½¸j. Tracer la courbe de½!f(½). (b) SoitG=fr2R+:f(r) = 1g. Déterminer explicitementGet donner sa cardinalité. (c)

Calculer

^½def= argmin½f(½): (d)Déterminer un intervalle[a;b], avec0< a < btel que

½2[a;b])°def= maxff(a);f(b)g<1:(5)

Montrer que

kI¡½Bk2=f(½):

Rappel :

pour toute matrice réelle et carréeA, son rayon spectral estR(A) = maxfj¸ij:¸i=valeur propre deAg

et l'on akAk2=p

R(ATA)oùATest la matrice transposée deA.

3. En étudiantkGk(u)¡Gk(v)k2pouru2RN,v2RN, montrer que k2[a;b])Gkest une contraction: Conclure quant à la convergence de l'itération donnée dans (4).

Rappel :

tout opérateur de projectionPUsatisfait l'inégalitékPU(u)¡PU(v)k2· ku¡vk2,8u2RNet

8v2RN.

4. Si^urésoud le problème formulé dans (2), montrer que l'itération (4) satisfait k2[a;b]) kuk¡^uk2·°kku0¡^uk2;(6) où°est déni dans (5). 5.

Commenter le cas où½k= ^½;8k¸0.

Dans le cas d'une fonctionFconvexe, coercive etC2, générale, nous avions obtenu en cours que la méthode

de gradient avec projection à pas variable vérie k2[a0;b0];0<~a <~b <2¸min

2max) 9~° <1tel quekuk¡^uk2·~°kku0¡^uk2;

où^uest tel queF(^u) = minu2UF(u). (a) Le résultat donné ci-dessus peut-il être appliqué au problème (2)? (b) Comparer la valeur debobtenue à la question (1d) avec~bet commenter l'importance du résultat (1d). 7.

Soitw2RN. PourUdénie dans (3), calculer

^z= argminz2U½ 1 2 kz¡wk22¾ (a) Pour toutw2RN, déduirePU(w)pourUdéni dans (3). (b) Donner une condition assurant quePUde la question 7a est linéaire.

Corrigé

1 2 1. (a) (b)

G=½

0;2 max¾ et Card(G) = 2. (c)

8a;8btels que0< a < b <2

maxon a° <1. 2.

I¡½B= (I¡½B)Tdonc

kI¡½Bk2=R(I¡½B) = max©j1¡½¸minj;j1¡½¸maxjª=f(½): 3.

Soit½k2[a;b]alors° <1

· ku¡½kBu¡v+½kBvk2

=k(I¡½kB)(u¡v)k2

·°k(u¡v)k2

Quel que soit½k2[a;b],Gkest une contraction donclimk!1uk= ^uoùGk(^u) = ^u. 4. En utilisant le fait queGk(^u) = ^u,8½k2[a;b]on a : · kuk¡1¡½k¡1Buk¡1¡^u+½k¡1B^uk2 =k(I¡½k¡1B)(uk¡1¡^u)k2

·°kuk¡1¡^uk2

·°2kuk¡2¡^uk2· ¢¢¢

·°kku0¡^uk2

Si½k= ^½,8k¸0, l'itération (4) correspond à la méthode de gradient avec projection à pas optimal.

6. (a)

Oui (évident).

(b)

La borne supérieure

2¸min

2maxest en général bien plus petite que la nouvelle borne2

max. Grâce à la nouvelle borne, on peut prendre des pas½kplus grands.

7.Lagrangien :L(z;¸) =12kz¡wk22+¸T(Az¡v)où¸2RM. On doit résoudre le système d'équations :

0 =z¡w+AT¸

0 =Az¡v

Alors

0 =Az¡Aw+AAT¸=v¡Aw+AAT¸

CommeAATest inversible,

¸= (AAT)¡1(Aw¡v)

Alors ^z=w¡AT¸=w¡AT(AAT)¡1(Aw¡v) =¡I¡AT(AAT)¡1A¢w+AT(AAT)¡1v (a) P

U(w) =¡I¡AT(AAT)¡1A¢w+AT(AAT)¡1v.

(b) v= 0.

Master MVA

Durée de l"examen : 2 heures. Aucun document autorisé.

18 Décembre 2007

1 Problème :

Dans tout l'énoncé,k:kdésigne la norme euclidienne usuelle surRN, eth:;:ile produit scalaire associé.

On rappelle qu'un sous-ensembleUest convexe si pour tousu;vdansUetdans[0;1], on av+(1)u2U. On rappelle aussi qu'une application:U!Rest convexe si pour tousu;vdansUetdans[0;1], on a : (v+ (1)u)(v) + (1)(u) On rappelle enn la formule de Taylor à l'ordre 1 pour une fonctionFde classeC1deRNdansR:

F(v)F(u) =Z

1 0 hrF(tv+ (1t)u);vuidt(1) Dans tout le problème, on suppose qu'il existe >0tel queFvérie l'inégalité suivante : hF(u)F(v);uvi kuvk2(2) On suppose aussi qu'il existeM >0tel queFvérie l'inégalité : krF(u) rF(v)k Mkvuk(3)

1. Dans cette question (et uniquement dans cette question), on suppose queFs'écrit sous la forme :

F(v) =12

hAv;vi hb;vi(4) avecAmatrice réelle etbvecteur deRN. CalculerrF(v)(on pourra commencer en supposantAsymmétrique). Donner une condition nécessaire et susante surApour queFdonnée par (4) vérie (2) et (3).

2. On revient au cas général pourF. Etant donnésuetvdansRN, on pose pourdans[0;1]:

() =F(v+ (1)u) +(1)2 kvuk2F(v)(1)F(u) Montrer queest croissante sur[0;1](on pourra utiliser (1)) . En déduire que pour tousuetvdansRN, etdans[0;1], on a :

F(v+ (1)u) +(1)2

kvuk2F(v) + (1)F(u)(5)

3. Montrer en utilisant (1) et (2) que :

F(v)F(u) +hrF(u);vui+2

kvuk2(6)

4. On se donne un sous-ensembleUconvexe fermé non vide deRN. On étudie le problème de minimisation :

Trouveru2Utel queF(u) = infv2UF(v)(7)

Montrer que (7) admet exactement une solution.

5. Montrer que siU=RN, alors la solution de (7) est caractérisée par :

rF(u) = 0(8)

6. Monter qu'en général, la solution de (7) est caractérisée par :

hrF(u);vui 0(9) pour toutv2U.

7. Dans cette question et jusqu'à la n du problème, on revient au casU=RN.

On part d'un élémentv0arbitraire dansRN. Supposantvkconnu, on considère le problème : Trouverk2Rtel queF(vkkrF(vk)) = inf2RF(vkrF(vk))(10) Montrer que sivkn'est pas solution de (7), alors(10)admet exactement une solution.

8. Sivkest pas solution de (7), on posevk+1=vk. Sinon on posevk+1=vkkrF(vk).

Montrer que

hrF(vk+1);rF(vk)i= 0

9. En déduire que :

F(vk)F(vk+1)2

kvkvk+1k2

10. Montrer que la suitevkainsi construite converge vers la solution de (7).

Comment s'appelle cet algorithme?

2 Exercice :

SoitJ:RN!Rconvexe, à valeurs finies. (Rappelons qu'alorsJest Lipschitzienne.)

1. Donner la dénition de la dérivée directionnelleJ(u)(v)deJenu2RNdans la direction dev2RN.

Montrer que l'applicationv!J(u)(v)est convexe, positivement homogène et lipschitzienne.

Peut-elle être linéaire et dans quel cas?

2. Rappeler les deux dénitions de@J(u) la sous-diérentielle deJenu2RNet expliquer leur équivalence.

(On peut utiliser les propriétés de la fonction-penteq(t) =J(u+tv)J(u)t pourt >0.)

3. SoitJ:R2!Rdénie parJ(u1;u2) =ju1j+ju2jpour >0un paramètre xe. Calculer la sous-

diérentielle deJau point(u1;u2) = (1;0). Déterminer les directions de déscente deJà partir de ce pointu. 2

ENS Cachan2006-2007

M2 parcours MVA

Optimisation pour la restauration d"images

Examen ´ecrit, dur´ee 1h30

Sujet : Minimisation par r´egularisation semi-quadratique L"usage de notes et d"autres documents est autoris´e. Pourvfix´e, on consid`ere la minimisation de la fonctionF: IRn→IR :

F(u) =?Au-v?2+βr?

i=1?(?Giu?), β >0,(1) o`u pour touti,Gi: IRn→IRs,s? {1,2}(chaqueGiest une matrice de tailles×n),A: IRn→IRnest inversible et

?: IR+→IR est convexe ;

t→t2/2-?(t) est convexe ;

?estC2avec??(0) = 0 et???(0)>0 ;

lim|t|→∞?(t)/t2<1/2.

Exemple de fonction :?(t) =⎷

1 +t2.

1. Pour toutw?IRsavecs= 1 ous= 2 on d´efinit

ψ(w) = sup

z?IRs? -1

2?z-w?2+?(?z?)?

(2)

V´erifier s"il s"agit d"un maximum.

2. Montrer que pour toutz?IRs

?(z) = infw?IRs? 1

2?z-w?2+ψ(?w?)?

(3)

On utilisera le fait que si une fonctionf: IRs→IR est continue, finie, convexe, alorsf= (f?)?o`u la

convexe conjugu´eef?defest d´efinie parf?(w) = supz?IRs{?z,w? -f(z)}.

3. D´eterminer la fonctionσ: IRs→IRstelle que pour toutz?IRs, siw=σ(z) alors?(z) =1

2?z-w?2+

ψ(?w?).

On peut utiliser le fait que pour le mˆeme couple (z,σ(z)) on trouve le sup dans (2). Dans la suites= 1.Notons que dans ce cas chaqueGiest un vecteur-ligne. Pour commodit´e, introduisons la matriceGde tailler×ndont la ligneiestGi. On consid`ere le crit`ere augment´eF: IRn×IRr

F(u,b) =?Au-v?2+βr?

i=1? 1

2(Giu-bi)2+ψ(bi)?

=?Au-v?2+β

2?Gu-b?2+βr?

i=1ψ(bi)

o`ubid´esigne lai`eme composante du vecteurb?IRr, et sa minimisation altern´ee o`u `a l"it´erationkon

effectue les minimisations suivantes b ktel queF(uk-1,bk) = infb?IRrF(uk-1,b) (4) u ktel queF(uk,bk) = infu?IRnF(u,bk) (5)

4. Montrer que la suiteF(uk) est d´ecroissante et qu"il existe un compactKtel queuk?Kpour toutk.

5. Calculer explicitementbketukd´efinis par (4) et (5).

6. En ins´erant l"expression obtenue pourbkdans (5), exhiber la fonctionJ: IRn→IRntelle que l"it´eration

(4)-(5) est ´equivalente `a u k=J(uk-1).

7. MettreJsous la formeJ(u) =u-(H(u))-1?F(u) et commenter cette expression.

8. Calculer la diff´erentielleDJdeJ.

9. V´erifier si pour toutu?Kle rayon spectral deDJ(u) est strictement plus petit que 1.

10. En d´eduire quant `a la convergence de la m´ethode it´erative d´efinie dans (4)-(5).

ENS Cachan2005-2006

M2 parcours MVA

Optimisation pour la restauration d'images

Examen Ecrit

partie II. trouver ^utel queF(^u) = infu2UF(u) (1)

U=fu2IRn:h(u)·0g

h(u) =Au¡b2IRm; m < n; A2IRm£n oµuFest une fonctionnelle convexe elliptique de constante¹ >0. (Rappel :FestC1ethrF(u)¡ rF(v); u¡vi ¸¹ku¡vk2;8(u;v)2IRn£IRn.) 1.

L(u;¸) =F(u) +h¸;h(u)i:(2)

2. u

¸tel queL(u¸;¸) = infu2IRnL(u;¸):(3)

(a) (b) (c) 3. utel queL(u;¸u) = sup

¸2IRm+L(u;¸):(4)

(a)

Argumenter l'existence d'une solution¸u.

(b) (Ne pas omettre que¸u¸0.) 4. 5. (Rappelons que sup

¸2IRm+infu2IRnL(^u;^¸) = infu2IRnsup

¸2IRm+L(^u;^¸).)

6. Montrer que pour tout½ >0,^¸est la projection du point^¸+½h(^u) sur l'ensemble IRm+.

Donner l'expression de ¦

Partant de¸02IRm+arbitraire, pour tout entierk¸0 on calcule u ktel queL(uk;¸k) = infu2IRnL(u;¸k) (5) k+1= ¦m+(¸k+½h(uk)) (6) oµu 0< ½ < K(7) 1. 2. Montrer quek¸k+1¡^¸k · k¸k¡^¸+½A(uk¡^u)k. (On peut utiliser le fait que ¦ 3. k¸k+1¡^¸k2· k¸k¡^¸k2¡´kuk¡^uk2 ( On peut commencer par calculerrF(uk)¡ rF(^u).) 4. 5. Etudier la convergence dek¸k¡^¸k2lorsquek! 1. 6. Conclure quant µa la convergence de la suiteuk. 7. 8. 9. Montrer qu'il existe une sous-suite (¸kj)j¸0qui est convergente. 10. Si rangA=m, montrer queLa un unique point-selle (^u;^¸).quotesdbs_dbs18.pdfusesText_24

[PDF] [PDF] 1 Exercice sur la fonctionnelle ROF 2 Méthode de gradient avec

ENS Cachan2008-2009

M2 parcours MVA

1 Exercice sur la fonctionnelle ROF

Soit½R2un ouvert convexe borné à bordC1.

F(u) =Z

Indications :

2 Méthode de gradient avec projection à pas variable pour une fonc-

F(u) =1

N; c2RN;

U=fu2RN:Au=vg; v2RM;rank(A) =M < N;(3)

Soit la fonctionf:R+!Rdénie par

Pour¸ >0xé, calculerargmin½

Calculer

½2[a;b])°def= maxff(a);f(b)g<1:(5)

Montrer que

Rappel :

R(ATA)oùATest la matrice transposée deA.

Rappel :

8v2RN.

Commenter le cas où½k= ^½;8k¸0.

2max) 9~° <1tel quekuk¡^uk2·~°kku0¡^uk2;

Soitw2RN. PourUdénie dans (3), calculer

Corrigé

G=½

8a;8btels que0< a < b <2

I¡½B= (I¡½B)Tdonc

Soit½k2[a;b]alors° <1

· ku¡½kBu¡v+½kBvk2

·°k(u¡v)k2

·°kuk¡1¡^uk2

·°2kuk¡2¡^uk2· ¢¢¢

·°kku0¡^uk2

Oui (évident).

La borne supérieure

2¸min

2maxest en général bien plus petite que la nouvelle borne2

7.Lagrangien :L(z;¸) =12kz¡wk22+¸T(Az¡v)où¸2RM. On doit résoudre le système d'équations :

0 =z¡w+AT¸

0 =Az¡v

0 =Az¡Aw+AAT¸=v¡Aw+AAT¸

CommeAATest inversible,

¸= (AAT)¡1(Aw¡v)

U(w) =¡I¡AT(AAT)¡1A¢w+AT(AAT)¡1v.

Master MVA

18 Décembre 2007

1 Problème :

F(v)F(u) =Z

1. Dans cette question (et uniquement dans cette question), on suppose queFs'écrit sous la forme :

F(v) =12

2. On revient au cas général pourF. Etant donnésuetvdansRN, on pose pourdans[0;1]:

F(v+ (1)u) +(1)2

3. Montrer en utilisant (1) et (2) que :

F(v)F(u) +hrF(u);vui+2

4. On se donne un sous-ensembleUconvexe fermé non vide deRN. On étudie le problème de minimisation :

Trouveru2Utel queF(u) = infv2UF(v)(7)

Montrer que (7) admet exactement une solution.

5. Montrer que siU=RN, alors la solution de (7) est caractérisée par :

6. Monter qu'en général, la solution de (7) est caractérisée par :

7. Dans cette question et jusqu'à la n du problème, on revient au casU=RN.

8. Sivkest pas solution de (7), on posevk+1=vk. Sinon on posevk+1=vkkrF(vk).

Montrer que

9. En déduire que :

F(vk)F(vk+1)2

10. Montrer que la suitevkainsi construite converge vers la solution de (7).

Comment s'appelle cet algorithme?

2 Exercice :

1. Donner la dénition de la dérivée directionnelleJ(u)(v)deJenu2RNdans la direction dev2RN.

Peut-elle être linéaire et dans quel cas?

2. Rappeler les deux dénitions de@J(u) la sous-diérentielle deJenu2RNet expliquer leur équivalence.

3. SoitJ:R2!Rdénie parJ(u1;u2) =ju1j+ju2jpour >0un paramètre xe. Calculer la sous-

ENS Cachan2006-2007

M2 parcours MVA

Optimisation pour la restauration d"images

Examen ´ecrit, dur´ee 1h30

F(u) =?Au-v?2+βr?

?: IR+→IR est convexe ;

t→t2/2-?(t) est convexe ;

?estC2avec??(0) = 0 et???(0)>0 ;

lim|t|→∞?(t)/t2<1/2.

?: IR+→IR est convexe ;

t→t2/2-?(t) est convexe ;

?estC2avec??(0) = 0 et???(0)>0 ;

lim|t|→∞?(t)/t2<1/2.