Residual QPAS subspace (ResQPASS) algorithm for bounded-variable least squares (BVLS) with superlinear Krylov convergence
share
This paper presents the Residual QPAS Subspace method (ResQPASS) method that solves large-scale least-squares problem with bound constraints on the variables. The problem is solved by creating a series of small problems with increasing size by projecting on the basis residuals. Each projected problem is solved by the QPAS method that is warm-started with a working set and the solution of the previous problem. The method coincides with conjugate gradients (CG) applied to the normal equations when none of the constraints is active. When only a few constraints are active the method converges, after a few initial iterations, as the CG method. We develop a convergence theory that links the convergence with Krylov subspaces. We also present an efficient implementation where the matrix factorizations using QR are updated over the inner and outer iterations.
READ FULL TEXT