×

zbMATH — the first resource for mathematics

A direct active set algorithm for large sparse quadratic programs with simple bounds. (English) Zbl 0691.90070
The authors show how a direct active set method can be efficiently implemented for quadratic problems of the form min \(x^ TAx+b^ Tx\), \(\ell \leq x\leq u\), where A is an \(n\times n\) symmetric (not necessarily positive definite) large and sparse matrix. The following improvements to the basic algorithm are proposed: (1) a new way to find a search direction in the indefinite case that allows to free more than one variable at a time; (2) a new heuristic method for finding a starting point.
Further it is shown how projection techniques can be used to add several constraints to the active set at each iteration. The experimental results showed that the algorithm with these improvements is faster for positive definite problems and finds local minima with lower function values for indefinite problems. The designed algorithms are not in general polynomial and in the indefinite case find only local minima.
Reviewer: K.Zimmermann

MSC:
90C20 Quadratic programming
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
65F30 Other matrix algorithms (MSC2010)
90C06 Large-scale problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J.L. Barlow, ”The use of three different rank detection methods in the solution of sparse weighted and equality constrained least squares problems,” Technical Report CS-88-18, The Pennsylvania State University (University Park, PA, 1988).
[2] D.P. Bertsekas, ”Projected Newton methods for optimization problems with simple constraints,”SIAM Journal on Control and Optimization 20 (1982) 221–246. · Zbl 0507.49018
[3] A. Björck, ”A direct method for sparse least squares problems with lower and upper bounds,”Numerische Mathematik 54 (1988) 19–32. · Zbl 0659.65039
[4] P.H. Calamai and J.J. Moré, ”Projected gradient methods for linearly constrained problems,”Mathematical Programming 39 (1987) 93–116. · Zbl 0634.90064
[5] T.F. Coleman, ”A chordal preconditioner for large scale optimization,”Mathematical Programming 40 (1988) 265–287. · Zbl 0685.90085
[6] A.R. Conn, N.I.M. Gould and Ph.L. Toint, ”Global convergence of a class of trust region algorithms for optimization with simple bounds,”SIAM Journal on Numerical Analysis 25 (1988) 433–460. · Zbl 0643.65031
[7] A.R. Conn, N.I.M. Gould and Ph.L. Toint, ”Testing a class of methods for solving minimization problems with simple bounds on the variables,”Mathematics of Computation 50 (1988) 399–430. · Zbl 0645.65033
[8] R.S. Dembo and U. Tulowitzki, ”On the minimization of quadratic functions subject to box constraints,” Technical Report B 71, Yale University (New Haven, CT, 1983).
[9] J.J. Dongarra, J.R. Bunch, C.B. Moler and G.W. Stewart,LINPACK Users’ Guide (SIAM, Philadelphia, PA, 1979).
[10] G.C. Everstine, ”A comparison of three resequencing algorithms for the reduction of matrix profile and wave front”,International Journal for Numerical Methods in Engineering 14 (1979) 837–853. · Zbl 0401.73082
[11] R. Fletcher, ”A general quadratic programming algorithm,”Journal of the Institute of Mathematics and its Applications 7 (1971) 76–91. · Zbl 0226.90036
[12] R. Fletcher and M.P. Jackson, ”Minimization of a quadratic function of many variables subject only to lower and upper bounds,”Journal of the Institute of Mathematics and Its Applications 14 (1974) 159–174. · Zbl 0301.90032
[13] A. George and J.W.H. Liu,Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, NY, 1981). · Zbl 0516.65010
[14] J.R. Gilbert and T. Peierls, ”Sparse partial pivoting in time proportional to arithmetic operations,”SIAM Journal on Scientific and Statistical Computing 9 (1988) 862–874. · Zbl 0656.65036
[15] P.E. Gill and W. Murray, ”Numerically stable methods for quadratic programming,Mathematical Programming 14 (1978) 349–372. · Zbl 0374.90054
[16] P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, New York, 1981). · Zbl 0503.90062
[17] G.H. Golub and C.F. Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, MD, 1983). · Zbl 0559.65011
[18] N.J. Higham, ”Fortran codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation,” Technical Report Numerical Analysis Report No. 135, University of Manchester (Manchester, UK, 1987).
[19] J.J. Moré, ”Numerical solution of bound constrained problems,” Technical Report 96, Argonne National Laboratory (Argonne, IL, 1987).
[20] J.J. Moré and D.C. Sorensen, ”Computing a trust region step,”SIAM Journal on Scientific and Statistical Computing (1983) 553–572. · Zbl 0551.65042
[21] J.J. Moré and G. Toraldo, ”Algorithms for bound constrained quadratic programming problems,” Technical Report 117, Argonne National Laboratory (Argonne, IL, 1988). · Zbl 0675.65061
[22] K.G. Murty and S.N. Kabadi, ”Some NP-complete problems in quadratic and nonlinear programming,”Mathematical Programming 39 (1987) 117–129. · Zbl 0637.90078
[23] S. Parter, ”The use of linear graphs in Gauss elimination,”SIAM Review 3 (1961) 119–130. · Zbl 0102.11302
[24] D.J. Rose, R.E. Tarjan and G.S. Leuker, ”Algorithmic aspects of vertex elimination on graphs,”SIAM Journal on Computing 5 (1976) 266–283. · Zbl 0353.65019
[25] M. Yannakakis, ”Computing the minimum fill-in is NP-complete,”SIAM Journal on algebraic and Discrete Methods 2 (1981) 77–79. · Zbl 0496.68033
[26] Y. Ye and E. Tse, ”A polynomial-time algorithm for convex quadratic programming,” Technical Report, Stanford University (Stanford, CA, 1986).
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.