▼ 

L'algorithme de Levenberg-Marquardt (LM) est parmi les algorithmes les plus populaires pour la résolution des problèmes des moindres carrés non linéaire. Motivés par la structure des problèmes de l'assimilation de données, nous considérons dans cette thèse l'extension de l'algorithme LM aux situations dans lesquelles le sous problème linéarisé, qui a la forme min||Ax - b ||², est résolu de façon approximative, et/ou les données sont bruitées et ne sont précises qu'avec une certaine probabilité. Sous des hypothèses appropriées, on montre que le nouvel algorithme converge presque sûrement vers un point stationnaire du premier ordre. Notre approche est appliquée à une instance dans l'assimilation de données variationnelles où les modèles stochastiques du gradient sont calculés par le lisseur de Kalman d'ensemble (EnKS). On montre la convergence dans L^p de l'EnKS vers le lisseur de Kalman, quand la taille de l'ensemble tend vers l'infini. On montre aussi la convergence de l'approche LM-EnKS, qui est une variante de l'algorithme de LM avec l'EnKS utilisé comme solveur linéaire, vers l'algorithme classique de LM ou le sous problème est résolu de façon exacte. La sensibilité de la méthode de décomposition en valeurs singulières tronquée est étudiée. Nous formulons une expression explicite pour le conditionnement de la solution des moindres carrés tronqués. Cette expression est donnée en termes de valeurs singulières de A et les coefficients de Fourier de b.

The Levenberg-Marquardt algorithm (LM) is one of the most popular algorithms for the solution of nonlinear least squares problems. Motivated by the problem structure in data assimilation, we consider in this thesis the extension of the LM algorithm to the scenarios where the linearized least squares subproblems, of the form min||Ax - b ||², are solved inexactly and/or the gradient model is noisy and accurate only within a certain probability. Under appropriate assumptions, we show that the modified algorithm converges globally and almost surely to a first order stationary point. Our approach is applied to an instance in variational data assimilation where stochastic models of the gradient are computed by the so-called ensemble Kalman smoother (EnKS). A convergence proof in L^p of EnKS in the limit for large ensembles to the Kalman smoother is given. We also show the convergence of LM-EnKS approach, which is a variant of the LM algorithm with EnKS as a linear solver, to the classical LM algorithm where the linearized subproblem is solved exactly. The sensitivity of the trucated sigular value decomposition method to solve the linearized subprobems is studied. We formulate an explicit expression for the condition number of the truncated least squares solution. This expression is given in terms of the singular values of A and the Fourier coefficients of b.

Advisors/Committee Members: Gratton, Serge (thesis director).

▼ 

Le sujet de cette thèse est le développement de méthodes itératives permettant la résolution degrands systèmes linéaires creux d'équations présentant plusieurs seconds membres simultanément. Ces méthodes seront en particulier utilisées dans le cadre d'une application géophysique : la migration sismique visant à simuler la propagation d'ondes sous la surface de la terre. Le problème prend la forme d'une équation d'Helmholtz dans le domaine fréquentiel en trois dimensions, discrétisée par des différences finies et donnant lieu à un système linéaire creux, complexe, non-symétrique, non-hermitien. De plus, lorsque de grands nombres d'onde sont considérés, cette matrice possède une taille élevée et est indéfinie. Du fait de ces propriétés, nous nous proposons d'étudier des méthodes de Krylov préconditionnées par des techniques hiérarchiques deux niveaux. Un tel pre-conditionnement s'est montré particulièrement efficace en deux dimensions et le but de cette thèse est de relever le défi de l'adapter au cas tridimensionel. Pour ce faire, des méthodes de Krylov sont utilisées à la fois comme lisseur et comme méthode de résolution du problème grossier. Ces derniers choix induisent l'emploi de méthodes de Krylov dites flexibles.

The topic of this PhD thesis is the development of iterative methods for the solution of large sparse linear systems of equations with possibly multiple right-hand sides given at once. These methods will be used for a specific application in geophysics - seismic migration - related to the simulation of wave propagation in the subsurface of the Earth. Here the three-dimensional Helmholtz equation written in the frequency domain is considered. The finite difference discretization of the Helmholtz equation with the Perfect Matched Layer formulation produces, when high frequencies are considered, a complex linear system which is large, non-symmetric, non-Hermitian, indefinite and sparse. Thus we propose to study preconditioned flexible Krylov subspace methods, especially minimum residual norm methods, to solve this class of problems. As a preconditioner we consider multi-level techniques and especially focus on a two-level method. This twolevel preconditioner has shown efficient for two-dimensional applications and the purpose of this thesis is to extend this to the challenging three-dimensional case. This leads us to propose and analyze a perturbed two-level preconditioner for a flexible Krylov subspace method, where Krylov methods are used both as smoother and as approximate coarse grid solver.

Advisors/Committee Members: Gratton, Serge (thesis director).

▼ L’évaluation des formations géologiques consiste en l’analyse et la synthèse de données de différentes sources, de différentes échelles (microscopique à kilométrique) et acquises à des dates très variables. Le processus conventionnel de caractérisation des formations relève alors de l’interprétation physique spécialisée de chacune de ces sources de données et leur mise en cohérence par des processus de synthèse essentiellement d’ordre statistique (corrélation, apprentissage, up-scaling…). Il s’avère cependant qu’une source de données présente un caractère central : les diagraphies. Ces mesures physiques de différentes natures (nucléaires, acoustiques, électromagnétiques…) sont réalisées le long de la paroi d’un puits à l’aide de différentes sondes. Elles sont sensibles aux propriétés in situ des roches, et ce, sur une gamme d’échelle centimétrique à métrique intermédiaire aux carottes et données de test de production. De par leur profondeur d’investigation, les données diagraphiques sont particulièrement sensibles au phénomène d’invasion de boue se produisant lors du forage dans l’abord puits. Traditionnellement, l’invasion est modélisée de façon frustre au moment de l’interprétation diagraphiques par un simple effet piston. Ce modèle simple permet d’honorer le bilan de volume mais ne prend aucunement en compte la physique réelle d’invasion et prive, de fait, les diagraphies de toute portée dynamique. Des essais de modélisation de l’historique d’invasion couplés aux données diagraphiques ont déjà été élaborés par différents laboratoires et une abondante littérature sur le sujet est disponible. Les limitations majeures de ces approches résident dans le caractère sous déterminé des problèmes inverses issus de ces modèles physiques et dans le fait que la donnée diagraphique est réalisée en général sur un intervalle de temps inadaptée au regard du développement de l’invasion. Nous proposons une approche différente qui s’attèle non pas à décrire la physique de l’écoulement mais celle de l’équilibre radial des fluides dans le domaine envahi lorsque les diagraphies sont acquises. Nous montrons qu’en introduisant quelques contraintes pétrophysiques supplémentaires, il est possible d’inverser efficacement la distribution des propriétés dynamiques pour chaque faciès géologique. L’inversion prend en compte le phénomène d’invasion radial dans la zone à eau ainsi que l’équilibre capillaire vertical caractérisant le profil de saturation dans le réservoir pour chaque facies. A chaque profondeur du puits, sont ainsi obtenues perméabilités, pressions capillaires et facteurs de cimentation avec leurs incertitudes ainsi que les lois pétrophysiques propres à chaque faciès. Cette méthode a été appliquée à deux puits réels. En guise de validation, les résultats d’inversion ont été comparés aux mesures laboratoire faites sur carotte. De plus, les perméabilités inversées ont été comparées aux transitoires de pression de mini-tests. La cohérence des résultats montre que, d’une part, les hypothèses de base du modèle sont validées et que,… Advisors/Committee Members: Gratton, Serge (thesis director).

▼ Cette thèse étudie la méthode du gradient conjugué et la méthode de Lanczos pour la résolution de problèmes aux moindres carrés non-linéaires sous déterminés et régularisés par un terme de pénalisation quadratique. Ces problèmes résultent souvent d'une approche du maximum de vraisemblance, et impliquent un ensemble de m observations physiques et n inconnues estimées par régression non linéaire. Nous supposons ici que n est grand par rapport à m. Un tel cas se présente lorsque des champs tridimensionnels sont estimés à partir d'observations physiques, par exemple dans l'assimilation de données appliquée aux modèles du système terrestre. Un algorithme largement utilisé dans ce contexte est la méthode de Gauss- Newton (GN), connue dans la communauté d'assimilation de données sous le nom d'assimilation variationnelle des données quadridimensionnelles. Le procédé GN repose sur la résolution approchée d'une séquence de moindres carrés linéaires optimale dans laquelle la fonction coût non-linéaire des moindres carrés est approximée par une fonction quadratique dans le voisinage de l'itération non linéaire en cours. Cependant, il est bien connu que cette simple variante de l'algorithme de Gauss-Newton ne garantit pas une diminution monotone de la fonction coût et sa convergence n'est donc pas garantie. Cette difficulté est généralement surmontée en utilisant une recherche linéaire (Dennis and Schnabel, 1983) ou une méthode de région de confiance (Conn, Gould and Toint, 2000), qui assure la convergence globale des points critiques du premier ordre sous des hypothèses faibles. Nous considérons la seconde de ces approches dans cette thèse. En outre, compte tenu de la grande échelle de ce problème, nous proposons ici d'utiliser un algorithme de région de confiance particulier s'appuyant sur la méthode du gradient conjugué tronqué de Steihaug-Toint pour la résolution approchée du sous-problème (Conn, Gould and Toint, 2000, p. 133-139) La résolution de ce sous-problème dans un espace à n dimensions (par CG ou Lanczos) est considérée comme l'approche primale. Comme alternative, une réduction significative du coût de calcul est possible en réécrivant l'approximation quadratique dans l'espace à m dimensions associé aux observations. Ceci est important pour les applications à grande échelle telles que celles quotidiennement traitées dans les systèmes de prévisions météorologiques. Cette approche, qui effectue la minimisation de l'espace à m dimensions à l'aide CG ou de ces variantes, est considérée comme l'approche duale. La première approche proposée (Da Silva et al., 1995; Cohn et al., 1998; Courtier, 1997), connue sous le nom de Système d'analyse Statistique de l'espace Physique (PSAS) dans la communauté d'assimilation de données, commence par la minimisation de la fonction de coût duale dans l'espace de dimension m par un CG préconditionné (PCG), puis revient l'espace à n dimensions. Techniquement, l'algorithme se compose de formules de récurrence impliquant des vecteurs de taille m au lieu de vecteurs de taille n. Cependant,… Advisors/Committee Members: Gratton, Serge (thesis director), Toint, Philippe (thesis director).

▼ 

Les travaux de ce doctorat concernent le développement de méthodes itératives pour la résolution de systèmes linéaires creux de grande taille comportant de nombreux seconds membres. L’application visée est la résolution d’un problème inverse en géophysique visant à reconstruire la vitesse de propagation des ondes dans le sous-sol terrestre. Lorsque de nombreuses sources émettrices sont utilisées, ce problème inverse nécessite la résolution de systèmes linéaires complexes non symétriques non hermitiens comportant des milliers de seconds membres. Dans le cas tridimensionnel ces systèmes linéaires sont reconnus comme difficiles à résoudre plus particulièrement lorsque des fréquences élevées sont considérées. Le principal objectif de cette thèse est donc d’étendre les développements existants concernant les méthodes de Krylov par bloc. Nous étudions plus particulièrement les techniques de déflation dans le cas multiples seconds membres et recyclage de sous-espace dans le cas simple second membre. Des gains substantiels sont obtenus en terme de temps de calcul par rapport aux méthodes existantes sur des applications réalistes dans un environnement parallèle distribué.

This PhD thesis concerns the development of flexible Krylov subspace iterative solvers for the solution of large sparse linear systems of equations with multiple right-hand sides. Our target application is the solution of the acoustic full waveform inversion problem in geophysics associated with the phenomena of wave propagation through an heterogeneous model simulating the subsurface of Earth. When multiple wave sources are being used, this problem gives raise to large sparse complex non-Hermitian and nonsymmetric linear systems with thousands of right-hand sides. Specially in the three-dimensional case and at high frequencies, this problem is known to be difficult. The purpose of this thesis is to develop a flexible block Krylov iterative method which extends and improves techniques already available in the current literature to the multiple right-hand sides scenario. We exploit the relations between each right-hand side to accelerate the convergence of the overall iterative method. We study both block deflation and single right-hand side subspace recycling techniques obtaining substantial gains in terms of computational time when compared to other strategies published in the literature, on realistic applications performed in a parallel environment.

Advisors/Committee Members: Gratton, Serge (thesis director), Vasseur, Xavier (thesis director).

▼ 

Au cours des dernières années, s’est développé un intérêt tout particulier pour l’optimisation sans dérivée. Ce domaine de recherche se divise en deux catégories: une déterministe et l’autre stochastique. Bien qu’il s’agisse du même domaine, peu de liens ont déjà été établis entre ces deux branches. Cette thèse a pour objectif de combler cette lacune, en montrant comment les techniques issues de l’optimisation déterministe peuvent améliorer la performance des stratégies évolutionnaires, qui font partie des meilleures méthodes en optimisation stochastique. Sous certaines hypothèses, les modifications réalisées assurent une forme de convergence globale, c’est-à-dire une convergence vers un point stationnaire de premier ordre indépendamment du point de départ choisi. On propose ensuite d’adapter notre algorithme afin qu’il puisse traiter des problèmes avec des contraintes générales. On montrera également comment améliorer les performances numériques des stratégies évolutionnaires en incorporant un pas de recherche au début de chaque itération, dans laquelle on construira alors un modèle quadratique utilisant les points où la fonction coût a déjà été évaluée. Grâce aux récents progrès techniques dans le domaine du calcul parallèle, et à la nature parallélisable des stratégies évolutionnaires, on propose d’appliquer notre algorithme pour résoudre un problème inverse d’imagerie sismique. Les résultats obtenus ont permis d’améliorer la résolution de ce problème.

In recent years, there has been significant and growing interest in Derivative-Free Optimization (DFO). This field can be divided into two categories: deterministic and stochastic. Despite addressing the same problem domain, only few interactions between the two DFO categories were established in the existing literature. In this thesis, we attempt to bridge this gap by showing how ideas from deterministic DFO can improve the efficiency and the rigorousness of one of the most successful class of stochastic algorithms, known as Evolution Strategies (ES’s). We propose to equip a class of ES’s with known techniques from deterministic DFO. The modified ES’s achieve rigorously a form of global convergence under reasonable assumptions. By global convergence, we mean convergence to first-order stationary points independently of the starting point. The modified ES’s are extended to handle general constrained optimization problems. Furthermore, we show how to significantly improve the numerical performance of ES’s by incorporating a search step at the beginning of each iteration. In this step, we build a quadratic model using the points where the objective function has been previously evaluated. Motivated by the recent growth of high performance computing resources and the parallel nature of ES’s, an application of our modified ES’s to Earth imaging Geophysics problem is proposed. The obtained results provide a great improvement for the problem resolution.

Advisors/Committee Members: Gratton, Serge (thesis director), Vicente, Luis Nunes (thesis director).

▼ 

Cette thèse se concentre sur l'étude d'un algorithme multi niveaux de régions de confiance en norme infinie, conçu pour la résolution de problèmes d'optimisation non linéaires de grande taille pouvant être soumis a des contraintes de bornes. L'étude est réalisée tant sur le plan théorique que numérique. L'algorithme RMTR8 que nous étudions ici a été élaboré a partir de l'algorithme présente par Gratton, Sartenaer et Toint (2008b), et modifie d'abord en remplaçant l'usage de la norme Euclidienne par une norme infinie, et ensuite en l'adaptant a la résolution de problèmes de minimisation soumis a des contraintes de bornes. Dans un premier temps, les spécificités du nouvel algorithme sont exposées et discutées. De plus, l'algorithme est démontré globalement convergent au sens de Conn, Gould et Toint (2000), c'est-a-dire convergent vers un minimum local au départ de tout point admissible. D'autre part, il est démontre que la propriété d'identification des contraintes actives des méthodes de régions de confiance basées sur l'utilisation d'un point de Cauchy peut être étendue a tout solveur interne respectant une décroissance suffisante. En conséquence, cette propriété d'identification est aussi respectée par une variante particulière du nouvel algorithme. Par la suite, nous étudions différents critères d'arrêt pour les algorithmes d'optimisation avec contraintes de bornes afin de déterminer le sens et les avantages de chacun, et ce pour pouvoir choisir aisément celui qui convient le mieux a certaines situations. En particulier, les critères d'arrêts sont analyses en termes d'erreur inverse (backward erreur), tant au sens classique du terme (avec l'usage d'une norme produit) que du point de vue de l'optimisation multicritères. Enfin, un algorithme pratique est mis en place, utilisant en particulier une technique similaire au lissage de Gauss-Seidel comme solveur interne. Des expérimentations numériques sont réalisées sur une version FORTRAN 95 de l'algorithme. Elles permettent d'une part de définir un panel de paramètres efficaces par défaut et, d'autre part, de comparer le nouvel algorithme a d'autres algorithmes classiques d'optimisation, comme la technique de raffinement de maillage ou la méthode du gradient conjugue, sur des problèmes avec et sans contraintes de bornes. Ces comparaisons numériques semblent donner l'avantage à l'algorithme multi niveaux, en particulier sur les cas peu non-linéaires, comportement attendu de la part d'un algorithme inspire des techniques multi grilles. En conclusion, l'algorithme de région de confiance multi niveaux présente dans cette thèse est une amélioration du précédent algorithme de cette classe d'une part par l'usage de la norme infinie et d'autre part grâce a son traitement de possibles contraintes de bornes. Il est analyse tant sur le plan de la convergence que de son comportement vis-à-vis des bornes, ou encore de la définition de son critère d'arrêt. Il montre en outre un comportement numérique prometteur.

This thesis concerns the study of a multilevel trust-region algorithm…

Advisors/Committee Members: Gratton, Serge (thesis director), Toint, Philippe (thesis director).

▼ 

L’optimisation sans dérivées (OSD) a connu un regain d’intérêt ces dernières années, principalement motivée par le besoin croissant de résoudre les problèmes d’optimisation définis par des fonctions dont les valeurs sont calculées par simulation (par exemple, la conception technique, la restauration d’images médicales ou de nappes phréatiques).Ces dernières années, un certain nombre de méthodes d’optimisation sans dérivée ont été développées et en particulier des méthodes fondées sur un modèle de région de confiance se sont avérées obtenir de bons résultats.Dans cette thèse, nous présentons un nouvel algorithme de région de confiance, basé sur l’interpolation, qui se montre efficace et globalement convergent (en ce sens que sa convergence vers un point stationnaire est garantie depuis tout point de départ arbitraire). Le nouvel algorithme repose sur la technique d’auto-correction de la géométrie proposé par Scheinberg and Toint (2010). Dans leur théorie, ils ont fait avancer la compréhension du rôle de la géométrie dans les méthodes d’OSD à base de modèles. Dans notre travail, nous avons pu améliorer considérablement l’efficacité de leur méthode, tout en maintenant ses bonnes propriétés de convergence. De plus, nous examinons l’influence de différents types de modèles d’interpolation sur les performances du nouvel algorithme.Nous avons en outre étendu cette méthode pour prendre en compte les contraintes de borne par l’application d’une stratégie d’activation. Considérer une méthode avec ensemble actif pour l’optimisation basée sur des modèles d’interpolation donne la possibilité d’économiser une quantité importante d’évaluations de fonctions. Il permet de maintenir les ensembles d’interpolation plus petits tout en poursuivant l’optimisation dans des sous-espaces de dimension inférieure. L’algorithme résultant montre un comportement numérique très compétitif. Nous présentons des résultats sur un ensemble de problèmes-tests issu de la collection CUTEr et comparons notre méthode à des algorithmes de référence appartenant à différentes classes de méthodes d’OSD.Pour réaliser des expériences numériques qui intègrent le bruit, nous créons un ensemble de cas-tests bruités en ajoutant des perturbations à l’ensemble des problèmes sans bruit. Le choix des problèmes bruités a été guidé par le désir d’imiter les problèmes d’optimisation basés sur la simulation. Enfin, nous présentons des résultats sur une application réelle d’un problème de conception de forme d’une aile fourni par Airbus.

Derivative-free optimization (DFO) has enjoyed renewed interest over the past years, mostly motivated by the ever growing need to solve optimization problems defined by functions whose values are computed by simulation (e.g. engineering design, medical image restoration or groundwater supply).In the last few years, a number of derivative-free optimization methods have been developed and especially model-based trust-region methods have been shown to perform well.In this thesis, we present a new interpolation-based trust-region algorithm…

Advisors/Committee Members: Gratton, Serge (thesis director), Toint, Philippe (thesis director).