{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T01:42:32Z","timestamp":1767836552582,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"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"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1807260"],"award-info":[{"award-number":["1807260"]}],"id":[{"id":"10.13039\/100000001","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\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["2006762"],"award-info":[{"award-number":["2006762"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["2007814"],"award-info":[{"award-number":["2007814"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-19-1-2321"],"award-info":[{"award-number":["N00014-19-1-2321"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the convex quadratic optimization problem in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R}^{n}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>R<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an <jats:inline-formula><jats:alternatives><jats:tex-math>$$(n+1) \\times (n+1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are \u201cfinitely generated.\u201d In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.\n<\/jats:p>","DOI":"10.1007\/s10107-023-01982-0","type":"journal-article","created":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T12:03:24Z","timestamp":1686139404000},"page":"703-737","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the convex hull of convex quadratic optimization problems with indicators"],"prefix":"10.1007","volume":"204","author":[{"given":"Linchuan","family":"Wei","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1220-808X","authenticated-orcid":false,"given":"Alper","family":"Atamt\u00fcrk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3668-0653","authenticated-orcid":false,"given":"Andr\u00e9s","family":"G\u00f3mez","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6548-9378","authenticated-orcid":false,"given":"Simge","family":"K\u00fc\u00e7\u00fckyavuz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"key":"1982_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, 187\u2013191 (2009)","journal-title":"Oper. Res. Lett."},{"key":"1982_CR2","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10951-009-0111-2","volume":"13","author":"MS Akt\u00fcrk","year":"2010","unstructured":"Akt\u00fcrk, M.S., Atamt\u00fcrk, A., G\u00fcrel, S.: Parallel machine match-up scheduling with manufacturing cost considerations. J. Sched. 13, 95\u2013110 (2010)","journal-title":"J. Sched."},{"issue":"2","key":"1982_CR3","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/0117041","volume":"17","author":"A Albert","year":"1969","unstructured":"Albert, A.: Conditions for positive and nonnegative definiteness in terms of pseudoinverses. SIAM J. Appl. Math. 17(2), 434\u2013440 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"1982_CR4","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, 421\u2013441 (2021)","journal-title":"Math. Program."},{"key":"1982_CR5","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Rank-one convexification for sparse regression. arXiv preprint arXiv:1901.10334 (2019)"},{"key":"1982_CR6","doi-asserted-by":"publisher","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Supermodularity and valid inequalities for quadratic optimization with indicators. Math. Program. (2022). https:\/\/doi.org\/10.1007\/s10107-022-01908-2","DOI":"10.1007\/s10107-022-01908-2"},{"key":"1982_CR7","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, 141\u2013176 (2018)","journal-title":"Math. Program."},{"issue":"52","key":"1982_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."},{"key":"1982_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, 419\u2013459 (2019)","journal-title":"Math. Program."},{"key":"1982_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1287\/opre.2015.1436","volume":"64","author":"D Bertsimas","year":"2015","unstructured":"Bertsimas, D., King, A.: OR forum\u2013an algorithmic approach to linear regression. Oper. Res. 64, 2\u201316 (2015)","journal-title":"Oper. Res."},{"issue":"6","key":"1982_CR11","doi-asserted-by":"publisher","first-page":"3321","DOI":"10.1287\/opre.2021.2182","volume":"70","author":"D Bertsimas","year":"2022","unstructured":"Bertsimas, D., Cory-Wright, R., Pauphilet, J.: Mixed-projection conic optimization: a new paradigm for modeling rank constraints. Oper. Res. 70(6), 3321\u20133344 (2022)","journal-title":"Oper. Res."},{"issue":"3","key":"1982_CR12","doi-asserted-by":"publisher","first-page":"1111","DOI":"10.1214\/13-AOS1096","volume":"41","author":"J Bien","year":"2013","unstructured":"Bien, J., Taylor, J., Tibshirani, R.: A lasso for hierarchical interactions. Ann. Stat. 41(3), 1111 (2013)","journal-title":"Ann. Stat."},{"issue":"2","key":"1982_CR13","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."},{"key":"1982_CR14","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s101070050106","volume":"86","author":"S Ceria","year":"1999","unstructured":"Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Program. 86, 595\u2013614 (1999)","journal-title":"Math. Program."},{"issue":"1","key":"1982_CR15","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10107-012-0613-0","volume":"143","author":"X Chen","year":"2014","unstructured":"Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained $$l_2-l_p$$ minimization. Math. Program. 143(1), 371\u2013383 (2014)","journal-title":"Math. Program."},{"issue":"6","key":"1982_CR16","doi-asserted-by":"publisher","first-page":"2211","DOI":"10.1002\/aic.14418","volume":"60","author":"A Cozad","year":"2014","unstructured":"Cozad, A., Sahinidis, N.V., Miller, D.C.: Learning surrogate models for simulation-based optimization. AIChE J. 60(6), 2211\u20132227 (2014)","journal-title":"AIChE J."},{"key":"1982_CR17","unstructured":"Dong, H., Chen, K., Linderoth, J.: Regularization vs. relaxation: a conic optimization perspective of statistical variable selection. arXiv preprint arXiv:1510.06083 (2015)"},{"key":"1982_CR18","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, 225\u2013236 (2006)","journal-title":"Math. Program."},{"key":"1982_CR19","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":"1982_CR20","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."},{"key":"1982_CR21","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, 1936\u20131941 (2011)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1982_CR22","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":"1982_CR23","unstructured":"Han, S., G\u00f3mez, A.: Compact extended formulations for low-rank functions with indicator variables. arXiv preprint arXiv:2110.14884 (2021)"},{"key":"1982_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01924-w","author":"S Han","year":"2023","unstructured":"Han, S., G\u00f3mez, A., Atamt\u00fcrk, A.: 2x2 convexifications for convex quadratic optimization with indicator variables. Math. Program. (2023). https:\/\/doi.org\/10.1007\/s10107-023-01924-w. (Online First Article)","journal-title":"Math. Program."},{"key":"1982_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01966-0","author":"Z He","year":"2023","unstructured":"He, Z., Han, S., G\u00f3mez, A., Cui, Y., Pang, J.-S.: Comparing solution paths of sparse quadratic minimization with a stieltjes matrix. Math. Program. (2023). https:\/\/doi.org\/10.1007\/s10107-023-01966-0","journal-title":"Math. Program."},{"issue":"4","key":"1982_CR26","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 (JACM) 48(4), 686\u2013701 (2001)","journal-title":"J. ACM (JACM)"},{"key":"1982_CR27","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."},{"key":"1982_CR28","unstructured":"K\u00fc\u00e7\u00fckyavuz, S., Shojaie, A., Manzour, H., Wei, L. , Wu, H.-H.: Consistent second-order conic integer programming for learning Bayesian networks. arXiv preprint arXiv:2005.14346 (2020)"},{"key":"1982_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01845-0","author":"P Liu","year":"2022","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. (2022). https:\/\/doi.org\/10.1007\/s10107-022-01845-0. (Article in Advance)","journal-title":"Math. Program."},{"issue":"1","key":"1982_CR30","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1287\/ijoo.2019.0040","volume":"3","author":"H Manzour","year":"2021","unstructured":"Manzour, H., K\u00fc\u00e7\u00fckyavuz, S., Wu, H.-H., Shojaie, A.: Integer programming for learning directed acyclic graphs from continuous data. INFORMS J. Optim. 3(1), 46\u201373 (2021)","journal-title":"INFORMS J. Optim."},{"key":"1982_CR31","doi-asserted-by":"crossref","unstructured":"Penrose, R.: A generalized inverse for matrices. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol\u00a051, pp. 406\u2013413. Cambridge University Press (1955)","DOI":"10.1017\/S0305004100030401"},{"key":"1982_CR32","unstructured":"POlyhedron Representation Transformation Algorithm. https:\/\/porta.zib.de\/#download. Accessed: 2021-11-20"},{"key":"1982_CR33","doi-asserted-by":"crossref","unstructured":"Wei, L., G\u00f3mez, A., K\u00fc\u00e7\u00fckyavuz, S.: On the convexification of constrained quadratic optimization problems with indicator variables. In: International conference on integer programming and combinatorial optimization, pp. 433\u2013447. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_33"},{"issue":"1\u20132","key":"1982_CR34","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10107-021-01734-y","volume":"192","author":"L Wei","year":"2022","unstructured":"Wei, L., G\u00f3mez, A., K\u00fc\u00e7\u00fckyavuz, S.: Ideal formulations for constrained convex optimization problems with indicator variables. Math. Program. 192(1\u20132), 57\u201388 (2022)","journal-title":"Math. Program."},{"key":"1982_CR35","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, 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-01982-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01982-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01982-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,18]],"date-time":"2024-02-18T23:39:02Z","timestamp":1708299542000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01982-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1982"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01982-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"6 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}