A comparison of block pivoting and interior-point algorithms for linear least squares problems with nonnegative variables. (English) Zbl 0812.90124
Summary: We discuss the use of block principal pivoting and predictor-corrector methods for the solution of large-scale linear least squares problems with nonnegative varibles (NVLSQ). We also describe two implementations of these algorithms that are based on the normal equations and corrected seminormal equations (CSNE) approaches. We show that the method of normal equations should be employed in the implementation of the predictor- corrector algorithm. This type of approach should also be used in the implementation of the block principal pivoting method, but a switch to the CSNE method may be useful in the last iterations of the algorithm. Computational experience is also included in this paper and shows that both the predictor-corrector and the block principal pivoting algorithms are quite efficient to deal with large-scale NVLSQ problems.
MSC:
| 90C20 | Quadratic programming |
| 65F50 | Computational methods for sparse matrices |
| 90C06 | Large-scale problems in mathematical programming |
Keywords:
block principal pivoting; predictor-corrector methods; large-scale linear least squares; nonnegative variblesReferences:
| [1] | M. Bierlaire, Ph. L. Toint, and D. Tuyttens, On iterative algorithms for linear least squares problems with bound constraints, Linear Algebra Appl. 143 (1991), 111 – 143. · Zbl 0722.65019 · doi:10.1016/0024-3795(91)90009-L |
| [2] | Åke Björck, A direct method for sparse least squares problems with lower and upper bounds, Numer. Math. 54 (1988), no. 1, 19 – 32. · Zbl 0659.65039 · doi:10.1007/BF01403888 |
| [3] | -, Algorithms for linear least-squares problems, Computer Algorithms for Solving Linear Algebraic Equations , NATO Adv. Sci. Inst. Ser. F: Comput. and Systems Sci., vol. 77, Springer, Berlin and New York, 1992, pp. 57-92. |
| [4] | J. Carpenter, I. Lustig, J. Mulvey, and D. Shanno, Higher order predictor-corrector interior point methods with applications to quadratic objectives, Tech. Report Rutcor Research Report #67.90, 1990. · Zbl 0794.90043 |
| [5] | 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), no. 2, 368 – 375. · Zbl 0403.65012 · doi:10.1137/0716029 |
| [6] | I. Duff, R. Grimes, and J. Lewis, Sparse matrix test problems, ACM Trans. Math. Software 15 (1989), 1-14. · Zbl 0667.65040 |
| [7] | Alan George and Michael T. Heath, Solution of sparse linear least squares problems using Givens rotations, Linear Algebra Appl. 34 (1980), 69 – 83. · Zbl 0459.65025 · doi:10.1016/0024-3795(80)90159-7 |
| [8] | Alan George and Joseph W. H. Liu, Computer solution of large sparse positive definite systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981. Prentice-Hall Series in Computational Mathematics. · Zbl 0516.65010 |
| [9] | J. J. Júdice and F. M. Pires, Bard-type methods for the linear complementarity problem with symmetric positive definite matrices, IMA J. Math. Appl. Bus. Indust. 2 (1988/89), no. 1, 51 – 68. · Zbl 0674.90091 · doi:10.1093/imaman/2.1.51 |
| [10] | -, Direct methods for convex quadratic programs subject to box constraints, Investigação Operacional 9 (1989), 51-68. |
| [11] | -, Solution of large-scale strictly convex linear complementarity problems, Investigação Operacional 11 (1991), 31-51. |
| [12] | Michael M. Kostreva, Block pivot methods for solving the complementarity problem, Linear Algebra Appl. 21 (1978), no. 3, 207 – 215. · Zbl 0395.65032 · doi:10.1016/0024-3795(78)90083-6 |
| [13] | Charles L. Lawson and Richard J. Hanson, Solving least squares problems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Prentice-Hall Series in Automatic Computation. · Zbl 0860.65028 |
| [14] | Irvin J. Lustig, Roy E. Marsten, and David F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Linear Algebra Appl. 152 (1991), 191 – 222. Interior point methods for linear programming. · Zbl 0731.65049 · doi:10.1016/0024-3795(91)90275-2 |
| [15] | S. Mehrotra, On the implementation of a (primal-dual) interior point method, Tech. Report 03, Department of Civil Engineering and Management Sciences, Northwestern University, Evanston, IL, 1990. · Zbl 0773.90047 |
| [16] | Katta G. Murty, Note on a Bard-type scheme for solving the complementarity problem, Opsearch 11 (1974), no. 2-3, 123 – 130. |
| [17] | P. Pardalos, Y. Ye, and C. Han, An interior point algorithm for large-scale quadratic problems subject to box constraints, Lecture Notes in Control and Inform. Sci., vol. 144, Springer, Berlin and New York, 1990, pp. 413-422. |
| [18] | L. Portugal, Solution of least-squares problems, Master’s thesis, Faculdade de Ciências e Tecnologia Universidade de Coimbra, 1992. (Portuguese) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
