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
This matrix is shown to be uniformly bounded and
nonsingular. The linear system may be solved using sparse LDL
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.
Published February 2018 , 20 pages