A comparison of block pivoting and interiorpoint algorithms for linear least squares problems with nonnegative variables
Authors:
Luís F. Portugal, Joaquím J. Júdice and Luís N. Vicente
Journal:
Math. Comp. 63 (1994), 625643
MSC:
Primary 90C20; Secondary 65K05
MathSciNet review:
1250776
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper we discuss the use of block principal pivoting and predictorcorrector methods for the solution of largescale linear least squares problems with nonnegative variables (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 predictorcorrector 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 predictorcorrector and the block principal pivoting algorithms are quite efficient to deal with largescale NVLSQ problems.
 [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. MR 1077727
(91j:65109), http://dx.doi.org/10.1016/00243795(91)90009L
 [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. MR 960847
(90a:65092), http://dx.doi.org/10.1007/BF01403888
 [3]
, Algorithms for linear leastsquares problems, Computer Algorithms for Solving Linear Algebraic Equations (E. Spedicato, ed.), NATO Adv. Sci. Inst. Ser. F: Comput. and Systems Sci., vol. 77, Springer, Berlin and New York, 1992, pp. 5792.
 [4]
J. Carpenter, I. Lustig, J. Mulvey, and D. Shanno, Higher order predictorcorrector interior point methods with applications to quadratic objectives, Tech. Report Rutcor Research Report #67.90, 1990.
 [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. MR
526498 (80g:65048), http://dx.doi.org/10.1137/0716029
 [6]
I. Duff, R. Grimes, and J. Lewis, Sparse matrix test problems, ACM Trans. Math. Software 15 (1989), 114.
 [7]
Alan
George and Michael
T. Heath, Solution of sparse linear least squares problems using
Givens rotations, Linear Algebra Appl. 34 (1980),
69–83. MR
591425 (82f:65040), http://dx.doi.org/10.1016/00243795(80)901597
 [8]
Alan
George and Joseph
W. H. Liu, Computer solution of large sparse positive definite
systems, PrenticeHall, Inc., Englewood Cliffs, N.J., 1981.
PrenticeHall Series in Computational Mathematics. MR 646786
(84c:65005)
 [9]
J.
J. Júdice and F.
M. Pires, Bardtype methods for the linear complementarity problem
with symmetric positive definite matrices, IMA J. Math. Appl. Bus.
Indust. 2 (1988/89), no. 1, 51–68. MR 1001442
(90c:90223), http://dx.doi.org/10.1093/imaman/2.1.51
 [10]
, Direct methods for convex quadratic programs subject to box constraints, Investigação Operacional 9 (1989), 5168.
 [11]
, Solution of largescale strictly convex linear complementarity problems, Investigação Operacional 11 (1991), 3151.
 [12]
Michael
M. Kostreva, Block pivot methods for solving the complementarity
problem, Linear Algebra Appl. 21 (1978), no. 3,
207–215. MR 0503864
(58 #20490)
 [13]
Charles
L. Lawson and Richard
J. Hanson, Solving least squares problems, PrenticeHall,
Inc., Englewood Cliffs, N.J., 1974. PrenticeHall Series in Automatic
Computation. MR
0366019 (51 #2270)
 [14]
Irvin
J. Lustig, Roy
E. Marsten, and David
F. Shanno, Computational experience with a primaldual interior
point method for linear programming, Linear Algebra Appl.
152 (1991), 191–222. Interior point methods for
linear programming. MR 1107553
(92d:90041), http://dx.doi.org/10.1016/00243795(91)902752
 [15]
S. Mehrotra, On the implementation of a (primaldual) interior point method, Tech. Report 03, Department of Civil Engineering and Management Sciences, Northwestern University, Evanston, IL, 1990.
 [16]
Katta
G. Murty, Note on a Bardtype scheme for solving the
complementarity problem, Opsearch 11 (1974),
no. 23, 123–130. MR 0453774
(56 #12028)
 [17]
P. Pardalos, Y. Ye, and C. Han, An interior point algorithm for largescale quadratic problems subject to box constraints, Lecture Notes in Control and Inform. Sci., vol. 144, Springer, Berlin and New York, 1990, pp. 413422.
 [18]
L. Portugal, Solution of leastsquares problems, Master's thesis, Faculdade de Ciências e Tecnologia Universidade de Coimbra, 1992. (Portuguese)
 [1]
 M. Bierlair, P. Toint, and D. Tuyttens, On iterative algorithms for linear leastsquares problems with bound constraints, Linear Algebra Appl. 143 (1991), 111143. MR 1077727 (91j:65109)
 [2]
 Å. Björck, A direct method for sparse leastsquares problems with lower and upper bounds, Numer. Math. 54 (1988), 1932. MR 960847 (90a:65092)
 [3]
 , Algorithms for linear leastsquares problems, Computer Algorithms for Solving Linear Algebraic Equations (E. Spedicato, ed.), NATO Adv. Sci. Inst. Ser. F: Comput. and Systems Sci., vol. 77, Springer, Berlin and New York, 1992, pp. 5792.
 [4]
 J. Carpenter, I. Lustig, J. Mulvey, and D. Shanno, Higher order predictorcorrector interior point methods with applications to quadratic objectives, Tech. Report Rutcor Research Report #67.90, 1990.
 [5]
 A. Cline, C. Moler, G. Stewart, and J. Wilkinson, An estimate for the condition number of a matrix, SIAM J. Numer. Anal. 16 (1979), 368675. MR 526498 (80g:65048)
 [6]
 I. Duff, R. Grimes, and J. Lewis, Sparse matrix test problems, ACM Trans. Math. Software 15 (1989), 114.
 [7]
 A. George and M. Heath, Solution of sparse linear leastsquares problems using Givens rotations, Linear Algebra Appl. 34 (1980), 6983. MR 591425 (82f:65040)
 [8]
 A. George and J. Liu, Computer solution of large sparse symmetric positive definite systems, PrenticeHall, Englewood Cliffs, NJ, 1981. MR 646786 (84c:65005)
 [9]
 J. Júdice and F. Pires, Bardtype methods for the linear complementarity problem with symmetric positive definite matrices, IMA J. Appl. Math. 2 (1988/89), 2356. MR 1001442 (90c:90223)
 [10]
 , Direct methods for convex quadratic programs subject to box constraints, Investigação Operacional 9 (1989), 5168.
 [11]
 , Solution of largescale strictly convex linear complementarity problems, Investigação Operacional 11 (1991), 3151.
 [12]
 M. Kostreva, Block pivot methods for solving the complementarity problem, Linear Algebra Appl. 21 (1978), 207215. MR 0503864 (58:20490)
 [13]
 C. Lawson and R. Hanson, Solving leastsquares problems, PrenticeHall, Englewood Cliffs, NJ, 1974. MR 0366019 (51:2270)
 [14]
 I. Lustig, R. Marsten, and D. Shanno, Computational experience with a primaldual interior point method for linear programming, Linear Algebra Appl. 152 (1991), 191222. MR 1107553 (92d:90041)
 [15]
 S. Mehrotra, On the implementation of a (primaldual) interior point method, Tech. Report 03, Department of Civil Engineering and Management Sciences, Northwestern University, Evanston, IL, 1990.
 [16]
 K. Murty, Note on a Bardtype scheme for solving the complementarity problem, Oper. Res. 11 (1974), 123130. MR 0453774 (56:12028)
 [17]
 P. Pardalos, Y. Ye, and C. Han, An interior point algorithm for largescale quadratic problems subject to box constraints, Lecture Notes in Control and Inform. Sci., vol. 144, Springer, Berlin and New York, 1990, pp. 413422.
 [18]
 L. Portugal, Solution of leastsquares problems, Master's thesis, Faculdade de Ciências e Tecnologia Universidade de Coimbra, 1992. (Portuguese)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
90C20,
65K05
Retrieve articles in all journals
with MSC:
90C20,
65K05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718199412507764
PII:
S 00255718(1994)12507764
Keywords:
Least squares problems,
linear complementarity problem,
quadratic programming,
sparse matrices,
largescale optimization
Article copyright:
© Copyright 1994
American Mathematical Society
