Soutenance mémoire
Méthodes de point fixe et éclatement d’opérateurs
Dans de nombreux domaines de l’analyse non linéaire, les méthodes de point fixe sont un moyen naturel de modéliser, d’analyser et de résoudre des problèmes complexes [7, 12, 29, 45]. Dans [14] il est montré que des méthodes classiques d’optimisation et de résolution d’inclusions monotones peuvent être modélisées et étudiées en tant que méthodes de point fixe. Ces dernières interviennent naturellement dans de nombreux champs des mathématiques appliquées : statistiques, apprentissage automatique, traitement du signal, équations aux dérivées partielles, problèmes inverses, transport optimal, optimisation [2, 4, 15, 19, 20, 23, 27, 28, 30, 34, 39, 42]. La notion d’opérateur moyenné, introduite dans [5], joue un rôle fondamental dans notre travail.
Définition 1.1 Soient H un espace de Hilbert réel, α ∈ ]0, 1] et T : H → H. Alors T est α-moyenné s’il existe une contraction R: H → H telle que T = (1 − α) Id +αR.
Un problème générique de point fixe est de trouver x ∈ H tel que x = T x, où T est une contraction. (1.1) Pour plus de flexibilité, il est préférable de considérer une formulation multicouche où l’on décompose l’opérateur T en opérateurs plus simples. En particulier, ceci permet de modéliser de manière plus souple les problèmes d’éclatement pour les inclusions monotones. Pour tout i ∈ {1, . . . , m}, soit Ti: H → H un opérateur moyenné. L’objectif est de trouver x ∈ H tel que x = (T1 ◦ · · · ◦ Tm)x. (1.2) Plus généralement, nous allons considérer une famille de problèmes de la forme (1.2) et obtenir la formulation suivante déjà proposée dans [14, 24].
Motivations et organisation de la thèse
De nombreuses stratégies sans liens apparents coexistent pour résoudre les problèmes d’inclusion monotone. Dans le but de simplifier et rationaliser l’état de l’art autour de principes élémentaires, nous proposons une théorie cohérente capable d’englober diverses techniques algorithmiques dans un cadre synthétique. Par exemple, les méthodes inertielles et celles des moyennes de Mann sont toujours étudiées de manière distincte. De même, les techniques d’itérations à métriques variables n’ont été étudiées que dans le cadre d’algorithmes spécifiques. Nous développons des outils pour analyser ces différentes constructions algorithmiques conjointement, clarifions et généralisons la théorie asymptotique de ces méthodes, et proposons de nouvelles méthodes itératives pour l’analyse non linéaire et l’optimisation. Notre méthodologie, ancrée sur un modèle de compositions de quasicontractions moyennées, nous permet de faire avancer simultanément sur plusieurs fronts la théorie des algorithmes de point fixe et de leurs applications aux inclusions monotones. Des exemples numériques sont proposés dans le cadre de la restauration d’image, où nous exposons un nouveau point de vue pour la formulation des problèmes variationnels. La thèse est organisée comme suit. Dans le Chapitre 2, nous nous intéressons aux algorithmes dont les règles de mise à jour utilisent l’ensemble des itérés déjà générés. Nous présentons un cadre général d’itération de point fixe dont le but est d’englober d’une part les méthodes de point fixe générales et, d’autre part, deux méthodes avec mémoire qui semblaient indépendantes, à savoir les moyennes de Mann et les techniques inertielles. Nous fournissons de nombreux exemples d’applications de notre théorème principal, et montrons qu’il couvre une large part des résultats connus dans ces divers domaines. Nous revisitons alors l’algorithme explicite-implicite, l’algorithme de Peaceman-Rachford, mais aussi par exemple l’algorithme du sous-gradient projeté de Polyak. L’objectif du Chapitre 3 est de compléter l’analyse du Chapitre 2 en étudiant plus en détail la notion de matrice concentrante. Nous en proposons une spécialisation, appelée superconcentrante, qui nous permet d’obtenir des résultats de sommabilité. Nous fournissons des exemples de telles matrices et nous proposons aussi de nouvelles matrices inertielles. Finalement, nous montrons l’intérêt d’obtenir la sommabilité en proposant des exemples d’algorithmes avec mémoire dont on ne sait pas prouver la convergence sans matrices superconcentrantes, comme l’algorithme de Krasnosel’skiˇı-Mann, ou en l’utilisant pour garantir la convergence forte d’une suite. Le Chapitre 4 présente une extension des méthodes de point fixe au cadre où la métrique sous-jacente change à chaque itération. De telles variantes ont notamment été étudiées dans le cas de l’algorithme explicite-implicite [22, 44]. Nous appliquons ces techniques pour proposer un algorithme multicouche sur-relaxé d’opérateurs moyennés avec métrique variable. Nous présentons plusieurs nouvelles méthodes et, en particulier, une application à l’algorithme explicite-implicite sur-relaxé à métrique variable, et à un algorithme explicite-implicite sur-relaxé dans l’espace primal-dual pour résoudre un problème composite. Enfin, le Chapitre 5 est une réflexion originale sur le choix des algorithmes dans les applications. Sur des exemples simples, nous avons constaté l’efficacité de l’algorithme de Douglas-Rachford (1.7) par rapport à l’algorithme explicite-implicite (1.8), pourtant habituellement privilégié sur ce type d’exemple. Ce constat nous conduit à remettre en cause la stratégie qui consiste à utiliser systématiquement des pas explicites sur les termes lisses dans les méthodes d’éclatement en optimisation convexe du premier ordre. Cette proposition peut surprendre car l’utilisation explicite d’opérateurs monotones se fait presque systématiquement en raison des propriétés supplémentaires (régularité, cocoercivité) dont ils jouissent. Nous fournissons un grand nombre de fonctions lisses utiles dans les applications dont on sait calculer l’opérateur proximal. Plusieurs simulations numériques en traitement de l’image viennent illustrer cette étude, montrant qu’il peut être avantageux d’utiliser des algorithmes entièrement proximaux, donc implicites, plutôt que des méthodes qui font intervenir des pas explicites.
Description et résultats principaux
Nous allons étudier l’inclusion monotone fondamentale qui suit.
Problème 4.1 Soit A un opérateur maximalement monotone, soit β ∈ ]0, +∞[ et soit B : H → H un opérateur β-cocoercif. De plus, on suppose que S = zer(A + B) 6= ∅. (4.1)
L’objectif est de trouver un point dans S. Nous utilisons le cadre général des opérateurs moyennés. On rappelle que l’on cherche à produire un algorithme pour lequel la métrique peut changer à chaque itération. Pour cela, nous allons avoir besoin de la définition suivante.
Définition 4.2 Soit µ ∈ ]0, +∞[, soit U ∈ Pµ(H), soit α ∈ ]0, 1] et soit T : H → H un opérateur. Alors T est α-moyenné sur (H, U) si (∀x ∈ H)(∀y ∈ H) kT x − T yk2U 6 kx − yk2U −1 − ααkT x − xk2U. (4.2)
Si α = 1, on dit que T est contractant sur (H, U).Nous allons résoudre le problème auxiliaire suivant.
Problème 4.3 Soit α ∈ ]0, +∞[, soit (ηn)n∈N ∈ ℓ1+(N) et soit (Un)n∈N une suite de Pα(H) telle que µ = sup n∈N kUnk < +∞ et (∀n ∈ N) (1 + ηn)Un+1 < Un. (4.3)
Soit m > 1 un entier. Pour tout n ∈ N et tout i ∈ {1, . . . , m}, soit αi,n ∈ ]0, 1] et soit Ti,n : H → H αi,n-moyenné sur (H, U −1n). L’objectif est de trouver x ∈ S =\n∈N Fix Tn 6= ∅, où (∀n ∈ N) Tn = T1,n · · · Tm,n. (4.4) On présente maintenant le résultat central de ce chapitre.
Théorème 4.4 On considère le cadre du Problème 4.3. Soit ε ∈ ]0, 1[ et pour tout n ∈ N, soit φn une constante de moyennage de Tn, soit λn ∈ ]0, φn] et soit ei,n ∈ H. On itère pour n = 0, 1, . . . $ yn = T1,n T2,n · · · Tm−1,n(Tm,nxn + em,n) + em−1,n · · · + e2,n + e1,n xn+1 = xn + λn(yn − xn).(4.5)
Supposons que (∀i ∈ {1, . . . , m})X n∈Nλnkei,nkU−1n < +∞, (4.6) et on définit (∀i ∈ {1, . . . , m})(∀n ∈ N) Ti+,n =(Ti+1,n · · · Tm,n, if i 6= m;Id , if i = m.(4.7)
Alors les propriétés suivantes sont satisfaites : (i) P n∈N λn(1/φn − λn)kT1,n · · · Tm,nxn − xnk2U−1n< +∞. (ii) Supposons que (∀n ∈ N) λn ∈ ]0, ε + (1 − ε)/φn]. Alors (∀x ∈ S) max16i6mX n∈N λn(1 − αi,n) αi,n k(Id −Ti,n)Ti+,nxn − (Id −Ti,n)Ti+,nxk2U−1n< +∞. (4.8)
(iii) (xn)n∈N converge faiblement vers un point de S si et seulement si tout point d’accumulation séquentiel faible de (xn)n∈N est dans S. Dans ce cas, la convergence est forte si int S 6= ∅. (iv) (xn)n∈N converge fortement vers un point de S si et seulement si lim dS(xn) = 0.
|
Table des matières
Résumé
Notations et glossaire
Chapitre 1 Introduction
1.1 Méthodes de point fixe et éclatement d’opérateurs
1.2 Motivations et organisation de la thèse
1.3 Contributions principales
1.4 Bibliographie
Chapitre 2 Itérations quasicontractantes : des moyennes de Mann aux méthodes inertielles
2.1 Description et résultats principaux
2.2 Article en anglais
2.2.1 Introduction
2.2.2 Preliminary results
2.2.3 Asymptotic behavior of Algorithm 2.8
2.2.4 Examples and Applications
2.3 Bibliographie
Chapitre 3 Matrices concentrantes, superconcentrantes, et méthodes inertielles
3.1 Introduction
3.2 Résultats préliminaires
3.3 Construction de matrices superconcentrantes
3.3.1 Matrices superconcentrantes positives
3.3.2 Matrices inertielles d’ordre 3
3.4 Applications
3.5 Bibliographie
Chapitre 4 Itérations moyennées à métrique variable
4.1 Description et résultats principaux
4.2 Article en anglais
4.2.1 Introduction
4.2.2 Notation and background
4.2.3 Main convergence result
4.2.4 Applications to the forward-backward algorithm
4.2.5 A composite monotone inclusion problem
4.3 Bibliographie
Chapitre 5 Activation proximale de fonctions lisses dans les méthodes d’éclatement
5.1 Description et résultats principaux
5.2 Article en anglais
5.2.1 Introduction
5.2.2 Proximity operators of smooth convex functions
5.2.3 Splitting algorithms
5.2.4 Application to inconsistent convex feasibility problems
5.2.5 Numerical illustrations
5.2.5.1 Forward-backward versus Douglas-Rachford splitting
5.2.5.2 Primal-dual splitting
5.3 Bibliographie
Chapitre 6 Conclusion et perspectives
6.1 Conclusion
6.2 Perspectives
6.3 Bibliographie
Télécharger le rapport complet
