A regularized interior-point method for constrained linear least squares. Issue 2 (2nd April 2020)

• Record Type: Journal Article
• Authors: Dehghani, Mohsen; Lambe, Andrew; Orban, Dominique
• Is Part Of: Infor. Volume 58:Issue 2(2020)
• Page Start: 202
• Page End: 224
• Publication Date: 2020-04-02
• Subjects: Linear least squares -- symmetric quasi-definite system -- interior-point method -- primal-dual regularization -- proximal point -- augmented Lagrangian; Operations research -- Periodicals; Electronic data processing -- Periodicals; Systems engineering -- Periodicals; Systems engineering; Electronic data processing; Periodicals; 003.05
• DOI: 10.1080/03155986.2018.1559428
• Languages: English
• ISSNs: 0315-5986

Abstract

Abstract: 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. 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. While the linear system may be solved using sparse LDL T factorization, we observe that other approaches may be used. In particular, we build on the connection between SQD linear systems and unconstrained linear least-squares problems to solve the linear system with sparse QR factorization. We establish conditions under which a solution of the original, constrained least-squares problem is recovered. We report computational experience with the sparse QR factorization and illustrate the potential advantages of our approach.