×

Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations. (English) Zbl 1254.90151

Summary: We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use rank-one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank-one matrices and the linear underestimation, we are able to construct convex relaxations that dominate Shor’s SDP relaxation and the strengthened SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization

Software:

BARON; CVX; GQTPAR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] 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
[3] Anstreicher K.M., Burer S.: D. C. versus copositive bounds for standard QP. J. Global Optim. 33, 299–312 (2005) · Zbl 1093.90033 · doi:10.1007/s10898-004-4312-0
[4] Audet C., Hansen P., Jaumard B., Savard G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Program. 87, 131–152 (2000) · Zbl 0966.90057
[5] Bertsekas D.P., Nedić A., Ozdaglar A.E.: Convex Analysis and Optimization. Athena Scientific Belmont, Mass (2003) · Zbl 1140.90001
[6] Bomze I.M.: Branch-and-bound approaches to standard quadratic optimization problems. J. Global Optim. 22, 17–37 (2002) · Zbl 1045.90042 · doi:10.1023/A:1013886408463
[7] Bomze I.M., Dür M.D., De Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Global Optim. 18, 301–320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[8] Bomze I.M., Locatelli M.: Undominated DC. decompositions of quadratic functions and applications to branch-and-bound approaches. Comput. Optim. Appl. 28, 227–245 (2004) · Zbl 1056.90112 · doi:10.1023/B:COAP.0000026886.61324.e4
[9] 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
[10] 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
[11] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming (web page and software) (2009)
[12] Kalantari B., Rosen J.B.: An algorithm for global minimization of linearly constrained concave quadratic functions. Math. Oper. Res. 12, 544–561 (1987) · Zbl 0638.90081 · doi:10.1287/moor.12.3.544
[13] Kim S., Kojima M.: Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods Softw. 15(3), 201–224 (2001) · Zbl 1109.90327 · doi:10.1080/10556780108805819
[14] Kim S., Kojima M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26, 143–154 (2003) · Zbl 1043.90060 · doi:10.1023/A:1025794313696
[15] LeThi Hoai An, Pham Dinh Tao: Solving a class of linearly constrained indefinite quadratic problems by D. C. algorithms J. Global Optim. 11, 253–285 (1997) · Zbl 0905.90131 · doi:10.1023/A:1008288411710
[16] LeThi Hoai An, Pham Dinh Tao, Le Dung Muu: A combined D. C. optimization-ellipsoidal branch-and-bound algorithm for solving nonconvex quadratic programming problems J. Comb. Optim. 2, 9–28 (1998) · Zbl 0904.90134
[17] 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
[18] 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
[19] Moré J.J., Sorensen D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572 (1983) · Zbl 0551.65042 · doi:10.1137/0904038
[20] Nesterov Y.: Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9, 141–160 (1998) · Zbl 0904.90136 · doi:10.1080/10556789808805690
[21] Pardalos P.M., Glick J.H., Rosen J.B.: Global minimization of indefinite quadratic problems. Computing 39, 281–291 (1987) · Zbl 0627.65072 · doi:10.1007/BF02239972
[22] Pardalos P.M., Rosen J.B.: Constrained Global Optimization: Algorithms and Applications. Springer, Berlin (1987) · Zbl 0638.90064
[23] Pardalos P.M., Vavasis S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1, 15–22 (1991) · Zbl 0755.90065 · doi:10.1007/BF00120662
[24] Phillips A.T., Rosen J.B.: Guaranteed {\(\epsilon\)}-approximate solution for indefinite quadratic global minimization. Naval Res. Logist. 37, 499–514 (1990) · Zbl 0708.90063 · doi:10.1002/1520-6750(199008)37:4<499::AID-NAV3220370405>3.0.CO;2-9
[25] Poljak S., Rendl F., Wolkowicz H.: A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Global Optim. 7, 51–73 (1995) · Zbl 0843.90088 · doi:10.1007/BF01100205
[26] Poljak S., Wolkowicz H.: Convex relaxations of (0-1) quadratic programming. Math. Oper. Res. 20, 550–561 (1995) · Zbl 0845.90089 · doi:10.1287/moor.20.3.550
[27] Raber U.: A simplicial branch-and-bound method for solving nonconvex all-quadratic programs. J. Global Optim. 13, 417–432 (1998) · Zbl 0916.90215 · doi:10.1023/A:1008377529330
[28] Ramana, M.: An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems. PhD thesis, The Johns Hopkins University, Baltimore (1993)
[29] Rosen J.B., Pardalos P.M.: Global minimization of large-scale constrained concave quadratic problems by separable programming. Math. Program. 34, 163–174 (1986) · Zbl 0597.90066 · doi:10.1007/BF01580581
[30] Sahinidis N.V.: BARON: a general purpose global optimization software package. J. Global Optim. 8, 201–205 (1996) · Zbl 0856.90104 · doi:10.1007/BF00138693
[31] Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations. Technical Report RC24695 (W0811-090), IBM, Yorktown Heights, NY (2008) · Zbl 1229.90144
[32] Sherali H.D., Adams W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1999) · Zbl 0926.90078
[33] Sherali H.D., Fraticelli B.M.P.: Enhancing rlt relaxations via a new class of semidefinite cuts. J. Global Optim. 22, 233–261 (2002) · Zbl 1045.90044 · doi:10.1023/A:1013819515732
[34] Shor N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1–11 (1987) · Zbl 0655.90055
[35] Tawarmalani M., Sahinidis N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Program. 99, 563–591 (2004) · Zbl 1062.90041 · doi:10.1007/s10107-003-0467-6
[36] Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[37] Ye Y.: Approximating global quadratic optimization with convex quadratic constraints. J. Global Optim. 15, 1–17 (1999) · Zbl 0953.90040 · doi:10.1023/A:1008370723217
[38] Zhang S.: Quadratic maximization and semidefinite relaxation. Math. Program. 87, 453–465 (2000) · Zbl 1009.90080 · doi:10.1007/s101070050006
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.