Solving the minimal least squares problem subject to bounds on the variables. (English) Zbl 0546.65041

The author considers a solution method for linear least squares problems subject to lower and upper bounds on the variables. In a first step, an arbitrary solution is found based on an active set strategy. The corresponding subproblems are either solved by direct factorization (QR) or a conjugate gradient method. Subsequently the minimum norm solution of the least squares problem is determined. The algorithm and details on its numerical implementation are outlined and some numerical results are presented.
Reviewer: K.Schittkowski


65K05 Numerical mathematical programming methods
90C20 Quadratic programming
62J05 Linear regression; mixed models
65H10 Numerical computation of solutions to systems of equations
Full Text: DOI


[1] Å. Björck and T. Elfving,Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations. BIT 19 (1979), 145–163. · Zbl 0409.65022
[2] P. Businger and G. H. Golub,Linear least squares solutions by Householder transformations. Num. Math. 7 (1965), 269–276. · Zbl 0142.11503
[3] 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. · Zbl 0403.65012
[4] C. Cryer,The solution of a quadratic programming problem using systematic overrelaxation. SIAM J. Control 9 (1971), 385–392. · Zbl 0216.54603
[5] U. Eckhardt,Quadratic programming by successive overrelaxation. Report Jül-1064-MA, Kernforschungsanlage, Jülich (1974).
[6] L. Eldén,Numerical analysis of regularization and constrained least squares methods. Ph.D. thesis, Dept. of Mathematics, Linköping University, Linköping (1977).
[7] R. Fletcher,Practical Methods of Optimization, vol. 2, Constrained Optimization. Wiley, Chichester-New York (1981). · Zbl 0474.65043
[8] 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. · Zbl 0301.90032
[9] P. E. Gill, G. H. Golub, W. Murray and M. A. Saunders,Methods for modifying matrix factorizations. Math. Comp. 28 (1974), 505–535. · Zbl 0289.65021
[10] P. E. Gill and W. Murray,Minimization subject to bounds on the variables. NPL report NAC 72, National Physical Laboratory, Teddington (1976). · Zbl 0345.65020
[11] P. E. Gill and W. Murray,Numerically stable methods for quadratic programming. Math. Prog. 14 (1978), 349–372. · Zbl 0374.90054
[12] P. E. Gill, W. Murray and M. H. Wright,Practical Optimization. Academic Press, London-New York (1981). · Zbl 0503.90062
[13] 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. · Zbl 0461.90056
[14] I. Karasalo,A criterion for truncation of the QR-decomposition algorithm for the singular linear least squares problem. BIT 14 (1974), 156–166. · Zbl 0282.65030
[15] C. L. Lawson and R. J. Hanson,Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, NJ (1974). · Zbl 0860.65028
[16] 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)). · Zbl 0501.70006
[17] R. Mifflin,A stable method for solving certain constrained least squares problems. Math. Prog. 16 (1979), 141–158. · Zbl 0407.90065
[18] D. P. O’Leary,A generalized conjugate gradient algorithm for solving a class of quadratic programming problems. Lin. Alg. Appl. 34 (1980), 371–399. · Zbl 0464.65039
[19] 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. · Zbl 0378.65026
[20] J. Stoer,On the numerical solution of constrained least-squares problems. SIAM J. Num. Anal. 8 (1971), 382–411. · Zbl 0219.90039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.