Cette thèse étudie la méthode du gradient conjugué et la méthode de Lanczos pour la résolution des problèmes aux moindres carrés non-linéaires sous-déterminés 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 qui sont estimés par régression non linéaire. Nous supposons ici que n est grand par rapport à m. Ces problèmes se retrouvent, par exemple, lorsque des champs à trois dimensions sont estimées à partir d'observations physiques, comme c'est le cas 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 de 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 de coût et que la convergence n'est pas garantie. La suppression de cette difficulté est généralement réalisé en utilisant une recherche linéaire (Dennis et Schnabel, 1983) ou par méthode de région de confiance (Conn, Gould et 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 et Toint, 2000, pp 133-139).
La résolution de ce sous-problème dans un espace à n dimensions (par CG ou Lanczos) est considéré 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 (Courtier, 1997), connu sous le nom de Système d'analyse Statistique de l'espace Physıque (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, l'utilisation de PSAS peut être excessivement coûteuse car il a été remarqué que la fonction de coût linéaire des moindres carrés ne diminue pas monotonement au cours des itérations non-linéaires.
Une autre approche duale a été proposée par Gratton et Tshimanga (2009) et est connue comme la méthode du gradient conjugué préconditionné restreint (RPCG). Il génère les mêmes itérations en arithmétique exacte que celles générés par l'approche primale, à nouveau en utilisant la formule de récurrence impliquant des vecteurs taille m. L'intérêt principal de RPCG est qu'il en résulte une réduction significative de la mémoire utilisée et des coûts de calculs tout en conservant la propriété de convergence souhaitée, contrairement à l'algorithme PSAS. La relation entre ces deux approches duales et la question de dériver efficacement les préconditionneurs (Gratton, Sartenaer et Tshimanga, 2011), essentielles dans le cas de problèmes à grande échelle, n'ont pas été abordées dans Gratton et Tshimanga (2009).
La motivation principale de cette thèse est de répondre à ces questions. En particulier, nous nous intéressons à la conception de techniques de préconditionnement et à une généralisation des régions de confiance qui maintiennent la correspondance une-à-une entre itérations primales et duales, offrant ainsi un calcul efficace dans un algorithme globalement convergent. |
This thesis investigates the conjugate-gradient method and the Lanczos method for the solution of under-determined nonlinear least-squares problems regularized by a quadratic penalty term. Such problems often result from a maximum likelihood approach, and involve a set of m physical observations and n unknowns that are estimated by nonlinear regression. We suppose here that n is large compared to m. These problems are encountered for instance when three-dimensional fields are estimated from physical observations, as is the case in data assimilation in Earth system models.
A widely used algorithm in this context is the Gauss-Newton (GN) method, known in the data assimilation community under the name of incremental four dimensional variational data assimilation. The GN method relies on the approximate solution of a sequence of linear least-squares problems in which the nonlinear least-squares cost function is approximated by a quadratic function in the neighbourhood of the current nonlinear iterate. However, it is well known that this simple variant of the Gauss-Newton algorithm does not ensure a monotonic decrease of the cost function and that convergence is not guaranteed. Removing this difficulty is typically achieved by using a line-search (Dennis and Schnabel, 1983) or trust-region (Conn, Gould and Toint, 2000) strategy, which ensures global convergence to first order critical points under mild assumptions. We consider the second of these approaches in this thesis.
Moreover, taking into consideration the large-scale nature of the problem, we propose here to use a particular trust-region algorithm relying on the Steihaug-Toint truncated conjugate-gradient method for the approximate solution of the subproblem (Conn, Gould and Toint, 2000, pp. 133-139).
Solving this subproblem in the n-dimensional space (by CG or Lanczos) is referred to as the primal approach. Alternatively, a significant reduction in the computational cost is possible by rewriting the quadratic approximation in the m-dimensional space associated with the observations. This is important for large-scale applications such as those solved daily in weather prediction systems. This approach, which performs the minimization in the m-dimensional space using CG or variants thereof, is referred to as the dual approach.
The first proposed dual approach (Courtier, 1997), known as the Physical-space
Statistical Analysis System (PSAS) in the data assimilation community starts by solving the corresponding dual cost function in m-dimensional space by a standard preconditioned CG (PCG), and then recovers the step in n-dimensional space through multiplication by an n by m matrix. Technically, the algorithm consists of recurrence formulas involving m-vectors instead of n-vectors. However, the use of PSAS can be unduly costly as it was noticed that the linear least-squares cost function does not monotonically decrease along the nonlinear iterations when applying standard termination.
Another dual approach has been proposed by Gratton and Tshimanga (2009) and is known as the Restricted Preconditioned Conjugate Gradient (RPCG) method. It generates the same iterates in exact arithmetic as those generated by the primal approach, again using recursion formula involving m-vectors. The main interest of RPCG is that it results in significant reduction of both memory and computational costs while maintaining the desired convergence property, in contrast with the PSAS algorithm. The relation between these two dual approaches and the question of deriving efficient preconditioners (Gratton, Sartenaer and Tshimanga, 2011) { essential when large-scale problems are considered { was not addressed in Gratton and Tshimanga (2009).
The main motivation for this thesis is to address these open issues. In particular, we are interested in designing preconditioning techniques and a trust-region globalization which maintains the one-to-one correspondance between primal and dual iterates, thereby offering a cost-effective computation in a globally convergent algorithm. |