Abstract
A computational procedure is developed for determining the solution of minimal length to a linear least squares problem subject to bounds on the variables. In the first stage, a solution to the least squares problem is computed and then in the second stage, the solution of minimal length is determined. The objective function in each step is minimized by an active set method adapted to the special structure of the problem.
The systems of linear equations satisfied by the descent direction and the Lagrange multipliers in the minimization algorithm are solved by direct methods based on QR decompositions or iterative preconditioned conjugate gradient methods. The direct and the iterative methods are compared in numerical experiments, where the solutions are sought to a sequence of related, minimal least squares problems subject to bounds on the variables. The application of the iterative methods to large, sparse problems is discussed briefly.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Å. Björck and T. Elfving,Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations. BIT 19 (1979), 145–163.
P. Businger and G. H. Golub,Linear least squares solutions by Householder transformations. Num. Math. 7 (1965), 269–276.
A. K. Cline, C. B. Moler, G. W. Stewart and J. H. Wilkinson,An estimate for the condition number of a matrix. SIAM J. Numer. Anal. 16 (1979), 368–375.
C. Cryer,The solution of a quadratic programming problem using systematic overrelaxation. SIAM J. Control 9 (1971), 385–392.
U. Eckhardt,Quadratic programming by successive overrelaxation. Report Jül-1064-MA, Kernforschungsanlage, Jülich (1974).
L. Eldén,Numerical analysis of regularization and constrained least squares methods. Ph.D. thesis, Dept. of Mathematics, Linköping University, Linköping (1977).
R. Fletcher,Practical Methods of Optimization, vol. 2, Constrained Optimization. Wiley, Chichester-New York (1981).
R. Fletcher and M. P. Jackson,Minimization of a quadratic function of many variables subject only to lower and upper bounds. J. Inst. Maths Applics 14 (1974), 159–174.
P. E. Gill, G. H. Golub, W. Murray and M. A. Saunders,Methods for modifying matrix factorizations. Math. Comp. 28 (1974), 505–535.
P. E. Gill and W. Murray,Minimization subject to bounds on the variables. NPL report NAC 72, National Physical Laboratory, Teddington (1976).
P. E. Gill and W. Murray,Numerically stable methods for quadratic programming. Math. Prog. 14 (1978), 349–372.
P. E. Gill, W. Murray and M. H. Wright,Practical Optimization. Academic Press, London-New York (1981).
K. H. Haskell, and R. J. Hanson,An algorithm for linear least squares problems with equality and nonnegativity constraints. Math. Prog. 21 (1981), 98–118.
I. Karasalo,A criterion for truncation of the QR-decomposition algorithm for the singular linear least squares problem. BIT 14 (1974), 156–166.
C. L. Lawson and R. J. Hanson,Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, NJ (1974).
P. Lötstedt,Numerical simulation of time-dependent contact and friction problems in rigid body mechanics. Report TRITA-NA-8214, Dept. of Num. Anal. and Comp. Science, Royal Institute of Technology, Stockholm (1982) (to appear in SIAM J. Sci. Stat. Comput 5 (1984)).
R. Mifflin,A stable method for solving certain constrained least squares problems. Math. Prog. 16 (1979), 141–158.
D. P. O'Leary,A generalized conjugate gradient algorithm for solving a class of quadratic programming problems. Lin. Alg. Appl. 34 (1980), 371–399.
K. Schittkowski and J. Stoer.A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes. Num. Math. 31 (1979), 431–463.
J. Stoer,On the numerical solution of constrained least-squares problems. SIAM J. Num. Anal. 8 (1971), 382–411.
Author information
Authors and Affiliations
Additional information
This work was supported by The National Swedish Board for Technical Development under contract dnr 80-3341.
Rights and permissions
About this article
Cite this article
Lötstedt, P. Solving the minimal least squares problem subject to bounds on the variables. BIT 24, 205–224 (1984). https://doi.org/10.1007/BF01937487
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01937487