zbMATH — the first resource for mathematics

Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. (English) Zbl 1445.90073
Summary: We study a class of quadratically constrained quadratic programs (QCQPs), called diagonal QCQPs, which contain no off-diagonal terms \(x_j x_k\) for \(j \ne k\), and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature and can be checked in polynomial time. We then extend our analysis from diagonal QCQPs to general QCQPs, i.e., ones with no particular structure. By reformulating a general QCQP into diagonal form, we establish new, polynomial-time-checkable sufficient conditions for the semidefinite relaxations of general QCQPs to be exact. Finally, these ideas are extended to show that a class of random general QCQPs has exact semidefinite relaxations with high probability as long as the number of constraints grows no faster than a fixed polynomial in the number of variables. To the best of our knowledge, this is the first result establishing the exactness of the semidefinite relaxation for random general QCQPs.

90C20 Quadratic programming
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
PhaseLift; SDPLR
Full Text: DOI
[1] Adler, I.; Megiddo, N., A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, J. Assoc. Comput. Mach., 32, 4, 871-895 (1985) · Zbl 0634.65044
[2] Anjos, MF; Lasserre, JB, Handbook on Semidefinite, Conic and Polynomial Optimization (2012), New York: Springer, New York
[3] Anstreicher, KM; Ji, J.; Potra, FA; Ye, Y., Probabilistic analysis of an infeasible-interior-point algorithm for linear programming, Math. Oper. Res., 24, 1, 176-192 (1999) · Zbl 0977.90019
[4] Bandeira, AS; Boumal, N.; Singer, A., Tightness of the maximum likelihood semidefinite relaxation for angular synchronization, Math. Program., 163, 1-2, 145-167 (2017) · Zbl 1365.90188
[5] Barvinok, A., Problems of distance geometry and convex properties of quadratic maps, Discrete Comput. Geom., 13, 189-202 (1995) · Zbl 0829.05025
[6] Beck, A.; Pan, D., A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Global Optim., 69, 2, 309-342 (2017) · Zbl 1382.90082
[7] Bhojanapalli, S., Boumal, N., Jain, P., Netrapalli, P.: Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. In: Proceedings of Machine Learning Research. Presented at the 31st Conference on Learning Theory, vol 75, pp. 1-28
[8] Bienstock, D., Michalka, A.: Polynomial solvability of variants of the trust-region subproblem. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 380-390 · Zbl 1428.90109
[9] Borgwardt, KH, The Simplex Method—A Probabilistic Approach (1987), New York: Springer, New York
[10] Burer, S., A gentle, geometric introduction to copositive optimization, Math. Program., 151, 1, 89-116 (2015) · Zbl 1327.90162
[11] Burer, S.; Anstreicher, KM, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23, 1, 432-451 (2013) · Zbl 1298.90062
[12] Burer, S.; Monteiro, RDC, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 2, 329-357 (2003) · Zbl 1030.90077
[13] Candès, EJ; Strohmer, T.; Voroninski, V., PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., 66, 8, 1241-1274 (2013) · Zbl 1335.94013
[14] Deza, MM; Laurent, M., Geometry of Cuts and Metrics. Algorithms and Combinatorics (1997), Berlin: Springer, Berlin
[15] Diestel, R., Graph Theory, Volume 173 of Graduate Texts in Mathematics (2018), Berlin: Springer, Berlin
[16] Fujie, T.; Kojima, M., Semidefinite programming relaxation for nonconvex quadratic programs, J. Global Optim., 10, 4, 367-380 (1997) · Zbl 0881.90101
[17] Laurent, M.; Varvitsiotis, A., A new graph parameter related to bounded rank positive semidefinite matrix completions, Math. Program., 145, 1-2, 291-325 (2014) · Zbl 1293.05238
[18] Luo, ZQ; Ma, WK; So, AMC; Ye, Y.; Zhang, S., Semidefinite relaxation of quadratic optimization problems, IEEE Signal Process. Mag., 27, 3, 20-34 (2010)
[19] Madani, R.; Fazelnia, G.; Lavaei, J., Rank-2 Matrix Solution for Semidefinite Relaxations of Arbitrary Polynomial Optimization Problems (2014), New York: Columbia University, New York
[20] Madani, R.; Sojoudi, S.; Fazelnia, G.; Lavaei, J., Finding low-rank solutions of sparse linear matrix inequalities using convex optimization, SIAM J. Optim., 27, 2, 725-758 (2017) · Zbl 1365.90185
[21] Pataki, G., On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math. Oper. Res., 23, 339-358 (1998) · Zbl 0977.90051
[22] Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[23] Shamsi, D., Taheri, N., Zhu, Z., Ye, Y.: Conditions for correct sensor network localization using SDP relaxation. In: Bezdek, K., Deza, A., Ye, Y. (eds.) Discrete Geometry and Optimization. Fields Institute Communications, vol. 69, pp. 279-301. Springer, Heidelberg (2013). 10.1007/978-3-319-00200-2_16 · Zbl 1277.90095
[24] Shor, N.:. Quadratic optimization problems. Soviet J. Comput. Syst. Sci. 25, 1-11 (1987). Originally published in Tekhnicheskaya Kibernetika 1, 128-139 (1987)
[25] Smale, S., On the average number of steps of the simplex method of linear programming, Math. Program., 27, 3, 241-262 (1983) · Zbl 0526.90060
[26] So, A.M.C.: Probabilistic analysis of the semidefinite relaxation detector in digital communications. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 698-711. SIAM, Philadelphia, PA (2010) · Zbl 1288.94005
[27] Sojoudi, S.; Lavaei, J., Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure, SIAM J. Optim., 24, 4, 1746-1778 (2014) · Zbl 1327.90221
[28] Spielman, DA; Teng, S-H, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM, 51, 3, 385-463 (2004) · Zbl 1192.90120
[29] Sturm, JF; Zhang, S., On cones of nonnegative quadratic functions, Math. Oper. Res., 28, 2, 246-267 (2003) · Zbl 1082.90086
[30] Todd, M., Semidefinite optimization, Acta Numer., 10, 515-560 (2001) · Zbl 1105.65334
[31] Todd, MJ, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems, Math. Program., 35, 2, 173-192 (1986) · Zbl 0613.90094
[32] Todd, MJ; Tunçel, L.; Ye, Y., Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems, Math. Program., 90, 1, 59-69 (2001) · Zbl 0978.90069
[33] Yang, B.; Anstreicher, K.; Burer, S., Quadratic programs with hollows, Math. Program., 170, 2, 541-553 (2018) · Zbl 1401.90147
[34] Ye, Y., Toward probabilistic analysis of interior-point algorithms for linear programming, Math. Oper. Res., 19, 1, 38-52 (1994) · Zbl 0799.90086
[35] Ye, Y., Approximating quadratic programming with bound and quadratic constraints, Math. Program., 81, 2, 219-226 (1999) · Zbl 0971.90056
[36] Ye, Y.; Zhang, S., New results on quadratic minimization, SIAM J. Optim., 14, 1, 245-267 (2003) · Zbl 1043.90064
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.