×

zbMATH — the first resource for mathematics

A polyhedral study of nonconvex quadratic programs with box constraints. (English) Zbl 1137.90009
Summary: 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 [ibid. 102, No. 3 (A), 559–575 (2005; Zbl 1137.90010)].

MSC:
90C20 Quadratic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[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, 171-206 (1998) · Zbl 0912.90233
[2] Balas, E.: Nonconvex quadratic programming via generalized polars. SIAM J. Appl. Math. 28, 335-349 (1975) · Zbl 0294.90066
[3] Crowder, H., Johnson, E.L., Padberg, M.W.: Solving large scale zero-one integer programming problems. Oper. Res. 31, 803-834 (1983) · Zbl 0576.90065
[4] Dang, C., Xu, L.: A barrier function method for the nonconvex quadratic programming problem with box constraints. J. Glob. Optim. 18, 165-188 (2000) · Zbl 0970.90059
[5] 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 · Zbl 0886.90130
[6] de Farias, Jr., I.R., Johnson, G.L.: Nemhauser. Facets of the complementarity knapsack polytope. Math. Oper. Res. 27, 210-226 (2002) · Zbl 1082.90586
[7] de Farias, Jr., I.R., Nemhauser, G.L.: A polyhedral study of the cardinality constrained knapsack polytope. Math. Prog. 96, 439-467 (2003) · Zbl 1023.90085
[8] Gupta, S., Pardalos, P.M.: A note on a quadratic formulation for linear complementarity problems. J. Optim. Theory Appl. 57, 197-202 (1988) · Zbl 0619.90077
[9] Hansen, P., Jaumard, B., Ruiz, M., Xiong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Nav. Res. Logist. 40, 373-392 (1993) · Zbl 0782.90071
[10] Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139-172 (1989) · Zbl 0675.90056
[11] Rosenberg, I.G.: 0-1 optimization and nonlinear programming. Rev. Françcaise Automat. Informat. Recherche Opérationnelle 6, 95-97 (1972) · Zbl 0255.90029
[12] Vandenbussche, D.: Polyhedral Approaches to Solving Nonconvex Quadratic Programs. PhD thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, 2003
[13] 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. · Zbl 1137.90010
[14] Vavasis, S.A.: Nonlinear optimization, Complexity Issues, volume 8 of Internat. Ser. Monogr. Comput. Sci. The Clarendon Press Oxford University Press, New York, 1991 · Zbl 0785.90091
[15] Yajima, Y., Fujie, T.: A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Glob. Optim. 13, 151-170 (1998) · Zbl 0912.90234
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.