Summary
We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barlow, R.E., Bartholomew, J.M., Brenner, J.M., Brunk, H.D.: Statistical inference under order restrictions, 1st Ed. New York: Wiley 1972
Bertsekas, D.P.: On the Goldstein-Levitin-Polyak gradient projection method. IEEE Trans. Autom. Control.21, 174–184 (1976)
Bertsekas, D.P.: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control. Optimization20, 221–246 (1982)
Björck, A.: A direct method for sparse least squares problems with lower and upper bounds. Numer. Math.54, 19–32 (1988)
Brucker, P.: AnO(n) algorithm for quadratic knapsack problems. Oper. Res. Lett.3, 163–166 (1984)
Burke, J.V., Moré, J.J.: On the identification of active constraints. SIAM J. Numer. Anal.25, 1197–1211 (1988)
Calamai, P.H., Moré, J.J.: Projected gradient methods for linearly constrained problems. Math. Programming39, 93–116 (1987a)
Calamai, P.H., Moré, J.J.: Quasi-Newton updates with bounds. SIAM J. Numer. Anal.24, 1434–1441 (1987b)
Clark, D.I., Osborne, M.R.: On linear restricted and interval least squares problems. IMA J. Numer. Anal.8, 23–36 (1988)
Cottle, R.W., Goheen, M.S.: A special class of large quadratic programs. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming 3, pp. 361–390. London: Academic Press 1978
Dembo, R.S., Tulowitzki, U.: On the minimization of quadratic functions subject to box constraints, Working Paper Series B # 71, School of Organization and Management, Yale University, New Haven 1983
Dongarra, J.J., Bunch, J.R., Moler, C.B., Stewart, G.W.: LINPACK Users Guide, SIAM Publications, Philadelphia 1979
Dunn, J.C.: Global and asymptotic convergence rate estimates for a class of projected gradient processes, SIAM J. Control Optimization19, 368–400 (1981)
Dunn, J.C.: On the convergence of projected gradient processes to singular critical points. J. Optimization Theory Appl.55, 203–216 (1987)
Glowinski, R.: Numerical methods for nonlinear variational problems. 1st Ed. Heidelberg Berlin New York: Springer 1984
Grotzinger, S.J., Witzgall, C.: Projections onto order simplexes. Appl. Math. Optimization12, 247–270 (1984)
Helgason, R., Kennington, J., Lall, H.: A polynomially bounded algorithm for a single constrained quadratic program. Math. Program. Study18, 338–343 (1980)
Lin, Y., Cryer, C.W.: An alternating direction implicit algorithm for the solution of linear complementarity problems arising from free boundary problems. J. Appl. Math. Optimization13, 1–17 (1985)
Lin, Y.Y., Pang, J.S.: Iterative methods for large convex quadratic programs: A survey. SIAM J. Control. Optimization25, 383–411 (1987)
Lötstedt, P.: Solving the minimal least squares problem subject to bounds on the variables. BIT24, 206–224 (1984)
Mangasarian, O.L.: Normal solutions of linear programs. Math. Program. Study21, 206–213 (1984)
Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Statist. Comput.4, 553–572 (1983)
O'Leary, D.P.: A generalized conjugate gradient algorithm for solving a class of quadratic programming problems. Linear Algebra Appl.34, 371–399 (1980)
Oreborn, U.: A direct method for sparse nonnegative least squares problems. Department of Mathematics, Thesis 87. Linköping University, Linköping, Sweden 1986
Yang, E.K., Tolle, J.W.: A class of methods for solving large convex quadratic programs subject to box constraints, University of North Carolina. Department of Operations Research preprint, Chapel Hill, North Carolina 1988
Author information
Authors and Affiliations
Additional information
Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38
Rights and permissions
About this article
Cite this article
Moré, J.J., Toraldo, G. Algorithms for bound constrained quadratic programming problems. Numer. Math. 55, 377–400 (1989). https://doi.org/10.1007/BF01396045
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01396045