Bounded-Variable Least-Squares: an Algorithm and Applications

The Fortran subroutine BVLS (bounded variable least-squares) solves linear least-squares problems with upper and lower bounds on the variables, using an active set strategy. The unconstrained least-squares problems for each candidate set of free variables are solved using the QR decomposition. BVLS has a “warm-start ” feature permitting some of the variables to be initialized at their upper or lower bounds, which speeds the solution of a sequence of related problems. Such sequences of problems arise, for example, when BVLS is used to find bounds on linear functionals of a model constrained to satisfy, in an approximate lp-norm sense, a set of linear equality constraints in addition to upper and lower bounds. We show how to use BVLS to solve that problem when p = 1, 2, or ∞, and to solve minimum l1 and l ∞ fitting problems. FORTRAN 77 code implementing BVLS is available from the statlib gopher at Carnegie Mellon University.