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

Exercice 1 Méthode du gradient conjugué

Appliquer la méthode du gradient conjugué à partir de x(0). Exercice 2 Méthode de Cauchy (ou de plus forte pente). Soit la fonction ƒ suivante : On pose x(0).

Algorithme du gradient conjugué. • La lettre n désigne un entier

Proposition de corrigé. 1). La fonctionnelle J a bien un minimum car la On touche l`a au génie de Hestenes et Stiefel qui ont inventé la méthode du gradient ...

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

préfère des méthodes plus sophistiquées telles sue la méthode "BICGSTAB" ou "GMRES". Corrigé de l'exercice 125 page 237 (Gradient conjugué préconditionné par

Analyse numérique avancée Corrigé du TD 1

18 févr. 2021 Exercice 1 : Convergence du gradient conjugué. 1. La majoration du ... méthode du gradient conjugué comme une méthode itérative et donc d ...

Méthodes Numériques : Optimisation

Nous abordons les algorithmes de type descente de gradient la méthode du gradient conjugué

Corrige Examen 2016-17

Algorithme 1 : Algorithme du gradient conjugué. Données : Un point initial x Etude de la convergence de l'Algorithme 2 avec la méthode exacte Le but de la fin ...

Analyse Numérique

2.2.4 Méthode du gradient à pas optimal. . . . . . . . . . . . . 14. 2.2.5 Méthode du gradient conjugué. . . . . . . . . . . . . . . . 15. 2.3 Exercices.

Optimisation

12 mars 2020 3.4 La méthode du gradient conjugué . ... Dans cet exercice on étudie une méthode de minimisation sans contraintes d'une fonction quadratique de ...

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

On utilisera le fait que si une fonction f : IRs → IR est continue finie

Untitled

Cours et exercices corrigés. Dr.BOUDIAF NAIMA1. 2017. 1n.boudiaf@univ&batna2.dz. Page 3 La méthode du gradient conjugué est une méthode de descente à pas ...

Exercice 1 Méthode du gradient conjugué

Appliquer la méthode du gradient conjugué à partir de x(0). Exercice 2 Méthode de Cauchy (ou de plus forte pente). —. Soit la fonction f suivante

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

Semaine 2 : 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) :.

Cours danalyse numérique 2004-2005

12 sept. 2006 L. Sainsaulieu Calcul scientifique cours et exercices corrigés ... Remarque 1.16 (Sur la méthode du gradient conjugué) Il existe une mé-.

Corrige Examen 2016-17

Algorithme de gradient conjugué pour les moindres carrés : On suppose désormais que Le but de l'exercice est d'étudier la convergence d'un algorithme de ...

RO04/TI07 - Optimisation non-linéaire

Exercices du chapitre I . . Interprétation de la méthode du gradient conjugué . ... Exercice I.2 Calcul du gradient d'une fonction quadratique.

#7<9: 1>Optimisation Sans Contraintes

Chapitre3 : Algorithmes. 3.1 Méthode du gradient. 3.2 Méthode du gradient conjugué. 3.3 Méthode de Newton. 3.4 Méthode de relaxation. 3.5 Travaux pratiques.

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.

Algorithme du gradient conjugué. • La lettre n désigne un entier

Description de l'algorithme du gradient conjugué. L'état xk au pas suivant de l'algorithme est issu de xk?1 via un ... Proposition de corrigé.

Analyse numérique avancée Corrigé du TD 1

18 févr. 2021 Corrigé du TD 1 ... Exercice 1 : Convergence du gradient conjugué ... Ici nous utilisons le gradient conjugué comme une méthode directe

Université Aix Marseille 1 Licence de mathématiques Cours d

2 févr. 2017 L. Sainsaulieu Calcul scientifique cours et exercices corrigés pour ... du gradient conjugué est en fait une méthode d'optimisation pour la ...

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] 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.