×

A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables. (English) Zbl 1380.65102

The authors develop a spatial branch-and-cut approach for nonconvex quadratically constrained quadratic programs with bounded complex variables. Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations. The authors apply the algorithm to solve the alternating current optimal power flow problem with complex variables as well as the box-constrained quadratic programming problem with real variables. Computational results are given.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C22 Semidefinite programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33, 42-54 (2005) · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002
[2] Andersen, E.D., Andersen, K.D.: The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. High Perform. Optim. 33, 197-232 (2000) · Zbl 1028.90022
[3] 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
[4] Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33-43 (2010) · Zbl 1198.90311 · doi:10.1007/s10107-010-0355-9
[5] Bai, X., Wei, H.: A semidefinite programming method with graph partitioning technique for optimal power flow problems. Int. J. Electr. Power Energy Syst. 33, 1309-1314 (2011) · doi:10.1016/j.ijepes.2011.06.003
[6] Bai, X., Wei, H., Fujisawa, K., Wang, Y.: Semidefinite programming for optimal power flow problems. Int. J. Electr. Power Energy Syst. 30, 383-392 (2008) · doi:10.1016/j.ijepes.2007.12.003
[7] 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
[8] Beck, A., Eldar, Y.C.: Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM J. Optim. 17, 844-860 (2006) · Zbl 1128.90044 · doi:10.1137/050644471
[9] Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numer. 22, 1-131 (2013) · Zbl 1291.65172 · doi:10.1017/S0962492913000032
[10] Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24, 597-634 (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124
[11] Ben-Tal, A., Nemirovski, A., Roos, C.: Extended matrix cube theorems with applications to \[\mu\] μ-theory in control. Math. Oper. Res. 28, 497-523 (2003) · Zbl 1082.90083 · doi:10.1287/moor.28.3.497.16392
[12] Bienstock, D.: Electrical Transmission System Cascades and Vulnerability: An Operations Research Viewpoint, vol. 22. SIAM, Philadelphia (2016) · Zbl 1344.90001
[13] Bienstock, D., Munoz, G.: LP Approximations to Mixed-Integer Polynomial Optimization Problems. arXiv:1501.00288 (2015) · Zbl 1179.90237
[14] Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1-29. Springer, New York (1993) · Zbl 0803.68081
[15] Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2, 1-19 (2010) · Zbl 1190.90135 · doi:10.1007/s12532-010-0010-8
[16] Burer, S., Vandenbussche, D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43, 181-195 (2009) · Zbl 1170.90522 · doi:10.1007/s10589-007-9137-6
[17] Chen, C., Atamtürk, A., Oren, S.S.: Bound tightening for the alternating current optimal power flow problem. IEEE Trans. Power Syst. (2015). doi:10.1109/TPWRS.2015.2497160 · doi:10.1109/TPWRS.2015.2497160
[18] Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4, 33-52 (2012) · Zbl 1257.90065 · doi:10.1007/s12532-011-0033-9
[19] Coffrin, C., Gordon, D., Scott, P.: NESTA, The NICTA Energy System Test Case Archive. arXiv:1411.0359 (2014) · Zbl 0754.90039
[20] De Maio, A., Huang, Y., Piezzo, M., Zhang, S., Farina, A.: Design of optimized radar codes with a peak to average power ratio constraint. IEEE Trans. Signal Proces. 59, 2683-2697 (2011) · Zbl 1392.94753 · doi:10.1109/TSP.2011.2128313
[21] Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: general framework. SIAM J. Optim. 11, 647-674 (2001) · Zbl 1010.90053 · doi:10.1137/S1052623400366218
[22] Gopalakrishnan, A., Raghunathan, A.U., Nikovski, D., Biegler, L.T.: Global optimization of optimal power flow using a branch & bound algorithm. In: IEEE 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 609-616 (2012) · Zbl 1341.90096
[23] Grone, R., Johnson, C.R., Sá, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58, 109-124 (1984) · Zbl 0547.15011 · doi:10.1016/0024-3795(84)90207-6
[24] Huang, Y., Palomar, D.P.: Randomized algorithms for optimal solutions of double-sided QCQP with applications in signal processing. IEEE Trans. Signal Process. 62, 1093-1108 (2014) · Zbl 1394.94245 · doi:10.1109/TSP.2013.2297683
[25] Huang, Y., Zhang, S.: Complex matrix decomposition and quadratic programming. Math. Oper. Res. 32, 758-768 (2007) · Zbl 1341.90096 · doi:10.1287/moor.1070.0268
[26] Jabr, R.A.: Optimal power flow using an extended conic quadratic formulation. IEEE Trans. Power Syst. 23, 1000-1008 (2008) · doi:10.1109/TPWRS.2008.926439
[27] Jabr, R.A.: Exploiting sparsity in SDP relaxations of the OPF problem. IEEE Trans. Power Syst. 27, 1138-1139 (2012) · doi:10.1109/TPWRS.2011.2170772
[28] Jiang, B., Li, Z., Zhang, S.: Approximation methods for complex polynomial optimization. Comput. Optim. Appl. 59, 219-248 (2014) · Zbl 1317.90328 · doi:10.1007/s10589-014-9640-5
[29] Josz, C., Molzahn, D.K.: Moment/Sum-of-Squares Hierarchy for Complex Polynomial Optimization. arXiv:1508.02068 (2015) · Zbl 1395.90196
[30] Kocuk, B., Dey, S.S., Sun, X.A.: Inexactness of SDP relaxation and valid inequalities for optimal power flow. IEEE Trans. Power Syst. 31, 642-651 (2016) · doi:10.1109/TPWRS.2015.2402640
[31] Lavaei, J., Low, S.H.: Zero duality gap in optimal power flow problem. IEEE Trans. Power Syst. 27, 92-107 (2012) · doi:10.1109/TPWRS.2011.2160974
[32] 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
[33] Lofberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: IEEE International Symposium on Computer Aided Control Systems Design, pp. 284-289 (2004) · Zbl 0787.90088
[34] Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1, 166-190 (1991) · Zbl 0754.90039 · doi:10.1137/0801013
[35] McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part 1 convex underestimating problems. Math. Program. 10, 147-175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665
[36] Misener, R., Floudas, C.A.: GloMIQO: global mixed-integer quadratic optimizer. J. Global Optim. 57, 3-50 (2013) · Zbl 1272.90034 · doi:10.1007/s10898-012-9874-7
[37] Misener, R., Smadbeck, J.B., Floudas, C.A.: Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2. Optim. Methods Softw. 30, 215-249 (2015) · Zbl 1325.90071 · doi:10.1080/10556788.2014.916287
[38] Molzahn, D.K., Holzer, J.T., Lesieutre, B.C., DeMarco, C.L.: Implementation of a large-scale optimal power flow solver based on semidefinite programming. IEEE Trans. Power Syst. 28, 1-12 (2013) · doi:10.1109/TPWRS.2013.2285610
[39] Petriu, D.C., Shen, H.: Applying the UML performance profile: graph grammar-based derivation of LQN models from UML specifications. In: Field, T., Harrison, P.G., Bradley, J., Harder, U. (eds.) Computer Performance Evaluation: Modelling Techniques and Tools, vol. 2324, pp. 159-177. Springer, Berlin (2002) · Zbl 1047.68538
[40] Phan, D.T.: Lagrangian duality-based branch and bound algorithms for optimal power flow. Oper. Res. 60, 275-285 (2012) · Zbl 1251.90308 · doi:10.1287/opre.1110.1036
[41] 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
[42] 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
[43] Sherali, H.D., Tuncbilek, C.H.: A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Global Optim. 2, 101-112 (1992) · Zbl 0787.90088 · doi:10.1007/BF00121304
[44] Shor, N.Z.: Quadratic optimization problems. Soviet J. Circuits Syst. Sci. 25, 6 (1987) · Zbl 0655.90055
[45] Sun, D.I., Ashley, B., Brewer, B., Hughes, A., Tinney, W.F.: Optimal power flow by Newton approach. IEEE Trans. Power Appar. Syst. 10, 2864-2880 (1984) · doi:10.1109/TPAS.1984.318284
[46] Tao, T.: Topics in Random Matrix Theory, vol. 132. American Mathematical Society, Providence (2012) · Zbl 1256.15020
[47] The MathWorks. MATLAB User’s Guide (1998) · Zbl 1169.90425
[48] Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[49] Waldspurger, I., D’Aspremont, A., Mallat, S.: Phase recovery, maxcut and complex semidefinite programming. Math. Program. 149, 47-81 (2015) · Zbl 1329.94018 · doi:10.1007/s10107-013-0738-9
[50] Zimmerman, R.D., Murillo-Sánchez, C.E., Thomas, R.J.: MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education. IEEE Trans. Power Syst. 26, 12-19 (2011) · doi:10.1109/TPWRS.2010.2051168
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.