A Projection Method for Least Squares Problems with a Quadratic Equality Constraint

Abstract

We consider the least squares problem with a quadratic equality constraint (LSQE), i.e., minimizing |Ax-b|2 subject to $\|x\|_2=\alpha$, without the assumption $\|A^\dagger b\|_2>\alpha$ which is commonly imposed in the literature. Structure and perturbation analysis are given to demonstrate the sensitivity of the LSQE problem. We present a projection method combined with correction techniques (PMCT) for solving numerically the LSQE problem when the LSQE problem is ill-conditioned. We also give a detailed convergence analysis of our algorithms to illustrate the convergence behavior. Our algorithms have some obvious advantages over Newton's method and variants. Numerical experiments indicate that PMCT is much more efficient than Newton's methods when the LSQE problem is ill-conditioned; PMCT has a 90% success rate in terms of convergence, while commonly used Newton-type iterations almost always fail.