Penalized semidefinite programming for quadratically-constrained quadratic optimization. (English) Zbl 1462.65068
Summary: In this paper, we give a new penalized semidefinite programming approach for non-convex quadratically-constrained quadratic programs (QCQPs). We incorporate penalty terms into the objective of convex relaxations in order to retrieve feasible and near-optimal solutions for non-convex QCQPs. We introduce a generalized linear independence constraint qualification (GLICQ) criterion and prove that any GLICQ regular point that is sufficiently close to the feasible set can be used to construct an appropriate penalty term and recover a feasible solution. Inspired by these results, we develop a heuristic sequential procedure that preserves feasibility and aims to improve the objective value at each iteration. Numerical experiments on large-scale system identification problems as well as benchmark instances from the library of quadratic programming demonstrate the ability of the proposed penalized semidefinite programs in finding near-optimal solutions for non-convex QCQP.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C26 | Nonconvex programming, global optimization |
| 90C22 | Semidefinite programming |
Keywords:
semidefinite programming; non-convex optimization; nonlinear programming; convex relaxationReferences:
| [1] | Ahmadi, AA; Majumdar, A., DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization, SIAM J. Appl. Algebr. Geom., 3, 2, 193-230 (2019) · Zbl 1465.90061 |
| [2] | Aittomaki, T., Koivunen, V.: Beam pattern optimization by minimization of quartic polynomial. In: 2009 IEEE/SP 15th Workshop on Statistical Signal Processing, pp. 437-440. IEEE (2009) |
| [3] | Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Program., 95, 1, 3-51 (2003) · Zbl 1153.90522 |
| [4] | ApS M: The MOSEK optimization toolbox for MATLAB manual. Version 8.1. http://docs.mosek.com/8.1/toolbox/index.html (2017) |
| [5] | Ashraphijuo, M., Madani, R., Lavaei, J.: Characterization of rank-constrained feasibility problems via a finite number of convex programs. In: 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 6544-6550. IEEE(2016) |
| [6] | Atamtürk, A.; Narayanan, V.; Fischetti, M.; Williamson, DP, Cuts for conic mixed-integer programming, Integer Programming and Combinatorial Optimization, 16-29 (2007), Heidelberg: Springer, Heidelberg · Zbl 1136.90518 |
| [7] | Aubry, A.; De Maio, A.; Jiang, B.; Zhang, S., Ambiguity function shaping for cognitive radar via complex quartic optimization, IEEE Trans. Signal Process., 61, 22, 5603-5619 (2013) · Zbl 1393.94165 |
| [8] | Bandeira, A.S., Boumal, N., Singer, A.: Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. arXiv preprint arXiv:1411.3272 (2014) · Zbl 1365.90188 |
| [9] | Bao, X.; Sahinidis, NV; Tawarmalani, M., Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons, Math. Program., 129, 129-157 (2011) · Zbl 1232.49035 |
| [10] | Belotti, P., COUENNE: A user’s manual (2013), Tech. rep.: Technical report, Lehigh University, Tech. rep. |
| [11] | Bienstock, D.; Munoz, G., LP formulations for polynomial optimization problems, SIAM J. Optim., 28, 2, 1121-1150 (2018) · Zbl 1395.80005 |
| [12] | Burer, S.; Vandenbussche, D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Math. Program., 113, 2, 259-282 (2008) · Zbl 1135.90034 |
| [13] | Burer, S., Ye, Y.: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. arXiv preprint arXiv:1802.02688 (2018) · Zbl 1445.90073 |
| [14] | Burgdorf, S., Laurent, M., Piovesan, T.: On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. arXiv preprint arXiv:1502.02842 (2015) · Zbl 1372.81026 |
| [15] | Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124 |
| [16] | Candes, 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 |
| [17] | Candes, EJ; Eldar, YC; Strohmer, T.; Voroninski, V., Phase retrieval via matrix completion, SIAM Rev., 57, 2, 225-251 (2015) · Zbl 1344.49057 |
| [18] | Chen, C.; Atamtürk, A.; Oren, SS, A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables, Math. Program., 165, 2, 549-577 (2017) · Zbl 1380.65102 |
| [19] | Chen, CY; Vaidyanathan, P., Mimo radar waveform optimization with prior information of the extended target and clutter, IEEE Trans. Signal Process., 57, 9, 3533-3544 (2009) · Zbl 1391.94666 |
| [20] | Chen, J.; Burer, S., Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4, 1, 33-52 (2012) · Zbl 1257.90065 |
| [21] | Cid, C., Murphy, S., Robshaw, M.: Computational and algebraic aspects of the advanced encryption standard. In: Proceedings of the Seventh International Workshop on Computer Algebra in Scientific Computing-CASC, vol. 2004 (2004) · Zbl 1130.68047 |
| [22] | Cid, C., Murphy, S., Robshaw, M.J. (2005) Small scale variants of the AES. In: International Workshop on Fast Software Encryption, pp. 145-162. Springer · Zbl 1140.94330 |
| [23] | Courtois, N.T., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 267-287. Springer (2002) · Zbl 1065.94543 |
| [24] | Deza, M.; Laurent, M., Applications of cut polyhedra-ii, J. Comput. Appl. Math., 55, 2, 217-247 (1994) · Zbl 0826.52013 |
| [25] | Fattahi, S., Sojoudi, S.: Data-driven sparse system identification. In: 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE (2018) |
| [26] | Fattahi, S.; Fazelnia, G.; Lavaei, J.; Arcak, M., Transformation of optimal centralized controllers into near-globally optimal static distributed controllers, IEEE Trans. Autom. Control, 64, 1, 66-80 (2018) · Zbl 1423.93415 |
| [27] | Fazelnia, G.; Madani, R.; Kalbat, A.; Lavaei, J., Convex relaxation for optimal distributed control problems, IEEE Trans. Autom. Control, 62, 1, 206-221 (2017) · Zbl 1359.90087 |
| [28] | Fogel, F., Waldspurger, I., dAspremont, A.: Phase retrieval for imaging problems. In: Mathematical Programming Computation, pp. 1-25 (2013) |
| [29] | Furini, F.; Traversi, E.; Belotti, P.; Frangioni, A.; Gleixner, A.; Gould, N.; Liberti, L.; Lodi, A.; Misener, R.; Mittelmann, H.; Sahinidis, N.; Vigerske, S.; Wiegele, A., QPLIB: a library of quadratic programming instances, Math. Program. Comput., 11, 237-310 (2019) · Zbl 1435.90099 |
| [30] | GAMS Development Corporation: General Algebraic Modeling System (GAMS) Release 24.2.1. Washington, DC, USA, http://www.gams.com/ (2013) |
| [31] | Gershman, AB; Sidiropoulos, ND; Shahbazpanahi, S.; Bengtsson, M.; Ottersten, B., Convex optimization-based beamforming: from receive to transmit and network designs, IEEE Signal Process. Mag., 27, 3, 62-75 (2010) |
| [32] | Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM (JACM), 42, 6, 1115-1145 (1995) · Zbl 0885.68088 |
| [33] | He, S.; Luo, Z.; Nie, J.; Zhang, S., Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization, SIAM J. Optim., 19, 503-523 (2008) · Zbl 1180.90218 |
| [34] | He, S.; Li, Z.; Zhang, S., Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Math. Program., 125, 353-383 (2010) · Zbl 1206.90124 |
| [35] | Hilling, JJ; Sudbery, A., The geometric measure of multipartite entanglement and the singular values of a hypermatrix, J. Math. Phys., 51, 7, 072102 (2010) · Zbl 1311.81026 |
| [36] | Ibaraki, S., Tomizuka, M.: Rank minimization approach for solving BMI problems with random search. In: Proceedings of the 2001 American Control Conference. (Cat. No. 01CH37148), vol. 3, pp. 1870-1875. IEEE (2001) |
| [37] | Josz, C.; Molzahn, DK, Lasserre hierarchy for large scale polynomial optimization in real and complex variables, SIAM J. Optim., 28, 2, 1017-1048 (2018) · Zbl 1395.90196 |
| [38] | Kheirandishfard, M., Zohrizadeh, F., Adil, M., Madani, R. (2018a). Convex relaxation of bilinear matrix inequalities part II: applications to optimal control synthesis. In: IEEE 57th Annual Conference on Decision and Control (CDC) |
| [39] | Kheirandishfard, M., Zohrizadeh, F., Adil, M., Madani, R.: Convex relaxation of bilinear matrix inequalities part ii: applications to optimal control synthesis. In: 2018 IEEE Conference on Decision and Control (CDC), pp. 75-82. IEEE (2018b) |
| [40] | Kheirandishfard, M., Zohrizadeh, F., Madani, R.: Convex relaxation of bilinear matrix inequalities part I: theoretical results. In: IEEE 57th Annual Conference on Decision and Control (CDC) (2018c) |
| [41] | Kim, S.; Kojima, M., Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations, Comput. Optim. Appl., 26, 2, 143-154 (2003) · Zbl 1043.90060 |
| [42] | Kim, S.; Kojima, M.; Yamashita, M., Second order cone programming relaxation of a positive semidefinite constraint, Optim. Methods Softw., 18, 535-541 (2003) · Zbl 1142.90466 |
| [43] | Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Integer Programming and Combinatorial Optimization, pp. 293-303. Springer (2001a) · Zbl 1010.90515 |
| [44] | Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817 (2001) · Zbl 1010.90061 |
| [45] | Lasserre, JB, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17, 822-843 (2006) · Zbl 1119.90036 |
| [46] | Laurent, M.; Piovesan, T., Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone, SIAM J. Optim., 25, 4, 2461-2493 (2015) · Zbl 1329.15066 |
| [47] | Li, Z.; He, S.; Zhang, S., Approximation Methods for Polynomial Optimization: Models, Algorithms, and Applications (2012), Berlin: Springer, Berlin · Zbl 1298.90003 |
| [48] | Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 2, 166-190 (1991) · Zbl 0754.90039 |
| [49] | Luo, Z.; Sidiropoulos, N.; Tseng, P.; Zhang, S., Approximation bounds for quadratic optimization with homogeneous quadratic constraints, SIAM J. Optim., 18, 1-28 (2007) · Zbl 1156.90011 |
| [50] | Luo, ZQ; Wk, Ma; So, AMC; Ye, Y.; Zhang, S., Semidefinite relaxation of quadratic optimization problems, IEEE Signal Process. Mag., 27, 3, 20 (2010) |
| [51] | Madani, R., Fazelnia, G., Lavaei, J.: Rank-2 matrix solution for semidefinite relaxations of arbitrary polynomial optimization problems. Preprint (2014) |
| [52] | Madani, R., Lavaei, J., Baldick, R.: Convexification of power flow problem over arbitrary networks. In: 2015 54th IEEE Conference on Decision and Control (CDC), pp. 1-8. IEEE (2015a) |
| [53] | Madani, R.; Sojoudi, S.; Lavaei, J., Convex relaxation for optimal power flow problem: Mesh networks, IEEE Trans. Power Syst., 30, 1, 199-211 (2015) |
| [54] | Madani, R.; Ashraphijuo, M.; Lavaei, J., Promises of conic relaxation for contingency-constrained optimal power flow problem, IEEE Trans. Power Syst., 31, 2, 1297-1307 (2016) |
| [55] | Madani, R., Atamtürk, A., Davoudi, A.: A scalable semidefinite relaxation approach to grid scheduling. arXiv preprint arXiv:1707.03541 (2017a) |
| [56] | 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 |
| [57] | Majumdar, A., Ahmadi, A.A., Tedrake, R.: Control and verification of high-dimensional systems with DSOS and SDSOS programming. In: 2014 IEEE 53rd Annual Conference on Decision and Control (CDC), pp. 394-401. IEEE (2014) |
| [58] | Mariere, B.; Luo, ZQ; Davidson, TN, Blind constant modulus equalization via convex optimization, IEEE Trans. Signal Process., 51, 3, 805-818 (2003) · Zbl 1369.94396 |
| [59] | Mohammad-Nezhad, A.; Terlaky, T., A rounding procedure for semidefinite optimization, Oper. Res. Lett., 47, 1, 59-65 (2019) · Zbl 1476.90234 |
| [60] | Mu, C.; Zhang, Y.; Wright, J.; Goldfarb, D., Scalable robust matrix recovery: Frank-Wolfe meets proximal methods, SIAM J. Sci. Comput., 38, 5, A3291-A3317 (2016) · Zbl 1348.90465 |
| [61] | Muramatsu, M.; Suzuki, T., A new second-order cone programming relaxation for max-cut problems, J. Oper. Res. Soc. Jpn., 46, 164-177 (2003) · Zbl 1109.90337 |
| [62] | Murphy, S., Robshaw, M.J.: Essential algebraic structure within the AES. In: Annual International Cryptology Conference, pp. 1-16. Springer (2002) · Zbl 1026.94537 |
| [63] | Natarajan. K., Shi, D., Toh, K.C.: A penalized quadratic convex reformulation method for random quadratic unconstrained binary optimization. Optimization Online (2013) |
| [64] | Nesterov, Y., Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw., 9, 141-160 (1998) · Zbl 0904.90136 |
| [65] | Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming (Vol. 13). SIAM (1994) · Zbl 0824.90112 |
| [66] | Papp, D.; Alizadeh, F., Semidefinite characterization of sum-of-squares cones in algebras, SIAM J. Optim., 23, 3, 1398-1423 (2013) · Zbl 1304.90156 |
| [67] | Pereira, J., Ibrahimi, M., Montanari, A.: Learning networks of stochastic differential equations. In: Advances in Neural Information Processing Systems, pp. 172-180 (2010) |
| [68] | Permenter, F., Parrilo, P.: Partial facial reduction: simplified, equivalent SDPS via approximations of the psd cone. Mathematical Programming, pp. 1-54 (2014) · Zbl 1405.90098 |
| [69] | Rotkowitz, M.; Lall, S., A characterization of convex problems in decentralized control, IEEE Trans. Autom. Control, 50, 12, 1984-1996 (2005) · Zbl 1365.93020 |
| [70] | Sarkar, T., Rakhlin, A.: How fast can linear dynamical systems be learned? arXiv preprint arXiv:1812.01251 (2018) |
| [71] | Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 3, 411-430 (1990) · Zbl 0712.90050 |
| [72] | Sherali, H.D., Adams, W.P.: A reformulation-linearization technique for solving discrete and continuous nonconvex problems, vol. 31. Springer, Berlin (2013) · Zbl 0926.90078 |
| [73] | Singer, A., Angular synchronization by eigenvectors and semidefinite programming, Appl. Comput. Harmonic Anal., 30, 1, 20-36 (2011) · Zbl 1206.90116 |
| [74] | Sojoudi, S., Lavaei, J.: On the exactness of semidefinite relaxation for nonlinear optimization over graphs: Part I. In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC), pp. 1043-1050. IEEE (2013a) |
| [75] | Sojoudi, S., Lavaei, J.: On the exactness of semidefinite relaxation for nonlinear optimization over graphs: part II. In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC), pp. 1043-1050. IEEE (2013b) |
| [76] | Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047 |
| [77] | Toker, O.; Ozbay, H., On the complexity of purely complex \(\mu\) computation and related problems in multidimensional systems, IEEE Trans. Autom. Control, 43, 3, 409-414 (1998) · Zbl 0905.93018 |
| [78] | Wang, YS; Matni, N.; Doyle, JC, Separable and localized system-level synthesis for large-scale systems, IEEE Trans. Autom. Control, 63, 12, 4234-4249 (2018) · Zbl 1423.93124 |
| [79] | Wang, YS; Matni, N.; Doyle, JC, A system-level approach to controller synthesis, IEEE Trans. Autom. Control, 64, 10, 4079-4093 (2019) · Zbl 1482.93194 · doi:10.1109/TAC.2018.2890753 |
| [80] | Ye, Y., Approximating global quadratic optimization with convex quadratic constraints, J. Global Optim., 15, 1-17 (1999) · Zbl 0953.90040 |
| [81] | Ye, Y., Approximating quadratic programming with bound and quadratic constraints, Math. Program., 84, 219-226 (1999) · Zbl 0971.90056 |
| [82] | Zhang, S., Quadratic maximization and semidefinite relaxation, Math. Program., 87, 453-465 (2000) · Zbl 1009.90080 |
| [83] | Zhang, S.; Huang, Y., Complex quadratic optimization and semidefinite programming, SIAM J. Optim., 87, 871-890 (2006) · Zbl 1113.90115 |
| [84] | Zohrizadeh, F., Kheirandishfard, M., Nasir, A., Madani, R.: Sequential relaxation of unit commitment with AC transmission constraints. In: IEEE 57th Annual Conference on Decision and Control (CDC) (2018a) |
| [85] | Zohrizadeh, F., Kheirandishfard, M., Quarm, E., Madani, R.: Penalized parabolic relaxation for optimal power flow problem. In: IEEE 57th Annual Conference on Decision and Control (CDC) (2018b) |
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.
