×

zbMATH — the first resource for mathematics

Strong formulations for quadratic optimization with M-matrices and indicator variables. (English) Zbl 1391.90423
Summary: We study quadratic optimization with indicator variables and an M-matrix, i.e., a PSD matrix with non-positive off-diagonal entries, which arises directly in image segmentation and portfolio optimization with transaction costs, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular minimization problem. To strengthen the formulation, we decompose the quadratic function into a sum of simple quadratic functions with at most two indicator variables each, and provide the convex-hull descriptions of these sets. We also describe strong conic quadratic valid inequalities. Preliminary computational experiments indicate that the proposed inequalities can substantially improve the strength of the continuous relaxations with respect to the standard perspective reformulation.

MSC:
90C11 Mixed integer programming
90C20 Quadratic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
MINOTAUR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, RK; Hochbaum, DS; Orlin, JB, A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem, Algorithmica, 39, 189-208, (2004) · Zbl 1134.90512
[2] Aktürk, MS; Atamtürk, A; Gürel, S, A strong conic quadratic reformulation for machine-job assignment with controllable processing times, Oper. Res. Lett., 37, 187-191, (2009) · Zbl 1167.90518
[3] Anstreicher, KM, On convex relaxations for quadratically constrained quadratic programming, Math. Program., 136, 233-251, (2012) · Zbl 1267.90103
[4] Atamtürk, A; Bhardwaj, A, Network design with probabilistic capacities, Networks, 71, 16-30, (2018)
[5] Atamtürk, A., Gomez, A.: Submodularity in conic quadratic mixed 0-1 optimization. BCOL Research Report 16.02, IEOR, UC Berkeley. arXiv preprint arXiv:1705.05918 (2017) · Zbl 0845.90089
[6] Atamtürk, A., Jeon, H.: Lifted polymatroid for mean-risk optimization with indicator variables. BCOL Research Report 17.01, IEOR, UC Berkeley. \(\text{arXiv}\,\,\text{ preprint }\)arXiv:1705.05915 (2017) · Zbl 0359.15005
[7] Atamtürk, A., Narayanan, V.: Cuts for conic mixed integer programming. In: Fischetti, M., Williamson, D.P. (eds.) Proceedings of the 12th International IPCO Conference, pp. 16-29 (2007) · Zbl 1136.90518
[8] Balas, E, Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Algebr. Discrete Methods, 6, 466-486, (1985) · Zbl 0592.90070
[9] Belotti, P., Góez, J.C., Pólik, 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: Numerical Analysis and Optimization, pp. 1-35. Springer (2015) · Zbl 1330.65083
[10] Bertsimas, D; King, A; Mazumder, R, Best subset selection via a modern optimization Lens, Ann. Stat., 44, 813-852, (2016) · Zbl 1335.62115
[11] Bienstock, D, Computational study of a family of mixed-integer quadratic programming problems, Math. Program., 74, 121-140, (1996) · Zbl 0855.90090
[12] Bienstock, D; Michalka, A, Cutting-planes for optimization of convex functions over nonconvex sets, SIAM J. Optim., 24, 643-677, (2014) · Zbl 1334.90130
[13] Boland, N; Dey, SS; Kalinowski, T; Molinaro, M; Rigterink, F, Bounding the gap between the mccormick relaxation and the convex hull for bilinear functions, Math. Program., 162, 523-535, (2017) · Zbl 1384.90073
[14] Boland, N., Gupte, A., Kalinowski, T., Rigterink, F., Waterer, H.: Extended formulations for convex hulls of graphs of bilinear functions. arXiv preprint arXiv:1702.04813 (2017b) · Zbl 1286.90117
[15] Bonami, P; Lodi, A; Tramontani, A; Wiese, S, On mathematical programming with indicator constraints, Math. Program., 151, 191-223, (2015) · Zbl 1328.90086
[16] Boykov, Y; Veksler, O; Zabih, R, Fast approximate energy minimization via graph cuts, IEEE Trans. Pattern Anal. Mach. Intell., 23, 1222-1239, (2001)
[17] Ceria, S; Soares, J, Convex programming for disjunctive convex optimization, Math. Program., 86, 595-614, (1999) · Zbl 0954.90049
[18] Cornuejols, G., Tütüncü, R.: Optimization Methods in Finance, vol. 5. Cambridge University Press, Cambridge (2006) · Zbl 1117.91031
[19] Dong, H., Linderoth, J.: On valid inequalities for quadratic programming with continuous variables and binary indicators. In: Goemans, M., Correa, J. (eds.) Proceedings of IPCO 2013, pp. 169-180. Springer, Berlin (2013) · Zbl 1372.90073
[20] Edmonds, J; Guy, R (ed.); Hanani, H (ed.); Sauer, N (ed.); Schönenheim, J (ed.), Submodular functions, matroids, and certain polyhedra, 69-87, (1970), Philadelphia
[21] Frangioni, A; Gentile, C, Perspective cuts for a class of convex 0-1 mixed integer programs, Math. Program., 106, 225-236, (2006) · Zbl 1134.90447
[22] Frangioni, A., Gentile, C., Hungerford, J.: Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs. Report R-16-10, IASI, Rome (2016)
[23] Gao, J; Li, D, Cardinality constrained linear-quadratic optimal control, IEEE Trans. Autom. Control, 56, 1936-1941, (2011) · Zbl 1368.90166
[24] Günlük, O; Linderoth, J, Perspective reformulations of mixed integer nonlinear programs with indicator variables, Math. Program., 124, 183-205, (2010) · Zbl 1229.90106
[25] Hijazi, H; Bonami, P; Cornuéjols, G; Ouorou, A, Mixed-integer nonlinear programs featuring “on/off” constraints, Comput. Optim. Appl., 52, 537-558, (2012) · Zbl 1250.90058
[26] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals, vol. 305. Springer, Berlin (2013) · Zbl 0795.49001
[27] Hochbaum, DS, Multi-label Markov random fields as an efficient and effective tool for image segmentation, total variations and regularization, Numer. Math. Theory Methods Appl., 6, 169-198, (2013) · Zbl 1289.68201
[28] Ivănescu, PL, Some network flow problems solved with pseudo-Boolean programming, Oper. Res., 13, 388-399, (1965) · Zbl 0132.13804
[29] Jeon, H; Linderoth, J; Miller, A, Quadratic cone cutting surfaces for quadratic programs with on-off constraints, Discrete Optim., 24, 32-50, (2017) · Zbl 1387.90174
[30] Keilson, J; Styan, GPH, Markov chains and M-matrices: inequalities and equalities, J. Math. Anal. Appl., 41, 439-459, (1973) · Zbl 0255.15016
[31] Kılınç-Karzan, F; Yıldız, S, Two-term disjunctions on the second-order cone, Math. Program., 154, 463-491, (2015) · Zbl 1327.90137
[32] Kolmogorov, V; Zabin, R, What energy functions can be minimized via graph cuts?, IEEE Trans. Pattern Anal. Mach. Intell., 26, 147-159, (2004)
[33] Lobo, MS; Fazel, M; Boyd, S, Portfolio optimization with linear and fixed transaction costs, Ann. Oper. Res., 152, 341-365, (2007) · Zbl 1132.91474
[34] Lovász, L; Bachem, A (ed.); Korte, B (ed.); Grötschel, M (ed.), Submodular functions and convexity, 235-257, (1983), Berlin
[35] Luedtke, J; Namazifar, M; Linderoth, J, Some results on the strength of relaxations of multilinear functions, Math. Program., 136, 325-351, (2012) · Zbl 1286.90117
[36] Luedtke, J., D’Ambrosio, C., Linderoth, J., Schweiger, J.: Strong convex nonlinear relaxations of the pooling problem. arXiv preprint arXiv:1803.02955 (2018)
[37] Luk, FT; Pagano, M, Quadratic programming with M-matrices, Linear Algebra Appl., 33, 15-40, (1980) · Zbl 0461.65050
[38] Mahajan, A., Leyffer, S., Linderoth, J., Luedtke, J., Munson, T.: Minotaur: A mixed-integer nonlinear optimization toolkit. ANL/MCS-P8010-0817, Argonne National Lab (2017) · Zbl 1334.90130
[39] Modaresi, S; Kılınç, MR; Vielma, JP, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, Math. Program., 155, 575-611, (2016) · Zbl 1358.90078
[40] Nemhauser, GL; Wolsey, LA; Fisher, ML, An analysis of approximations for maximizing submodular set functions I, Math. Program., 14, 265-294, (1978) · Zbl 0374.90045
[41] Orlin, JB, A faster strongly polynomial time algorithm for submodular function minimization, Math. Program., 118, 237-251, (2009) · Zbl 1179.90290
[42] Picard, JC; Ratliff, HD, Minimum cuts and related problems, Networks, 5, 357-370, (1975) · Zbl 0325.90047
[43] Plemmons, RJ, M-matrix characterizations. I—nonsingular M-matrices, Linear Algebra Appl., 18, 175-188, (1977) · Zbl 0359.15005
[44] Poljak, S; Wolkowicz, H, Convex relaxations of (0,1)-quadratic programming, Math. Oper. Res., 20, 550-561, (1995) · Zbl 0845.90089
[45] Stubbs, RA; Mehrotra, S, A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 515-532, (1999) · Zbl 0946.90054
[46] Vielma, J.P.: Small and strong formulations for unions of convex sets from the cayley embedding. To appear in Mathematical Programming, arXiv preprint arXiv:1704.03954 (2018)
[47] Wei, D; Sestok, CK; Oppenheim, AV, Sparse filter design under a quadratic constraint: low-complexity algorithms, IEEE Trans. Signal Process., 61, 857-870, (2013) · Zbl 1393.94485
[48] Wu, B; Sun, X; Li, D; Zheng, X, Quadratic convex reformulations for semicontinuous quadratic programming, SIAM J. Optim., 27, 1531-1553, (2017) · Zbl 1370.90156
[49] Young, N, The rate of convergence of a matrix power series, Linear Algebra Appl., 35, 261-278, (1981) · Zbl 0454.15013
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.