Abstract
We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.
The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.
Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. Beyer, “FLECS—Fortran Language with Extended Control Structures—User's manual”, University of Oregon Computing Center, Eugene, OR (September 1974).
C.W. de Boor, “Package for calculating withB-splines”,SIAM Journal on Numerical Analysis 14 (1977) 441–442.
A.K. Cline, “The transformation of a quadratic programming problem into solvable form”, ICASE Rept. No. 75-14 (August 1975).
L. Eldén, “Numerical analysis of regularization and constrained least squares methods”, Part V, Linköping Studies in Science and Technology, Dissertations, No. 21, LiTH-MAT-R-1977-20 (1977).
M. Gentleman, “Least squares computations by Givens transformations without square roots”,Journal of the Institute of Mathematics and its Applications 12 (1973) 329–336.
G.H. Golub and M.A. Saunders, “Linear least squares and quadratic programming”, in: J. Abadie, ed.,Integer and nonlinear programming, II (North-Holland, Amsterdam, 1970) pp. 229–256.
K.H. Haskell and R.J. Hanson, “Selected algorithms for the linearly constrained least squares problem—A user's guide”, SAND78-1290, Sandia Laboratories, Albuquerque, NM (1979).
C.L. Lawson, R.J. Hanson, D.R. Kincaid and F.T. Krogh, “Basic linear algebra subprograms for Fortran usage”,ACM Transactions on Mathematical Software 5 (1979) 308–323.
C.L. Lawson and R.J. Hanson,Solving least squares problems (Prentice-Hall, Englewood Cliffs, NJ, 1974).
C.L. Lawson, “On the discovery and description of mathematical programming algorithms”, in: A. Dold and B. Eckmann, eds.,Lecture Notes in Mathematics, Vol. 506 (Springer, Berlin, 1976) pp. 157–165.
R. Mifflin, “A stable method for solving certain constrained least squares problems”,Mathematical Programming 16 (1979) 141–158.
K. Schittkowski and J. Stoer, “A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes”,Numerische Mathematik 31 (1979) 431–463.
J. Stoer, “On the numerical solution of constrained least squares problems”,SIAM Journal on Numerical Analysis 8 (2) (1971) 382–411.
G. Strang and G. Fix,An analysis of the finite element method (Prentice-Hall, Englewood Cliffs, NJ, 1973) p. 56.
P. Wolfe, “Finding the nearest point in a polytope”,Mathematical Programming 11 (1976) 128–149.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Haskell, K.H., Hanson, R.J. An algorithm for linear least squares problems with equality and nonnegativity constraints. Mathematical Programming 21, 98–118 (1981). https://doi.org/10.1007/BF01584232
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01584232