zbMATH — the first resource for mathematics

A class of methods for solving large, convex quadratic programs subject to box constraints. (English) Zbl 0737.90046
Summary: We analyze conjugate gradient-type algorithms for solving convex quadratic programs subject only to box constraints (i.e. lower and upper bounds on the variables). Programs of this type, which we denote by BQP, play an important role in many optimization models and algorithms. We propose a new class of finite algorithms based on a nonfinite heuristic for solving a large, sparse BQP. The numerical results suggest that these algorithms are competitive with the CRGP algorithm of R. S. Dembo and U. Tulowitzki [“On the minimization of a quadratic function subject to box constraints”, Working Paper No. 71, Ser. B, School Organiz. Manage., Yale Univ. (New Haven/CT 1983)] in general, and perform better than CRGP for problems that have a low percentage of free variables at optimality, and for problems with only nonnegativity constraints.

90C20 Quadratic programming
90C25 Convex programming
90C06 Large-scale problems in mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] R.S. Dembo and U. Tulowitzski, ”On the minimization of a quadratic function subject to box constraints,” Working Paper No. 71, Series B, School of Organization and Management, Yale University (New Haven, CT, 1983).
[2] 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
[3] R.H. Nickel and J.W. Tolle, ”A sequential quadratic programming algorithm for solving large, sparse nonlinear programs,”Journal of Optimization Theory and Its Applications 60 (1989) 453–473. · Zbl 0632.90053
[4] B.T. Polyak, ”The conjugate gradient method in extremal problems,”USSR Computational Mathematics and Mathematical Physics 9 (1969) 94–112. · Zbl 0229.49023
[5] G.W. Stewart, ”The efficient generation of random orthogonal matrices with an application to condition estimators,”SIAM Journal on Numerical Analysis 17 (1980) 403–409. · Zbl 0443.65027
[6] E. Yang and J.W. Tolle, ”A class of methods for solving large, convex quadratic programs subject to box constraints,” Technical Report 86-3, Department of Operations Research, University of North Carolina (Chapel Hill, NC, 1986). · Zbl 0737.90046
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.