Abstract.
By reformulating quadratic programs using necessary optimality conditions, we obtain a linear program with complementarity constraints. For the case where the only constraints are bounds on the variables, we study a relaxation based on a subset of the optimality conditions. By characterizing its convex hull, we obtain a large class of valid inequalities. These inequalities are used in a branch-and-cut scheme, see [13].
Similar content being viewed by others
References
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, 171–206 (1998)
Balas, E.: Nonconvex quadratic programming via generalized polars. SIAM J. Appl. Math. 28, 335–349 (1975)
Crowder, H., Johnson, E.L., Padberg, M.W.: Solving large scale zero-one integer programming problems. Oper. Res. 31, 803–834 (1983)
Dang, C., Xu, L.: A barrier function method for the nonconvex quadratic programming problem with box constraints. J. Glob. Optim. 18, 165–188 (2000)
De Angelis, P., Pardalos, P., Toraldo, G.: Quadratic programming with box constraints. In: I.M. Bomze, T. Csendes, R. Horst, P. Pardalos (eds.), Developments in Global Optimization, Kluwer Academic Publishers, 1997, pp. 73–94
de Farias, Jr., I.R., Johnson, G.L.: Nemhauser. Facets of the complementarity knapsack polytope. Math. Oper. Res. 27, 210–226 (2002)
de Farias, Jr., I.R., Nemhauser, G.L.: A polyhedral study of the cardinality constrained knapsack polytope. Math. Prog. 96, 439–467 (2003)
Gupta, S., Pardalos, P.M.: A note on a quadratic formulation for linear complementarity problems. J. Optim. Theory Appl. 57, 197–202 (1988)
Hansen, P., Jaumard, B., Ruiz, M., **ong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Nav. Res. Logist. 40, 373–392 (1993)
Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139–172 (1989)
Rosenberg, I.G.: 0-1 optimization and nonlinear programming. Rev. Françcaise Automat. Informat. Recherche Opérationnelle 6, 95–97 (1972)
Vandenbussche, D.: Polyhedral Approaches to Solving Nonconvex Quadratic Programs. PhD thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, 2003
Vandenbussche, D., Nemhauser, G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Technical Report TLI-03-05, Georgia Institute of Technology, 2003. To appear in Math. Prog.
Vavasis, S.A.: Nonlinear optimization, Complexity Issues, volume 8 of Internat. Ser. Monogr. Comput. Sci. The Clarendon Press Oxford University Press, New York, 1991
Yajima, Y., Fujie, T.: A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Glob. Optim. 13, 151–170 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (2000): 90C26, 90C27, 90C20
Rights and permissions
About this article
Cite this article
Vandenbussche, D., Nemhauser, G. A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102, 531–557 (2005). https://doi.org/10.1007/s10107-004-0549-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-004-0549-0