A Regularized Interior-Point Method for Constrained Linear Least Squares

We propose an infeasible interior-point algorithm for constrained linear least-squares problems based on the primal-dual regularization of convex programs of Friedlander and Orban (2012). At each iteration, the sparse LDLT factorization of a symmetric quasi-definite matrix is computed. This coefficient matrix is shown to be uniformly bounded and nonsingular. We establish conditions under which a solution of the original problem is recovered. The regularization allows us to dispense with the assumption that the active gradients are linearly independent. Although the implementation described here is factorization based, it paves the way for a matrix-free implementation in which a regularized unconstrained linear least-squares problem is solved at each iteration. We report on computational experience and illustrate the potential advantages of our approach.

Résumé

Nous proposons une méthode de points intérieurs non réalisable pour le problème aux moindres carrés linéaire avec contraintes basée sur la régularisation primale-duale de problèmes quadratiques convexes de Friedlander et Orban (2012). À chaque itération, la méthode effectue une factorisation LDLT creuse d'une matrice symétrique et quasi définie. Cette matrice est uniformément bornée et non singulière. Nous établissons des conditions sous lesquelles la méthode produit une solution du problème original. La régularisation nous permet d'éliminer l'hypothèse que les gradients actifs sont linéairement indépendants. Bien que l'implémentation proposée ici repose sur une factorisation, elle ouvre la voie à une implémentation itérative dans laquelle on résout un problème aux moindres carrés régularisé sans contraintes de façon inexacte à chaque itération. Nous illustrons notre approche sur plusieurs applications qui mettent en évidence ses avantages.