Solving quadratically constrained least squares using black box solvers

Abstract

We present algorithms for solving quadratically constrained linear least squares problems that do not necessarily require expensive dense matrix factorizations. Instead, only “black box” solvers for certain related unconstrained least squares problems, as well as the solution of two related linear systems involving the coefficient matrixA and the constraint matrixB, are required. Special structures in the problem can thus be exploited in these solvers, and iterative as well as direct solvers can be used. Our approach is to solve for the Lagrange multiplier as the root of an implicitly-defined secular equation. We use both a linear and a rational (Hebden) local model and a Newton and secant method. We also derive a formula for estimating the Lagrange multiplier which depends on the amount the unconstrained solution violates the constraint and an estimate of the smallest generalized singular value ofA andB. The Lagrange multiplier estimate can be used as a good initial guess for solving the secular equation. We also show conditions under which this estimate is guaranteed to be an acceptable solution without further refinement. Numerical results comparing the different algorithms are presented.