×

Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. (English) Zbl 1232.49035

Summary: At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for Quadratically Constrained Quadratic Programming (QCQP) can be formulated as SemiDefinite Programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is equivalent to the Shor relaxation, when the latter is enhanced with a partial first-order relaxation-linearization technique. These two relaxations are shown to theoretically dominate six other SDP relaxations. A computational comparison reveals that the two dominant relaxations require three orders of magnitude more computational time than the weaker relaxations, while providing relaxation gaps averaging 3% as opposed to gaps of up to 19% for weaker relaxations, on 700 randomly generated problems with up to 60 variables. An SDP relaxation derived from Lagrangian relaxation, after the addition of redundant nonlinear constraints to the primal, achieves gaps averaging 13% in a few CPU seconds.

MSC:

49M29 Numerical methods involving duality
65K05 Numerical mathematical programming methods
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adhya N., Tawarmalani M., Sahinidis N.V.: A Lagrangian approach to the pooling problem. Ind. Eng. Chem. 38, 1956–1972 (1999) · doi:10.1021/ie980666q
[2] Al-Khayyal F.A.: Generalized bilinear programming: Part I. Models, applications and linear programming relaxation. Eur. J. Oper. Res. 60, 306–314 (1992) · Zbl 0784.90051 · doi:10.1016/0377-2217(92)90082-K
[3] Al-Khayyal F.A., Falk J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8, 273–286 (1983) · Zbl 0521.90087 · doi:10.1287/moor.8.2.273
[4] Al-Khayyal F.A., Larsen C., Van Voorhis T.: A relaxation method for nonconvex quadratically constrained quadratic programs. J. Global Optim. 6, 215–230 (1995) · Zbl 0835.90060 · doi:10.1007/BF01099462
[5] Anstreicher, K., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. http://www.dollar.biz.uiowa.edu/\(\sim\)sburer/papers/023-qphull.pdf (2007) · Zbl 1198.90311
[6] Anstreicher K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Global Optim. 43, 471–484 (2009) · Zbl 1169.90425 · doi:10.1007/s10898-008-9372-0
[7] Anstreicher K.M., Burer S.: DC versus copositive bounds for standard QP. J. Global Optim. 33(2), 299–312 (2005) · Zbl 1093.90033 · doi:10.1007/s10898-004-4312-0
[8] Bao X., Sahinidis N.V., Tawarmalani M.: Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optim. Methods Softw. 24, 485–504 (2009) · Zbl 1179.90252 · doi:10.1080/10556780902883184
[9] Ben-Tal, A., Nemirovski, A.S.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2001) · Zbl 0986.90032
[10] Benson, S.J., Ye, Y.: DSDP5: Software for semidefinite programming. Tech. Rep. ANL/MCS-P1289-0905, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL. ACM Trans. Math. Softw. http://www.mcs.anl.gov/\(\sim\)benson/dsdp (submitted, 2005) · Zbl 1291.65173
[11] Bomze I.M., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24, 163–185 (2002) · Zbl 1047.90038 · doi:10.1023/A:1020209017701
[12] Bomze I.M., Dur M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Global Optim. 18(4), 301–320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[13] Bomze I.M., Frommlet F., Rubey M.: Improved SDP bounds for minimizing quadratic functions over the l(1)-ball. Optim. Lett. 1(1), 49–59 (2007) · Zbl 1135.90377 · doi:10.1007/s11590-006-0018-1
[14] Bomze I.M., Locatelli M., Tardella F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115(1), 31–64 (2008) · Zbl 1171.90007 · doi:10.1007/s10107-007-0138-0
[15] Borchers B.: CSDP, A C library for semidefinite programming. Optim. Methods Softw. 11, 613–623 (1999) · Zbl 0973.90524 · doi:10.1080/10556789908805765
[16] Brooke A., Kendrick D., Meeraus A.: GAMS–A User’s Guide. The Scientific Press, Redwood City, CA (1988)
[17] Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Tech. rep., University of Iowa, Iowa City, IA. http://www.optimization-online.org/DB_FILE/2009/01/2184.pdf (2008)
[18] Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 295–479 (2009) · Zbl 1180.90234
[19] Burer, S., Chen, J.: Relaxing the optimality conditions of box QP. Tech. rep., Dept. of Management Sciences, University of Iowa, Iowa City, IA 52240. Available at http://www.optimization-online.org/DB_FILE/2007/10/1815.pdf (2007)
[20] Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 112, 259–282 (2008) · Zbl 1135.90034 · doi:10.1007/s10107-006-0080-6
[21] Dorneich M.C., Sahinidis N.V.: Global optimization algorithms for chip layout and compaction. Eng. Optim. 25, 131–154 (1995) · doi:10.1080/03052159508941259
[22] Fujie T., Kojima M.: Semidefinite programming relaxation for nonconvex quadratic programs. J. Global Optim. 10, 367–380 (1997) · Zbl 0881.90101 · doi:10.1023/A:1008282830093
[23] Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684
[24] Hao E.P.: Quadratically constrained quadratic programming: some applications and a method for solution. Math. Methods Oper. Res. 26, 105–119 (1982) · Zbl 0479.90065 · doi:10.1007/BF01917102
[25] Linderoth J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 103, 251–282 (2005) · Zbl 1099.90039 · doi:10.1007/s10107-005-0582-7
[26] Liu M.L., Sahinidis N.V.: Process planning in a fuzzy environment. Eur. J. Oper. Res. 100, 142–169 (1997) · Zbl 0947.90608 · doi:10.1016/S0377-2217(96)00025-2
[27] Locatelli M., Raber U.: Packing equal circles in a square: a deterministic global optimization approach. Discret. Appl. Math. 122, 139–166 (2002) · Zbl 1019.90033 · doi:10.1016/S0166-218X(01)00359-6
[28] McCormick G.P.: Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems. Math. Program. 10, 147–175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665
[29] Mittelmann H.D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95, 407–430 (2003) · Zbl 1030.90080 · doi:10.1007/s10107-002-0355-5
[30] Nowak I.: A new semidefinite programming bound for indefinite quadratic forms over a simplex. J. Global Optim. 14, 357–364 (1999) · Zbl 0959.65077 · doi:10.1023/A:1008315627883
[31] Pólik I., Terlaky T.: A survey of the S-Lemma. SIAM Rev. 49, 371–418 (2007) · Zbl 1128.90046 · doi:10.1137/S003614450444614X
[32] Poljak S., Rendl F., Wolkowicz H.: A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Global Optim. 7(1), 51–73 (1995) · Zbl 0843.90088 · doi:10.1007/BF01100205
[33] Quist A.J., de Klerk E., Roos C., Terlaky T.: Copositive relaxations for general quadratic programming. Optim. Methods Softw. 9, 185–208 (1998) · Zbl 0904.90126 · doi:10.1080/10556789808805692
[34] Rikun A.D.: A convex envelope formula for multilinear functions. J. Global Optim. 10, 425–437 (1997) · Zbl 0881.90099 · doi:10.1023/A:1008217604285
[35] Rockafellar R.T.: Convex Analysis Princeton. Mathematical Series. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[36] Sherali H.D.: Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Mathematica Vietnamica 22, 245–270 (1997) · Zbl 0914.90205
[37] Sherali H.D.: RLT: a unified approach for discrete and continuous nonconvex optimization. Ann. Oper. Res. 149(1), 185–193 (2007) · Zbl 1213.90029 · doi:10.1007/s10479-006-0107-7
[38] Shor N.Z.: Quadratic optimization problems. Soviet J. Comput. Syst. Sci. 25, 1–11 (1987) · Zbl 0655.90055
[39] Shor N.Z.: Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25, 163–168 (1990) · Zbl 0783.90081 · doi:10.1007/BF02283692
[40] Shor N.Z.: Dual estimates in multiextremal problems. J. Global Optim. 2, 411–418 (1992) · Zbl 0765.90072 · doi:10.1007/BF00122430
[41] Sutou A., Dai Y.: Global optimization approach to unequal sphere packing problems in 3D. J. Optim. Theory Appl. 114, 671–694 (2002) · Zbl 1026.90078 · doi:10.1023/A:1016083231326
[42] Tawarmalani M., Sahinidis N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225–249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[43] Van Voorhis T.: A global optimization algorithm using lagrangian underestimates and the interval Newton method. J. Global Optim. 24, 349–370 (2002) · Zbl 1046.90067 · doi:10.1023/A:1020383700229
[44] Vavasis S.A.: Quadratic programming is in NP. Inf. Process. Lett. 36, 73–77 (1990) · Zbl 0719.90052 · doi:10.1016/0020-0190(90)90100-C
[45] Wolkowicz, H.: Semidefinite and lagrangian relaxations for hard combinatorial problems. In: Proceedings of the 19th IFIP TC7 Conference on System Modelling and Optimization, pp. 269–310. Kluwer, B.V., Deventer, The Netherlands (2000) · Zbl 0999.90031
[46] Wolkowicz H.: A note on lack of strong duality for quadratic problems with orthogonal constraints. Eur. J. Oper. Res. 143(2), 356–364 (2002) · Zbl 1058.90046 · doi:10.1016/S0377-2217(02)00295-3
[47] Wolkowicz H., Anjos M.F.: Semidefinite programming for discrete optimization and matrix completion problems. Discret. Appl. Math. 123(1–3), 513–577 (2002) · Zbl 1060.90059 · doi:10.1016/S0166-218X(01)00352-3
[48] Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. Theory, Algorithms, and Applications. Kluwer (2000) · Zbl 0951.90001
[49] Xie W., Sahinidis N.V.: A branch-and-bound algorithm for the continuous facility layout problem. Comput. Chem. Eng. 32, 1016–1028 (2008) · doi:10.1016/j.compchemeng.2007.05.003
[50] Yamashita M., Fujisawa K., Kojima M.: Implementation and evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0). Optim. Methods Softw. 18, 491–505 (2003) · Zbl 1106.90366 · doi:10.1080/1055678031000118482
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.