×

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation. (English) Zbl 1236.90089

Authors’ abstract: “We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0-1 constraints.”

MSC:

90C20 Quadratic programming
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization

Software:

CVX; BARON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] Al-Khayyal F.A., Larsen C., Van Voorhis T.: A relaxation method for nonconvex quadratically constrained quadratic programs. J. Glob. Optim. 6, 215–230 (1995) · Zbl 0835.90060 · doi:10.1007/BF01099462
[3] An L.T.H., Tao P.D.: Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms. J. Glob. Optim. 11, 253–285 (1997) · Zbl 0905.90131 · doi:10.1023/A:1008288411710
[4] Anstreicher K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43, 471–484 (2009) · Zbl 1169.90425 · doi:10.1007/s10898-008-9372-0
[5] Anstreicher, K.M.: On Convex Relaxations for Quadratically Constrained Quadratic Programming. Tech. rep., Department of Management Sciences, University of Iowa (2010). Avaialable at http://www.optimization-online.org/DB_FILE/2010/08/2699.pdf
[6] Anstreicher K.M., Burer S.: D.C. versus copositive bounds for standard QP. J. Glob. Optim. 33, 299–312 (2005) · Zbl 1093.90033 · doi:10.1007/s10898-004-4312-0
[7] Anstreicher K.M., Wolkowicz H.: On Lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22, 41 (2000) · Zbl 0990.90088 · doi:10.1137/S0895479898340299
[8] 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
[9] Beck A., Eldar Y.C.: Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM J. Optim. 17, 844–860 (2007) · Zbl 1128.90044 · doi:10.1137/050644471
[10] Ben-Tal, A.: Conic and Robust Optimization. Lecture Notes, Universita di Roma La Sapienzia, Rome, Italy (2002). Available at http://ie.technion.ac.il/Home/Users/morbt/rom.pdf · Zbl 1007.90047
[11] Bertsekas D.P., Nedić A., Ozdaglar A.E.: Convex Analysis and Optimization. Athena Scientific Belmont, Massachusetts (2003) · Zbl 1140.90001
[12] Bomze I.M., Dür M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[13] Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z
[14] Burer, S., Saxena, A.: Old Wine in New Bottle: The MILP Road to MIQCP. Tech. rep., Department of Management Sciences, University of Iowa (2009). Available at http://www.optimization-online.org/DB_FILE/2009/07/2338.pdf
[15] Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113, 259–282 (2008) · Zbl 1135.90034 · doi:10.1007/s10107-006-0080-6
[16] Fu M., Luo Z.Q., Ye Y.: Approximation algorithms for quadratic programming. J. Comb. Optim. 2, 29–50 (1998) · Zbl 0896.90154 · doi:10.1023/A:1009739827008
[17] Fujie T., Kojima M.: Semidefinite programming relaxation for nonconvex quadratic programs. J. Glob. Optim. 10, 367–380 (1997) · Zbl 0881.90101 · doi:10.1023/A:1008282830093
[18] 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
[19] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1. 21 (2011). http://cvxr.com/cvx
[20] Horn R.A., Johnson C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001
[21] Kellerer H., Pferschy U., Pisinger D.: Knapsack Problems. Springer, Berlin (2004) · Zbl 1103.90003
[22] 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
[23] de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[24] de Klerk E., Pasechnik D.V.: A linear programming reformulation of the standard quadratic optimization problem. J. Glob. Optim. 37, 75–84 (2007) · Zbl 1127.90051
[25] Kojima M., Tunçel L.: Cones of matrices and successive convex relaxations of nonconvex sets. SIAM J. Optim. 10, 750–778 (2000) · Zbl 0966.90062 · doi:10.1137/S1052623498336450
[26] 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
[27] 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
[28] Nesterov Y.: Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9, 141–160 (1998) · Zbl 0904.90136 · doi:10.1080/10556789808805690
[29] Nesterov Y., Nemirovsky A.: Interior-Point Polynomial Methods in Convex Programming. SIAM, Philadelphia (1994)
[30] Nesterov Y., Todd M.J., Ye Y.: Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems. Math. Program. 84, 227–267 (1999) · Zbl 0971.90061
[31] Parrilo, P.A.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.D. thesis, California Institute of Technology (2000)
[32] Povh J., Rendl F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18, 223–241 (2007) · Zbl 1143.90025 · doi:10.1137/050637467
[33] Povh J., Rendl F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6, 231–241 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002
[34] Raber U.: A simplicial branch-and-bound method for solving nonconvex all-quadratic programs. J. Glob. Optim. 13, 417–432 (1998) · Zbl 0916.90215 · doi:10.1023/A:1008377529330
[35] Sahinidis N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996) · Zbl 0856.90104 · doi:10.1007/BF00138693
[36] Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations. Math. Program. (2011). doi: 10.1007/s10107-010-0340-3 · Zbl 1229.90144
[37] Sherali H.D.: Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Math. Vietnamica 22, 245–270 (1997) · Zbl 0914.90205
[38] Sherali H.D., Adams W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1999) · Zbl 0926.90078
[39] Sherali H.D., Tuncbilek C.H.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim. 7, 1–31 (1995) · Zbl 0844.90064 · doi:10.1007/BF01100203
[40] Sturm J.F., Zhang S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28, 246–267 (2003) · Zbl 1082.90086 · doi:10.1287/moor.28.2.246.14485
[41] Tseng P.: Further results on approximating nonconvex quadratic optimization by semidefinite programming relaxation. SIAM J. Optim. 14, 268 (2003) · Zbl 1075.90061 · doi:10.1137/S1052623401395899
[42] Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[43] Vanderbussche D., Nemhauser G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102, 371–405 (2005) · Zbl 1079.90080 · doi:10.1007/s10107-004-0531-x
[44] Ye Y.: Approximating global quadratic optimization with convex quadratic constraints. J. Glob. Optim. 15, 1–17 (1999) · Zbl 0953.90040 · doi:10.1023/A:1008370723217
[45] Ye Y.: Approximating quadratic programming with bound and quadratic constraints. Math. Program. 84, 219–226 (1999) · Zbl 0971.90056
[46] Ye Y., Zhang S.: New results on quadratic minimization. SIAM J. Optim. 14, 245–267 (2004) · Zbl 1043.90064 · doi:10.1137/S105262340139001X
[47] Zhang S.: Quadratic maximization and semidefinite relaxation. Math. Program. 87, 453–465 (2000) · Zbl 1009.90080 · doi:10.1007/s101070050006
[48] Zheng, X.J., Sun, X.L., Li, D.: Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations. J. Glob. Optim. (2011). doi: 10.1007/s10898-010-9630-9 · Zbl 1254.90151
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.