Algorithmes de moindres carrés non linéaires en précision mixte avec applications aux problèmes d'ajustement de faisceaux

Cette maîtrise explore les différentes méthodes de résolution des moindres carrés non-linéaires présentes dans la littérature, les compare et détermine lesquelles sont les plus adaptées pour la résolution de grands problèmes creux. En particulier, nous proposons des alternatives aux problèmes mal conditionnés. Pour cela, nous avons commencé par étudier en détail les problèmes de moindres carrés non-linéaires et l’algorithme de Levenberg-Marquardt. Nous nous sommes ensuite concentrés sur la méthode de résolution du sous-problème et en particulier les méthodes de résolution inexacte du sous-problème. Nous avons d’abord étudié les méthodes proposées par Ceres, un logiciel de résolution de moindres carrés non linéaires qui représente l’état de l’art en la matière. Nous avons ensuite proposé une reformulation du problème qui permet l’utilisation de différentes méthodes itératives et préconditionneurs. Nous implémentons ces différentes méthodes de résolution en Julia pour les comparer et intégrer différentes technologies comme la précision mixte, la différentiation automatique, et le calcul sur GPUs. Nos résultats montrent que la reformulation du sous-problème de moindres carrés linéaires sans former les équations normales permet de réduire d’un facteur important le conditionnement des matrices. De plus, l’utilisation de précision mixte, et GPUs, si elle est faite de manière optimale, permet une accélération notable des calculs. Enfin, la différentiation automatique permet de généraliser notre code pour tous les problèmes dont on ne dispose pas d’un détail de la matrice jacobienne.

Abstract

This master’s thesis explores and compares the different existing methods in the litterature to solve large sparse nonlinear least squares problems. In particular, we suggest alternative solutions for ill-conditioned problems. In order to do that we started off by studying the Levenberg-Marquardt algorithm. We then focused on solving the subproblem and in particular inexact resolution of this subproblem. We first investigated the methods offered by Ceres, a state of the art nonlinear least squares solver. We then proceeded to rework the problem based on the KKT conditions of the linear least squares problem without forming normal equations that allows the use of other iterative methods and preconditioners. We implemend all theses solutions in Julia to compare them and integrate different technologies like mixed precision, automatic differentiation, and GPUs computations. Our results show that the reformulation of the sub-problem without forming the normal equations allows to reduce the conditioning of the matrices. On top of that, if well used, mixed precision and GPUs computations allow a clear improvement of the results. Finally, automatic differentiation use allows to generalize our code for all the problems for which we don’t have a detail of the jacobian matrix.