×

How to convexify the intersection of a second order cone and a nonconvex quadratic. (English) Zbl 1358.90095

Summary: A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown–by several authors using different techniques – that the convex hull of the intersection of an ellipsoid, \(\mathcal {E}\), and a split disjunction, \((l - x_j)(x_j - u) \leq 0\) with \(l < u\), equals the intersection of \(\mathcal {E}\) with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form \(\mathcal {K}\cap \mathcal {Q}\) and \(\mathcal {K}\cap \mathcal {Q}\cap H\), where \(\mathcal {K}\) is a SOCr cone, \(\mathcal {Q}\) is a nonconvex cone defined by a single homogeneous quadratic, and \(H\) is an affine hyperplane. Under several easy-to-verify conditions, we derive simple, computable convex relaxations \(\mathcal {K}\cap \mathcal {S}\) and \(\mathcal {K}\cap \mathcal {S}\cap H\), where \(\mathcal {S}\) is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.

MSC:

90C25 Convex programming
90C10 Integer programming
90C11 Mixed integer programming
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization

Software:

GQTPAR

References:

[1] Adjiman, C., Dallwig, S., Floudas, C., Neumaier, A.: A global optimization method, \[ \alpha\] α-BB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137-1158 (1998) · doi:10.1016/S0098-1354(98)00027-1
[2] Andersen, K., Jensen, A.N.: Intersection cuts for mixed integerconic quadratic sets. In: Proceedings of IPCO 2013, volume7801 of Lecture Notes in Computer Science, pp. 37-48.Valparaiso, Chile (March 2013) · Zbl 1346.90623
[3] Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \[ \alpha{{\rm BB}}\] αBB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7(4), 337-363 (1995). State of the art in global optimization: computational methods and applications (Princeton, NJ, 1995) · Zbl 0846.90087
[4] Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124(1-2), 33-43 (2010) · Zbl 1198.90311 · doi:10.1007/s10107-010-0355-9
[5] Atamtürk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Math. Program. 122(1), 1-20 (2010) · Zbl 1184.90112 · doi:10.1007/s10107-008-0239-4
[6] Balas, E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19-39 (1971) · Zbl 0219.90035 · doi:10.1287/opre.19.1.19
[7] Balas, E.: Disjunctive programming. Ann. Discret. Math. 5, 3-51 (1979) · Zbl 0409.90061 · doi:10.1016/S0167-5060(08)70342-X
[8] Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58, 295-324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[9] Bao, X., Sahinidis, N.V., Tawarmalani, M.: Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math. Program. 129(1), 129-157 (2011) · Zbl 1232.49035 · doi:10.1007/s10107-011-0462-2
[10] Barvinok, A.: A Course in Convexity, vol. 54. American Mathematical Society, Providence (2002) · Zbl 1014.52001
[11] Belotti, P.: Disjunctive cuts for nonconvex MINLP. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, volume 154 of The IMA Volumes in Mathematics and its Applications, pp. 117-144. Springer, New York, NY (2012) · Zbl 1242.90118
[12] Belotti, P., Góez, J., Pólik, I., Ralphs, T., Terlaky, T.: On families of quadratic surfaces having fixed intersections with two hyperplanes. Discret. Appl. Math. 161(16), 2778-2793 (2013) · Zbl 1288.90052 · doi:10.1016/j.dam.2013.05.017
[13] Belotti, P., Goez, J.C., Polik, I., Ralphs, T.K., Terlaky, T.: A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization. In: Al-Baali, M., Grandinetti, L., Purnama, A. (eds.) Numerical Analysis and Optimization, volume 134 of Springer Proceedings in Mathematics and Statistics, pp. 1-35. Springer (2014) · Zbl 1330.65083
[14] Bienstock, D., Michalka, A.: Cutting-planes for optimization of convex functions over nonconvex sets. SIAM J. Optim. 24(2), 643-677 (2014) · Zbl 1334.90130 · doi:10.1137/120878963
[15] Bonami, P.: Lift-and-project cuts for mixed integer convex programs. In: Gunluk, O., Woeginger, G.J. (eds.) Proceedings of the 15th IPCO Conference, volume 6655 of Lecture Notes in Computer Science, pp. 52-64. Springer, New York, NY (2011) · Zbl 1339.90243
[16] Burer, S., Anstreicher, K.M.: Second-order-cone constraints for extended trust-region subproblems. SIAM J. Optim. 23(1), 432-451 (2013) · Zbl 1298.90062 · doi:10.1137/110826862
[17] Burer, S., Saxena, A.: The MILP road to MIQCP. In: Mixed Integer Nonlinear Programming, pp. 373-405. Springer (2012) · Zbl 1242.90122
[18] Cadoux, F.: Computing deep facet-defining disjunctive cuts for mixed-integer programming. Math. Program. 122(2), 197-223 (2010) · Zbl 1184.90105 · doi:10.1007/s10107-008-0245-6
[19] Çezik, M., Iyengar, G.: Cuts for mixed 0-1 conic programming. Math. Program. 104(1), 179-202 (2005) · Zbl 1159.90457 · doi:10.1007/s10107-005-0578-3
[20] Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Program. 86(3), 595-614 (1999) · Zbl 0954.90049 · doi:10.1007/s101070050106
[21] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-RegionMethods. MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA (2000) · Zbl 1047.90510
[22] Cornuéjols, G., Lemaréchal, C.: A convex-analysis perspective on disjunctive cuts. Math. Program. 106(3), 567-586 (2006) · Zbl 1149.90175 · doi:10.1007/s10107-005-0670-8
[23] Dadush, D., Dey, S.S., Vielma, J.P.: The split closure of a strictly convex body. Oper. Res. Lett. 39, 121-126 (2011) · Zbl 1225.90085 · doi:10.1016/j.orl.2011.02.002
[24] Drewes, S.: Mixed Integer Second Order Cone Programming. Ph.D. thesis, Technische Universität Darmstadt (2009) · Zbl 1176.90002
[25] Drewes, S., Pokutta, S.: Cutting-planes for weakly-coupled 0/1 second order cone programs. Electron. Notes in Discrete Math. 36, 735-742 (2010) · Zbl 1237.90160 · doi:10.1016/j.endm.2010.05.093
[26] Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504-525 (1999) · Zbl 1047.90510 · doi:10.1137/S1052623497322735
[27] Günlük, O., Linderoth, J.: Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program. 124(1-2), 183-205 (2010) · Zbl 1229.90106 · doi:10.1007/s10107-010-0360-z
[28] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2013) · Zbl 1267.15001
[29] Hu, J., Mitchell, J.E., Pang, J.-S., Bennett, K.P., Kunapuli, G.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19(1), 445-471 (2008) · Zbl 1163.90031 · doi:10.1137/07068463x
[30] Jeyakumar, V., Li, G.Y.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. 147(1), 171-206 (2013) · Zbl 1297.90105
[31] Júdice, J.J., Sherali, H., Ribeiro, I.M., Faustino, A.M.: A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints. J. Glob. Optim. 136, 89-114 (2006) · Zbl 1131.90061 · doi:10.1007/s10898-006-9001-8
[32] Kato, T.: Perturbation Theory for Linear Operators, second edn. Springer, Berlin-New York (1976). Grundlehren der Mathematischen Wissenschaften, Band 132 · Zbl 1288.90052
[33] Kılınç, M., Linderoth, J., Luedtke, J.: Effective separation of disjunctive cuts for convex mixed integer nonlinear programs. Technical report. http://www.optimization-online.org/DB_FILE/2010/11/2808.pdf (2010) · Zbl 1387.90159
[34] Kılınç-Karzan, F.: On minimal inequalities for mixed integer conic programs. Math. Oper. Res. 41(2), 477-510 (2016) · Zbl 1338.90275 · doi:10.1287/moor.2015.0737
[35] Kılınç-Karzan, F., Yıldız, S.: Two-term disjunctions on the second-order cone. In: Lee, J., Vygen, J. (eds.) IPCO, volume 8494 of Lecture Notes in Computer Science, pp. 345-356. Springer (2014) · Zbl 1418.90178
[36] Kılınç-Karzan, F., Yıldız, S.: Two-term disjunctions on the second-order cone. Math. Program. 154(1), 463-491 (2015) · Zbl 1327.90137 · doi:10.1007/s10107-015-0903-4
[37] Kim, S., Kojima, M.: Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods Softw. 15(3-4), 201-224 (2001) · Zbl 1109.90327 · doi:10.1080/10556780108805819
[38] Mahajan, A., Munson, T.: Exploiting second-order cone structure for global optimization. Technical report. ANL/MCS-P1801-1010, Argonne National Laboratory, http://www.optimization-online.org/DB_HTML/2010/10/2780.html (October 2010) · Zbl 0219.90035
[39] Modaresi, S., Kılınç, M.R., Vielma, J.P.: Split cuts and extended formulations for mixed integer conic quadratic programming. Oper. Res. Lett. 43(1), 10-15 (2015) · Zbl 1408.90201 · doi:10.1016/j.orl.2014.10.006
[40] Modaresi, S., Kılınç, M.R., Vielma, J.P.: Intersection cuts for nonlinear integer programming: convexification techniques for structured sets. Math. Program. 155(1), 575-611 (2016) · Zbl 1358.90078 · doi:10.1007/s10107-015-0866-5
[41] Modaresi, S., Vielma, J.: Convex hull of two quadratic or a conic quadratic and a quadratic inequality. Technical report. http://www.optimization-online.org/DB_HTML/2014/11/4641.html (November 2014) · Zbl 1393.90074
[42] Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4(3), 553-572 (1983) · Zbl 0551.65042 · doi:10.1137/0904038
[43] Nguyen, T.T., Tawarmalani, M., Richard, J.-P.P.: Convexification techniques for linear complementarity constraints. In: Günlük, O., Woeginger, G.J. (eds.) IPCO, volume 6655 of Lecture Notes in Computer Science, pp. 336-348. Springer (2011) · Zbl 1341.90130
[44] Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), 339-358 (1998) · Zbl 0977.90051 · doi:10.1287/moor.23.2.339
[45] Pólik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49(3), 371-418 (2007). (electronic) · Zbl 1128.90046 · doi:10.1137/S003614450444614X
[46] Rellich, F.: Perturbation theory of eigenvalue problems. Assisted by J. Berkowitz. With a preface by Jacob T. Schwartz. Gordon and Breach Science Publishers, New York-London-Paris (1969) · Zbl 0181.42002
[47] Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77(2), 273-299 (1997) · Zbl 0888.90137
[48] Saxena, A., Bonami, P., Lee, J.: Disjunctive cuts for non-convex mixed integer quadratically constrained programs. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO, volume 5035 of Lecture Notes in Computer Science, pp. 17-33. Springer (2008) · Zbl 1143.90365
[49] Sherali, H., Shetty, C.: Optimization with disjunctive constraints. Lectures on Econ. Math. Systems, 181 (1980) · Zbl 0437.90052
[50] Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0-1 mixed convex programming. Math. Program. 86(3), 515-532 (1999) · Zbl 0946.90054 · doi:10.1007/s101070050103
[51] Tawarmalani, M., Richard, J., Chung, K.: Strong valid inequalities for orthogonal disjunctions and bilinear covering sets. Math. Program. 124(1-2), 481-512 (2010) · Zbl 1198.90298 · doi:10.1007/s10107-010-0374-6
[52] Tawarmalani, M., Richard, J.-P.P., Xiong, C.: Explicit convex and concave envelopes through polyhedral subdivisions. Math. Program. 138(1-2), 531-577 (2013) · Zbl 1273.90165 · doi:10.1007/s10107-012-0581-4
[53] Vielma, J.P., Ahmed, S., Nemhauser, G.L.: A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS J. Comput. 20(3), 438-450 (2008) · Zbl 1243.90170 · doi:10.1287/ijoc.1070.0256
[54] Yıldıran, U.: Convex hull of two quadratic constraints is an LMI set. IMA J. Math. Control Inf. 26, 417-450 (2009) · Zbl 1187.90227 · doi:10.1093/imamci/dnp023
[55] Yıldız, S., Cornuéjols, G.: Disjunctive cuts for cross-sections of the second-order cone. Oper. Res. Lett. 43(4), 432-437 (2015) · Zbl 1408.90206 · doi:10.1016/j.orl.2015.06.001
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.