×

A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. (English) Zbl 1135.90034

Summary: Existing global optimization techniques for nonconvex quadratic programming (QP) branch by recursively partitioning the convex feasible set and thus generate an infinite number of branch-and-bound nodes. An open question of theoretical interest is how to develop a finite branch-and-bound algorithm for nonconvex QP. One idea, which guarantees a finite number of branching decisions, is to enforce the first-order Karush-Kuhn-Tucker (KKT) conditions through branching. In addition, such an approach naturally yields linear programming (LP) relaxations at each node. However, the LP relaxations are unbounded, a fact that precludes their use. In this paper, we propose and study semidefinite programming relaxations, which are bounded and hence suitable for use with finite KKT-branching. Computational results demonstrate the practical effectiveness of the method, with a particular highlight being that only a small number of nodes are required.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

BARON; NewtonKKTqp; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Absil, P.-A., Tits, A.: Newton-KKT interior-point methods for indefinite quadratic programming. Manuscript, Department of Electrical and Computer Engineering, University of Maryland, College Park, MD, USA (2006). To appear in Computational Optimization and Applications · Zbl 1278.90288
[2] Anstreicher, K.M.: Combining RLT and SDP for nonconvex QCQP. Talk given at the Workshop on Integer Programming and Continuous Optimization, Chemnitz University of Technology, November 7–9 (2004)
[3] Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24(2), 163–185 (2002). Dedicated to Professor Naum Z. Shor on his 65th birthday · Zbl 1047.90038
[4] Burer S. and Vandenbussche D. (2006). Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3): 726–750 · Zbl 1113.90100 · doi:10.1137/040609574
[5] Floudas, C., Visweswaran, V.: Quadratic optimization. In: Horst, R., Pardalos, P. (eds.) Handbook of Global Optimization, pp. 217–269. Kluwer Academic Publishers (1995) · Zbl 0833.90091
[6] Giannessi, F., Tomasin, E.: Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: Fifth Conference on Optimization Techniques (Rome, 1973), Part I, pp. 437–449. Lecture Notes in Computer Science, vol. 3. Springer, Berlin Heidelberg New York (1973) · Zbl 0274.90039
[7] Globallib: http://www.gamsworld.org/global/globallib.htm
[8] Goemans M. and Williamson D. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42: 1115–1145 · Zbl 0885.68088 · doi:10.1145/227683.227684
[9] Gould, N.I.M., Toint, P.L.: Numerical methods for large-scale non-convex quadratic . In: Trends in Industrial and Applied Mathematics (Amritsar, 2001), vol. 72 of Appl. Optim., pp. 149–179. Kluwer Academic Publishers, Dordrecht (2002)
[10] Hansen P., Jaumard B., Ruiz M. and Xiong J. (1993). Global minimization of indefinite quadratic functions subject to box constraints. Naval Res. Logist. 40(3): 373–392 · Zbl 0782.90071 · doi:10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A
[11] ILOG, Inc.: ILOG CPLEX 9.0, User Manual (2003).
[12] Kojima M. and Tunçel L. (2000). Cones of matrices and successive convex relaxations of nonconvex sets. SIAM J. Optim. 10(3): 750–778 · Zbl 0966.90062 · doi:10.1137/S1052623498336450
[13] Kojima M. and Tunçel L. (2002). Some fundamental properties of successive convex relaxation methods on LCP and related problems. J. Global Optim. 24(3): 333–348 · Zbl 1046.90062 · doi:10.1023/A:1020300717650
[14] Kozlov M.K., Tarasov S.P. and Khachiyan L.G. (1979). Polynomial solvability of convex quadratic programming. Dokl. Akad. Nauk SSSR 248(5): 1049–1051 · Zbl 0434.90071
[15] Lootsma F.A. and Pearson J.D. (1970). An indefinite-quadratic-programming model for a continuous-production problem. Philips Res. Rep. 25: 244–254 · Zbl 0242.90020
[16] Lovász L. and Schrijver A. (1991). Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1: 166–190 · Zbl 0754.90039 · doi:10.1137/0801013
[17] Nesterov Y. (1998). Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9: 141–160 · Zbl 0904.90136 · doi:10.1080/10556789808805690
[18] Pardalos P. (1991). Global optimization algorithms for linearly constrained indefinite quadratic problems. Comput. Math. Appl. 21: 87–97 · Zbl 0733.90051 · doi:10.1016/0898-1221(91)90163-X
[19] Pardalos P.M. and Vavasis S.A. (1991). Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1): 15–22 · Zbl 0755.90065 · doi:10.1007/BF00120662
[20] Sahinidis N.V. (1996). BARON a general purpose global optimization software package. J. Glob. Optim. 8: 201–205 · Zbl 0856.90104 · doi:10.1007/BF00138693
[21] Sherali H.D. and Fraticelli B.M.P. (2002). Enhancing RLTrelaxations via a new class of semidefinite cuts. J. Global Optim. 22: 233–261 · Zbl 1045.90044 · doi:10.1023/A:1013819515732
[22] Sherali, H.D., Tuncbilek, C.H.: A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Global Optim. 2(1), 101–112 (1992) Conference on Computational Methods in Global Optimization, I (Princeton, NJ, 1991). · Zbl 0787.90088
[23] Sherali H.D. and Tuncbilek C.H. (1995). A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Global Optim. 7: 1–31 · Zbl 0844.90064 · doi:10.1007/BF01100203
[24] Skutella M. (2001). Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM 48(2): 206–242 · Zbl 1323.90024 · doi:10.1145/375827.375840
[25] Vandenbussche D. and Nemhauser G. (2005). A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3): 531–557 · Zbl 1137.90009 · doi:10.1007/s10107-004-0549-0
[26] Vandenbussche D. and Nemhauser G. (2005). A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3): 559–575 · Zbl 1137.90010 · doi:10.1007/s10107-004-0550-7
[27] Ye Y. (1999). Approximating quadratic programming with bound and quadratic constraints. Math. Program. 84(2, Ser. A): 219–226 · Zbl 0971.90056
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.