{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T04:11:33Z","timestamp":1767845493530,"version":"3.49.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T00:00:00Z","timestamp":1674864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T00:00:00Z","timestamp":1674864000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1930582"],"award-info":[{"award-number":["1930582"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1818700"],"award-info":[{"award-number":["1818700"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1807260"],"award-info":[{"award-number":["1807260"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009224","name":"Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["260801540061"],"award-info":[{"award-number":["260801540061"]}],"id":[{"id":"10.13039\/100009224","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["12951270"],"award-info":[{"award-number":["12951270"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["211253"],"award-info":[{"award-number":["211253"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study the convex quadratic optimization problem with indicator variables. For the <jats:inline-formula><jats:alternatives><jats:tex-math>$${2\\times 2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the <jats:inline-formula><jats:alternatives><jats:tex-math>$${2\\times 2}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including the optimal perspective relaxation and the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.\n<\/jats:p>","DOI":"10.1007\/s10107-023-01924-w","type":"journal-article","created":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T14:23:44Z","timestamp":1674915824000},"page":"95-134","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["$$\\mathbf {2\\times 2}$$-Convexifications for convex quadratic optimization with indicator variables"],"prefix":"10.1007","volume":"202","author":[{"given":"Shaoning","family":"Han","sequence":"first","affiliation":[]},{"given":"Andr\u00e9s","family":"G\u00f3mez","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1220-808X","authenticated-orcid":false,"given":"Alper","family":"Atamt\u00fcrk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,28]]},"reference":[{"issue":"3","key":"1924_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.orl.2008.12.009","volume":"37","author":"MS Akt\u00fcrk","year":"2009","unstructured":"Akt\u00fcrk, M.S., Atamt\u00fcrk, A., G\u00fcrel, S.: A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37(3), 187\u2013191 (2009)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1924_CR2","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-010-0355-9","volume":"124","author":"K Anstreicher","year":"2010","unstructured":"Anstreicher, K., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124(1), 33\u201343 (2010)","journal-title":"Math. Program."},{"issue":"2","key":"1924_CR3","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s10107-021-01671-w","volume":"188","author":"KM Anstreicher","year":"2021","unstructured":"Anstreicher, K.M., Burer, S.: Quadratic optimization with switching variables: the convex hull for $$ n= 2$$. Math. Program. 188(2), 421\u2013441 (2021)","journal-title":"Math. Program."},{"issue":"1","key":"1924_CR4","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10107-018-1301-5","volume":"170","author":"A Atamt\u00fcrk","year":"2018","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Strong formulations for quadratic optimization with M-matrices and indicator variables. Math. Program. 170(1), 141\u2013176 (2018)","journal-title":"Math. Program."},{"key":"1924_CR5","unstructured":"Atamt\u00fcrk, A. G\u00f3mez, A.: Rank-one convexification for sparse regression. arXiv:1901.10334 (2019)"},{"key":"1924_CR6","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Safe screening rules for $$\\ell _0$$-regression from perspective relaxations. In: International Conference on Machine Learning, pp. 421\u2013430. PMLR (2020)"},{"key":"1924_CR7","doi-asserted-by":"crossref","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Supermodularity and valid inequalities for quadratic optimization with indicators. Forthcoming Math. Program. (2022)","DOI":"10.1007\/s10107-022-01908-2"},{"issue":"52","key":"1924_CR8","first-page":"1","volume":"22","author":"A Atamt\u00fcrk","year":"2021","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A., Han, S.: Sparse and smooth signal estimation: convexification of $$\\ell _0$$-formulations. J. Mach. Learn. Res. 22(52), 1\u201343 (2021)","journal-title":"J. Mach. Learn. Res."},{"issue":"1\u20132","key":"1924_CR9","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s10107-018-1248-6","volume":"175","author":"F Bach","year":"2019","unstructured":"Bach, F.: Submodular functions: from discrete to continuous domains. Math. Program. 175(1\u20132), 419\u2013459 (2019)","journal-title":"Math. Program."},{"issue":"3","key":"1924_CR10","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10589-016-9847-8","volume":"65","author":"P Belotti","year":"2016","unstructured":"Belotti, P., Bonami, P., Fischetti, M., Lodi, A., Monaci, M., Nogales-G\u00f3mez, A., Salvagnin, D.: On handling indicator constraints in mixed integer programming. Comput. Optim. Appl. 65(3), 545\u2013566 (2016)","journal-title":"Comput. Optim. Appl."},{"key":"1924_CR11","unstructured":"Bertsimas, D., Cory-Wright, R., Pauphilet, J.: A unified approach to mixed-integer optimization: Nonlinear formulations and scalable algorithms. arXiv:1907.02109 (2019)"},{"issue":"2","key":"1924_CR12","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02592208","volume":"74","author":"D Bienstock","year":"1996","unstructured":"Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74(2), 121\u2013140 (1996)","journal-title":"Math. Program."},{"issue":"2","key":"1924_CR13","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1137\/120878963","volume":"24","author":"D Bienstock","year":"2014","unstructured":"Bienstock, D., Michalka, A.: Cutting-planes for optimization of convex functions over nonconvex sets. SIAM J. Optim. 24(2), 643\u2013677 (2014)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1924_CR14","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s10107-016-1031-5","volume":"162","author":"N Boland","year":"2017","unstructured":"Boland, N., Dey, S.S., Kalinowski, T., Molinaro, M., Rigterink, F.: Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions. Math. Program. 162(1), 523\u2013535 (2017)","journal-title":"Math. Program."},{"key":"1924_CR15","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.laa.2005.03.029","volume":"405","author":"EG Boman","year":"2005","unstructured":"Boman, E.G., Chen, D., Parekh, O., Toledo, S.: On factor width and symmetric H-matrices. Linear Algebra Appl. 405, 239\u2013248 (2005)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1924_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s10107-015-0891-4","volume":"151","author":"P Bonami","year":"2015","unstructured":"Bonami, P., Lodi, A., Tramontani, A., Wiese, S.: On mathematical programming with indicator constraints. Math. Program. 151(1), 191\u2013223 (2015)","journal-title":"Math. Program."},{"issue":"4","key":"1924_CR17","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1287\/opre.2014.1293","volume":"62","author":"J Castro","year":"2014","unstructured":"Castro, J., Frangioni, A., Gentile, C.: Perspective reformulations of the CTA problem with $$l_2$$ distances. Oper. Res. 62(4), 891\u2013909 (2014)","journal-title":"Oper. Res."},{"key":"1924_CR18","unstructured":"De\u00a0Rosa, A., Khajavirad, A.: Explicit convex hull description of bivariate quadratic sets with indicator variables. arXiv:2208.08703 (2022)"},{"issue":"135","key":"1924_CR19","first-page":"1","volume":"22","author":"A Dedieu","year":"2021","unstructured":"Dedieu, A., Hazimeh, H., Mazumder, R.: Learning sparse classifiers: continuous and mixed integer optimization perspectives. J. Mach. Learn. Res. 22(135), 1\u201347 (2021)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"1924_CR20","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s11081-018-9402-9","volume":"20","author":"SS Dey","year":"2019","unstructured":"Dey, S.S., Santana, A., Wang, Y.: New SOCP relaxation and branching rule for bipartite bilinear programs. Optim. Eng. 20(2), 307\u2013336 (2019)","journal-title":"Optim. Eng."},{"key":"1924_CR21","unstructured":"Dong, H., Chen, K., Linderoth, J.: Regularization vs. relaxation: A conic optimization perspective of statistical variable selection. arXiv:1510.06083 (2015)"},{"key":"1924_CR22","doi-asserted-by":"crossref","unstructured":"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\u2013180. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-36694-9_15"},{"issue":"2","key":"1924_CR23","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-005-0594-3","volume":"106","author":"A Frangioni","year":"2006","unstructured":"Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0\u20131 mixed integer programs. Math. Program. 106(2), 225\u2013236 (2006)","journal-title":"Math. Program."},{"key":"1924_CR24","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.orl.2006.03.008","volume":"35","author":"A Frangioni","year":"2007","unstructured":"Frangioni, A., Gentile, C.: SDP diagonalizations and perspective cuts for a class of nonseparable MIQP. Oper. Res. Lett. 35, 181\u2013185 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1924_CR25","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1287\/moor.2018.0969","volume":"45","author":"A Frangioni","year":"2020","unstructured":"Frangioni, A., Gentile, C., Hungerford, J.: Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs. Math. Oper. Res. 45(1), 15\u201333 (2020)","journal-title":"Math. Oper. Res."},{"issue":"8","key":"1924_CR26","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1109\/TAC.2011.2140770","volume":"56","author":"J Gao","year":"2011","unstructured":"Gao, J., Li, D.: Cardinality constrained linear-quadratic optimal control. IEEE Trans. Autom. Control 56(8), 1936\u20131941 (2011)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"3","key":"1924_CR27","doi-asserted-by":"publisher","first-page":"1897","DOI":"10.1137\/19M1306233","volume":"31","author":"A G\u00f3mez","year":"2021","unstructured":"G\u00f3mez, A.: Outlier detection in time series via mixed-integer conic quadratic optimization. SIAM J. Optim. 31(3), 1897\u20131925 (2021)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1924_CR28","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10107-020-01508-y","volume":"188","author":"A G\u00f3mez","year":"2021","unstructured":"G\u00f3mez, A.: Strong formulations for conic quadratic optimization with indicator variables. Math. Program. 188(1), 193\u2013226 (2021)","journal-title":"Math. Program."},{"key":"1924_CR29","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s10107-010-0360-z","volume":"124","author":"O G\u00fcnl\u00fck","year":"2010","unstructured":"G\u00fcnl\u00fck, O., Linderoth, J.: Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program. 124, 183\u2013205 (2010)","journal-title":"Math. Program."},{"key":"1924_CR30","doi-asserted-by":"publisher","first-page":"100569","DOI":"10.1016\/j.disopt.2020.100569","volume":"36","author":"A Gupte","year":"2020","unstructured":"Gupte, A., Kalinowski, T., Rigterink, F., Waterer, H.: Extended formulations for convex hulls of some bilinear functions. Discret. Optim. 36, 100569 (2020)","journal-title":"Discret. Optim."},{"key":"1924_CR31","unstructured":"Han, S., G\u00f3mez, A.: Compact extended formulations for low-rank functions with indicator variables. arXiv:2110.14884 (2021)"},{"issue":"2","key":"1924_CR32","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.orl.2022.01.007","volume":"50","author":"S Han","year":"2022","unstructured":"Han, S., G\u00f3mez, A., Atamt\u00fcrk, A.: The equivalence of optimal perspective formulation and shor\u2019s sdp for quadratic programs with indicator variables. Oper. Res. Lett. 50(2), 195\u2013198 (2022)","journal-title":"Oper. Res. Lett."},{"key":"1924_CR33","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10589-011-9424-0","volume":"52","author":"H Hijazi","year":"2012","unstructured":"Hijazi, H., Bonami, P., Cornu\u00e9jols, G., Ouorou, A.: Mixed-integer nonlinear programs featuring \u201con\/off\u2019\u2019 constraints. Comput. Optim. Appl. 52, 537\u2013558 (2012)","journal-title":"Comput. Optim. Appl."},{"key":"1924_CR34","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1145\/502090.502093","volume":"48","author":"DS Hochbaum","year":"2001","unstructured":"Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48, 686\u2013701 (2001)","journal-title":"J. ACM"},{"key":"1924_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411","volume-title":"Matrix Analysis","author":"RA Horn","year":"2012","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2012)"},{"key":"1924_CR36","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.disopt.2016.04.008","volume":"24","author":"H Jeon","year":"2017","unstructured":"Jeon, H., Linderoth, J., Miller, A.: Quadratic cone cutting surfaces for quadratic programs with on-off constraints. Discret. Optim. 24, 32\u201350 (2017)","journal-title":"Discret. Optim."},{"issue":"1\u20132","key":"1924_CR37","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s10107-017-1197-5","volume":"172","author":"CH Lim","year":"2018","unstructured":"Lim, C.H., Linderoth, J., Luedtke, J.: Valid inequalities for separable concave constraints with indicator variables. Math. Program. 172(1\u20132), 415\u2013442 (2018)","journal-title":"Math. Program."},{"key":"1924_CR38","doi-asserted-by":"crossref","unstructured":"Liu, P., Fattahi, S., G\u00f3mez, A., K\u00fc\u00e7\u00fckyavuz, S.: A graph-based decomposition method for convex quadratic optimization with indicators. Math. Program. 1\u201333 (2022)","DOI":"10.1007\/s10107-022-01845-0"},{"issue":"1","key":"1924_CR39","first-page":"56","volume":"144","author":"M Locatelli","year":"2014","unstructured":"Locatelli, M., Schoen, F.: On convex envelopes for bivariate functions over polytopes. Math. Program. 144(1), 56\u201391 (2014)","journal-title":"Math. Program."},{"key":"1924_CR40","unstructured":"Mahajan, A., Leyffer, S., Linderoth, J., Luedtke, J., Munson, T.: Minotaur: a mixed-integer nonlinear optimization toolkit. Technical report, ANL\/MCS-P8010-0817, Argonne National Lab (2017)"},{"key":"1924_CR41","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T.: Convex Analysis (1970)","DOI":"10.1515\/9781400873173"},{"key":"1924_CR42","first-page":"1","volume":"25","author":"NZ Shor","year":"1987","unstructured":"Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1\u201311 (1987)","journal-title":"Sov. J. Comput. Syst. Sci."},{"issue":"1","key":"1924_CR43","doi-asserted-by":"publisher","first-page":"171","DOI":"10.2140\/pjm.1958.8.171","volume":"8","author":"M Sion","year":"1958","unstructured":"Sion, M.: On general minimax theorems. Pac. J. Math. 8(1), 171\u2013176 (1958)","journal-title":"Pac. J. Math."},{"key":"1924_CR44","doi-asserted-by":"publisher","first-page":"1531","DOI":"10.1137\/15M1012232","volume":"27","author":"B Wu","year":"2017","unstructured":"Wu, B., Sun, X., Li, D., Zheng, X.: Quadratic convex reformulations for semicontinuous quadratic programming. SIAM J. Optim. 27, 1531\u20131553 (2017)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1924_CR45","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1287\/ijoc.2014.0592","volume":"26","author":"X Zheng","year":"2014","unstructured":"Zheng, X., Sun, X., Li, D.: Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach. INFORMS J. Comput. 26(4), 690\u2013703 (2014)","journal-title":"INFORMS J. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01924-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01924-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01924-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T19:50:12Z","timestamp":1697053812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01924-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,28]]},"references-count":45,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["1924"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01924-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,28]]},"assertion":[{"value":"15 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}