Groupe d’études et de recherche en analyse des décisions

G-2018-07

A regularized interior-point method for constrained linear least squares

, et

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). Regularization allows us to dispense with the assumption that the active gradients are linearly independent. At each iteration, a linear system with a symmetric quasi-definite (SQD) matrix is solved. This matrix is shown to be uniformly bounded and nonsingular. The linear system may be solved using sparse LDL\({}^{\mathrm{T}}\) factorization, sparse QR factorization, or a factorization-free method. The last two approaches make use of the fact that SQD linear systems may be solved as regularized unconstrained linear least-squares problems. We establish conditions under which a solution of the original, constrained least-squares problem is recovered. We report computational experience and illustrate the potential advantages of our approach.

, 20 pages