Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. (English) Zbl 1170.90522

Summary: We consider a recent branch-and-bound algorithm of the authors for nonconvex quadratic programming. The algorithm is characterized by its use of semidefinite relaxations within a finite branching scheme. In this paper, we specialize the algorithm to the box-constrained case and study its implementation, which is shown to be a state-of-the-art method for globally solving box-constrained nonconvex quadratic programs.


90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut


Full Text: DOI


[1] An, L.T.H., Tao, P.D.: A branch and bound method via d.c. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems. J. Glob. Optim. 13(2), 171–206 (1998) · Zbl 0912.90233
[2] Anstreicher, K., Brixius, N., Goux, J.-P., Linderoth, J.: Solving large quadratic assignment problems on computational grids. Math. Program. 91(3, Ser. B), 563–588 (2002). ISMP 2000, Part 1 (Atlanta, GA) · Zbl 1030.90105
[3] Braun, S., Mitchell, J.E.: A semidefinite programming heuristic for quadratic programming problems with complementarity constraints. Comput. Optim. Appl. 31(1), 5–29 (2005) · Zbl 1114.90158
[4] Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3), 726–750 (2006) · Zbl 1113.90100
[5] Burer, S., Vandenbussche, D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA, USA, June 2005. Revised April 2006 and June 2006. Math. Program. (to appear) · Zbl 1135.90034
[6] De Angelis, P., Pardalos, P., Toraldo, G.: Quadratic programming with box constraints. In: Bomze, I.M., Csendes, T., Horst, R., Pardalos, P. (eds.) Developments in Global Optimization, pp. 73–94 (1997) · Zbl 0886.90130
[7] Giannessi, F., Tomasin, E.: Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: Fifth Conference on Optimization Techniques, Rome, 1973, Part I. Lecture Notes in Comput. Sci., vol. 3, pp. 437–449. Springer, Berlin (1973) · Zbl 0274.90039
[8] Gould, N.I.M., Toint, P.L.: Numerical methods for large-scale non-convex quadratic programming. In: Trends in Industrial and Applied Mathematics, Amritsar, 2001. Appl. Optim., vol. 72, pp. 149–179. Kluwer Acad., Dordrecht (2002)
[9] Hansen, P., Jaumard, B., Ruiz, M., Xiong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Naval Res. Logist. 40(3), 373–392 (1993) · Zbl 0782.90071
[10] Helmberg, C.: Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21(3), 952–969 (2000) (Electronic) · Zbl 0961.90075
[11] ILOG, Inc. ILOG CPLEX 9.0, User Manual (2003)
[12] Kozlov, M.K., Tarasov, S.P., Khachiyan, L.G.: Polynomial solvability of convex quadratic programming. Dokl. Akad. Nauk SSSR 248(5), 1049–1051 (1979) · Zbl 0434.90071
[13] Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 166–190 (1991) · Zbl 0754.90039
[14] Pardalos, P.: Global optimization algorithms for linearly constrained indefinite quadratic problems. Comput. Math. Appl. 21, 87–97 (1991) · Zbl 0733.90051
[15] Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1(1), 15–22 (1991) · Zbl 0755.90065
[16] Vandenbussche, D., Nemhauser, G.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3), 531–557 (2005) · Zbl 1137.90009
[17] Vandenbussche, D., Nemhauser, G.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3), 559–575 (2005) · Zbl 1137.90010
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.