×

zbMATH — the first resource for mathematics

The convex hull of a quadratic constraint over a polytope. (English) Zbl 1453.90115
MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
Software:
GloMIQO; SPOTless
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] W. Adams, A. Gupte, and Y. Xu, Error bounds for monomial convexification in polynomial optimization, Math. Program., 175 (2019), pp. 355-393. · Zbl 1412.90119
[2] A. A. Ahmadi and A. Majumdar, DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization, in Proceedings of the 48th Annual Conference on Information Sciences and Systems, IEEE, 2014, pp. 1-5.
[3] F. A. Al-Khayyal and J. E. Falk, Jointly constrained biconvex programming, Math. Oper. Res., 8 (1983), pp. 273-286. · Zbl 0521.90087
[4] M. Alfaki and D. Haugland, Strong formulations for the pooling problem, J. Global Optim., 56 (2013), pp. 897-916. · Zbl 1272.90054
[5] I. P. Androulakis, C. D. Maranas, and C. A. Floudas, \( \alpha\) BB: A global optimization method for general constrained nonconvex problems, J. Global Optim., 7 (1995), pp. 337-363. · Zbl 0846.90087
[6] K. M. Anstreicher and S. Burer, Computable representations for convex hulls of low-dimensional quadratic forms, Math. Program., 124 (2010), pp. 33-43. · Zbl 1198.90311
[7] X. Bao, A. Khajavirad, N. V. Sahinidis, and M. Tawarmalani, Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7 (2015), pp. 1-37. · Zbl 1317.90243
[8] P. Belotti, J. C. Góez, I. Pólik, T. K. Ralphs, and T. Terlaky, On families of quadratic surfaces having fixed intersections with two hyperplanes, Discrete Appl. Math., 161 (2013), pp. 2778-2793. · Zbl 1288.90052
[9] P. Belotti, A. J. Miller, and M. Namazifar, Valid inequalities and convex hulls for multilinear functions, Electron. Notes Discrete Math., 36 (2010), pp. 805-812, https://doi.org/10.1016/j.endm.2010.05.102. · Zbl 1274.90499
[10] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPS-SIAM Ser. Optim. 2, SIAM, Philadelphia, 2001. · Zbl 0986.90032
[11] H. P. Benson, Concave envelopes of monomial functions over rectangles, Naval Res. Logist., 51 (2004), pp. 467-476. · Zbl 1054.90056
[12] D. Bienstock and A. Michalka, Polynomial solvability of variants of the trust-region subproblem, in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 2014, pp. 380-390, https://doi.org/10.1137/1.9781611973402.28. · Zbl 1428.90109
[13] D. Bienstock and A. Michalka, Cutting-planes for optimization of convex functions over nonconvex sets, SIAM J. Optim., 24 (2014), pp. 643-677. · Zbl 1334.90130
[14] S. Bose, D. F. Gayme, K. M. Chandy, and S. H. Low, Quadratically constrained quadratic programs on acyclic graphs with application to power flow, IEEE Trans. Control Network Syst., 2 (2015), pp. 278-287, https://doi.org/10.1109/TCNS.2015.2401172. · Zbl 1370.90168
[15] C. Buchheim and C. D’Ambrosio, Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization, J. Global Optim., 67 (2017), pp. 759-786. · Zbl 1370.90153
[16] S. Burer and K. M. Anstreicher, Second-order-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23 (2013), pp. 432-451. · Zbl 1298.90062
[17] S. Burer and F. K\il\inç-Karzan, How to convexify the intersection of a second order cone and a nonconvex quadratic, Math. Program., 162 (2017), pp. 393-429, https://doi.org/10.1007/s10107-016-1045-z. · Zbl 1358.90095
[18] S. Burer, S. Kim, and M. Kojima, Faster, but weaker, relaxations for quadratically constrained quadratic programs, Comput. Optim. Appl., 59 (2014), pp. 27-45, https://doi.org/10.1007/s10589-013-9618-8. · Zbl 1303.90077
[19] S. Burer and B. Yang, The trust region subproblem with non-intersecting linear constraints, Math. Program., 149 (2015), pp. 253-264. · Zbl 1308.90121
[20] C. Chen, A. Atamtürk, and S. S. Oren, Bound tightening for the alternating current optimal power flow problem, IEEE Trans. Power Syst., 31 (2016), pp. 3729-3736, https://doi.org/10.1109/TPWRS.2015.2497160.
[21] Y. Crama and E. Rodríguez-Heck, A class of valid inequalities for multilinear 0-1 optimization problems, Discrete Optim., 25 (2017), pp. 28-47. · Zbl 1387.90125
[22] D. Davarnia, J.-P. P. Richard, and M. Tawarmalani, Simultaneous convexification of bilinear functions over polytopes with application to network interdiction, SIAM J. Optim., 27 (2017), pp. 1801-1833. · Zbl 1377.90066
[23] A. Del Pia and A. Khajavirad, A polyhedral study of binary polynomial programs, Math. Oper. Res., 42 (2016), pp. 389-410. · Zbl 1364.90225
[24] S. S. Dey and A. Gupte, Analysis of MILP techniques for the pooling problem, Oper. Res., 63 (2015), pp. 412-427. · Zbl 1327.90351
[25] S. S. Dey, B. Kocuk, and A. Santana, Convexifications of rank-one-based substructures in QCQPs and applications to the pooling problem, J. Global Optim., 77 (2020), pp. 227-272, https://doi.org/10.1007/s10898-019-00844-4. · Zbl 07195873
[26] S. S. Dey, A. Santana, and Y. Wang, New SOCP relaxation and branching rule for bipartite bilinear programs, Optim. Eng., 20 (2019), pp. 307-336, https://doi.org/10.1007/s11081-018-9402-9. · Zbl 1431.90148
[27] W. L. Edge, The Theory of Ruled Surfaces, Cambridge University Press, New York, 1931. · Zbl 0001.40405
[28] H. Fawzi, On representing the positive semidefinite cone using the second-order cone, Math. Program., 175 (2019), pp. 109-118. · Zbl 1412.90103
[29] A. Gharanjik, B. Shankar, M. Soltanalian, and B. Oftersten, An iterative approach to nonconvex QCQP with applications in signal processing, in Proceedings of the Sensor Array and Multichannel Signal Processing Workshop, IEEE, 2016, pp. 1-5.
[30] M. X. Goemans and D. P. Williamson, ..879-approximation algorithms for MAX CUT and MAX 2SAT, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994, pp. 422-431. · Zbl 1345.68274
[31] A. Gupte, Mixed Integer Bilinear Pogramming with Applications to the Pooling Problem, Ph.D. thesis, Georgia Institute of Technology, 2011.
[32] A. Gupte, S. Ahmed, S. S. Dey, and M. S. Cheon, Relaxations and discretizations for the pooling problem, J. Global Optim., 67 (2017), pp. 631-669. · Zbl 1392.90117
[33] A. Gupte, T. Kalinowski, F. Rigterink, and H. Waterer, Extended formulations for convex hulls of graphs of some bilinear functions, Discrete Optim., 36 (2020). · Zbl 07225953
[34] C. A. Haverly, Studies of the behavior of recursion for the pooling problem, ACM SIGMAP Bulletin, 1978, pp. 19-28.
[35] R. J. Hillestad and S. E. Jacobsen, Linear programs with an additional reverse convex constraint, Appl. Math. Optim., 6 (1980), pp. 257-269, https://doi.org/10.1007/BF01442898. · Zbl 0435.90065
[36] Q. Jin, Y. Tian, Z. Deng, S.-C. Fang, and W. Xing, Exact computable representation of some second-order cone constrained quadratic programming problems, J. Oper. Res. Soc. of China, 1 (2013), pp. 107-134, https://doi.org/10.1007/s40305-013-0009-8. · Zbl 1277.90091
[37] A. Khabbazibasmenj and S. A. Vorobyov, Generalized quadratically constrained quadratic programming for signal processing, in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 2014, pp. 7629-7633, https://doi.org/10.1109/ICASSP.2014.6855084.
[38] B. Kocuk, S. S. Dey, and X. A. Sun, Strong SOCP relaxations for the optimal power flow problem, Oper. Res., 64 (2016), pp. 1177-1196. · Zbl 1354.90154
[39] B. Kocuk, S. S. Dey, and X. A. Sun, Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem, Math. Program. Comput., 10 (2018), pp. 557-596, https://doi.org/10.1007/s12532-018-0150-9. · Zbl 1411.90249
[40] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796-817. · Zbl 1010.90061
[41] Q. Li and V. Vittal, Convex hull of the quadratic branch AC power flow equations and its application in radial distribution networks, IEEE Trans. Power Systems, 33 (2018), pp. 839-850, https://doi.org/10.1109/TPWRS.2017.2712697.
[42] L. Liberti and C. C. Pantelides, Convex envelopes of monomials of odd degree, J. Global Optim., 25 (2003), pp. 157-168. · Zbl 1030.90117
[43] M. Locatelli, Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes, J. Global Optim., 66 (2016), pp. 629-668. · Zbl 1393.90095
[44] G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I-convex underestimating problems, Math. Program., 10 (1976), pp. 147-175. · Zbl 0349.90100
[45] C. A. Meyer and C. A. Floudas, Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes, J. Global Optim., 29 (2004), pp. 125-155. · Zbl 1085.90047
[46] C. A. Meyer and C. A. Floudas, Convex envelopes for edge-concave functions, Math. Program., 103 (2005), pp. 207-224. · Zbl 1099.90045
[47] C. A. Meyer and C. A. Floudas, Global optimization of a combinatorially complex generalized pooling problem, AIChE J., 52 (2006), pp. 1027-1037.
[48] R. Misener, J. B. Smadbeck, and C. A. Floudas, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optim. Methods Softw., 30 (2015), pp. 215-249. · Zbl 1325.90071
[49] S. Modaresi and J. P. Vielma, Convex hull of two quadratic or a conic quadratic and a quadratic inequality, Math. Program., 164 (2017), pp. 383-409, https://doi.org/10.1007/s10107-016-1084-5. · Zbl 1393.90074
[50] T. T. Nguyen, J.-P. P. Richard, and M. Tawarmalani, Deriving the Convex Hull of a Polynomial Partitioning Set Through Lifting and Projection, Tech. report, 2013.
[51] T. T. Nguyen, M. Tawarmalani, and J.-P. P. Richard, Convexification techniques for linear complementarity constraints, in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6655, Springer, New York, 2011, pp. 336-348. · Zbl 1341.90130
[52] H. Rahman and A. Mahajan, Facets of a mixed-integer bilinear covering set with bounds on variables, J. Global Optim., 74 (2019), pp. 417-442, https://doi.org/10.1007/s10898-019-00783-0. · Zbl 1426.90192
[53] A. D. Rikun, A convex envelope formula for multilinear functions, J. Global Optim., 10 (1997), pp. 425-437, https://doi.org/10.1023/A:1008217604285. · Zbl 0881.90099
[54] H. S. Ryoo and N. V. Sahinidis, Analysis of bounds for multilinear functions, J. Global Optim., 19 (2001), pp. 403-424. · Zbl 0982.90054
[55] H. D. Sherali, Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Math. Vietnam., 22 (1997), pp. 245-270. · Zbl 0914.90205
[56] H. D. Sherali and W. P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optim. Appl. 31, Springer, New York, 2013. · Zbl 0926.90078
[57] H. D. Sherali and A. Alameddine, An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopes, Ann. Oper. Res., 25 (1990), pp. 197-209. · Zbl 0723.90073
[58] H. D. Sherali and A. Alameddine, A new reformulation-linearization technique for bilinear programming problems, J. Global Optim., 2 (1992), pp. 379-410. · Zbl 0791.90056
[59] E. Speakman and J. Lee, Quantifying double McCormick, Math. Oper. Res., 42 (2017), pp. 1230-1253. · Zbl 1386.90121
[60] M. Tawarmalani and J.-P. P. Richard, Decomposition Techniques in Convexification of Inequalities, Tech. report, 2013.
[61] M. Tawarmalani, J.-P. P. Richard, and K. Chung, Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Math. Program., 124 (2010), pp. 481-512. · Zbl 1198.90298
[62] M. Tawarmalani, J.-P. P. Richard, and C. Xiong, Explicit convex and concave envelopes through polyhedral subdivisions, Math. Program., 138 (2013), pp. 531-577. · Zbl 1273.90165
[63] M. Tawarmalani and N. V. Sahinidis, Semidefinite relaxations of fractional programs via novel convexification techniques, J. Global Optim., 20 (2001), pp. 133-154, https://doi.org/10.1023/A:1011233805045. · Zbl 1001.90064
[64] M. Tawarmalani and N. V. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Nonconvex Optim. Appl. 65, Springer, New York, 2002. · Zbl 1031.90022
[65] H. Tuy, Convex Analysis and Global Optimization, Springer Optim. Appl. 110, Springer, New York, 2016. · Zbl 1362.90001
[66] A. L. Wang and F. K\il\inç-Karzan, On the Tightness of SDP Relaxations of QCQPs, preprint, https://arxiv.org/abs/1911.09195, 2019.
[67] A. L. Wang and F. K\il\inç-Karzan, On Convex Hulls of Epigraphs of QCQPs, preprint, https://arxiv.org/abs/2002.01566, 2020.
[68] U. Y\ild\iran, Convex hull of two quadratic constraints is an LMI set, IMA J. Math. Control Inform., 26 (2009), pp. 417-450, https://doi.org/10.1093/imamci/dnp023. · Zbl 1187.90227
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.