{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:37Z","timestamp":1740109297326,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/R045518\/1"],"award-info":[{"award-number":["EP\/R045518\/1"]}],"id":[{"id":"10.13039\/501100000266","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,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added to tighten the relaxation, is vacuously satisfied and can thus be omitted, and (ii) the number of decision variables in the RLT relaxation can be reduced from <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}} (n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}} (n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Taken together, both observations allow us to reduce computation times by up to several orders of magnitude. Our results can be specialized to indefinite quadratic optimization problems over simplices and extended to non-convex optimization problems over the Cartesian product of two simplices as well as specific classes of polyhedral and non-convex feasible regions. Our numerical experiments illustrate the promising performance of the proposed framework.<\/jats:p>","DOI":"10.1007\/s10107-021-01726-y","type":"journal-article","created":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T15:02:41Z","timestamp":1636124561000},"page":"427-447","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A reformulation-linearization technique for optimization over simplices"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7019-3635","authenticated-orcid":false,"given":"Aras","family":"Selvi","sequence":"first","affiliation":[]},{"given":"Dick","family":"den Hertog","sequence":"additional","affiliation":[]},{"given":"Wolfram","family":"Wiesemann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,5]]},"reference":[{"issue":"10","key":"1726_CR1","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"WP Adams","year":"1986","unstructured":"Adams, W.P., Sherali, H.D.: A tight linearization and an algorithm for zero-one quadratic programming problems. Manag. Sci. 32(10), 1274\u20131290 (1986)","journal-title":"Manag. Sci."},{"issue":"2\u20133","key":"1726_CR2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10898-008-9372-0","volume":"43","author":"KM Anstreicher","year":"2009","unstructured":"Anstreicher, K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43(2\u20133), 471\u2013484 (2009)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1726_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s10107-011-0462-2","volume":"129","author":"X Bao","year":"2011","unstructured":"Bao, X., Sahinidis, N.V., Tawarmalani, M.: Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math. Program. 129(1), 129\u2013157 (2011)","journal-title":"Math. Program."},{"doi-asserted-by":"crossref","unstructured":"Beliakov, G., Abraham, A.: Global optimisation of neural networks using a deterministic hybrid approach. In: Hybrid Information Systems, pp. 79\u201392. Springer (2002)","key":"1726_CR4","DOI":"10.1007\/978-3-7908-1782-9_8"},{"issue":"7","key":"1726_CR5","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.1016\/S0165-1889(03)00109-X","volume":"28","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., Lauprete, G.J., Samarov, A.: Shortfall as a risk measure: properties, optimization and applications. J. Econ. Dyn. Control 28(7), 1353\u20131381 (2004)","journal-title":"J. Econ. Dyn. Control"},{"issue":"4","key":"1726_CR6","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1023\/A:1008369322970","volume":"13","author":"IM Bomze","year":"1998","unstructured":"Bomze, I.M.: On standard quadratic optimization problems. J. Glob. Optim. 13(4), 369\u2013387 (1998)","journal-title":"J. Glob. Optim."},{"key":"1726_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"3","key":"1726_CR8","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1016\/j.ejor.2007.01.055","volume":"191","author":"E De Klerk","year":"2008","unstructured":"De Klerk, E., Den Hertog, D., Elabwabi, G.: On the complexity of optimization over the standard simplex. Eur. J. Oper. Res. 191(3), 773\u2013785 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1726_CR9","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s13675-016-0079-6","volume":"5","author":"M Fampa","year":"2017","unstructured":"Fampa, M., Lee, J., Melo, W.: On global optimization with indefinite quadratics. EURO J. Comput. Optim. 5(3), 309\u2013337 (2017)","journal-title":"EURO J. Comput. Optim."},{"unstructured":"Gurobi Optimization, LLC: Gurobi optimizer reference manual (2020)","key":"1726_CR10"},{"issue":"2","key":"1726_CR11","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/S003614299630587X","volume":"35","author":"JS Hesthaven","year":"1998","unstructured":"Hesthaven, J.S.: From electrostatics to almost optimal nodal sets for polynomial interpolation in a simplex. SIAM J. Numer. Anal. 35(2), 655\u2013676 (1998)","journal-title":"SIAM J. Numer. Anal."},{"key":"1726_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0015-5","volume-title":"Introduction to Global Optimization","author":"R Horst","year":"2000","unstructured":"Horst, R., Pardalos, P., Van Thoai, N.: Introduction to Global Optimization. Springer, Berlin (2000)"},{"issue":"1","key":"1726_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1021765131316","volume":"103","author":"R Horst","year":"1999","unstructured":"Horst, R., Thoai, N.V.: DC programming: overview. J. Optim. Theor. Appl. 103(1), 1\u201343 (1999)","journal-title":"J. Optim. Theor. Appl."},{"unstructured":"IBM ILOG CPLEX: V12.6: User\u2019s Manual for CPLEX (2014)","key":"1726_CR14"},{"issue":"2","key":"1726_CR15","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10898-006-9005-4","volume":"36","author":"L Liberti","year":"2006","unstructured":"Liberti, L., Pantelides, C.C.: An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Glob. Optim. 36(2), 161\u2013189 (2006)","journal-title":"J. Glob. Optim."},{"unstructured":"L\u00f6fberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference. Taipei, Taiwan (2004)","key":"1726_CR16"},{"issue":"1","key":"1726_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Math. Program. 10(1), 147\u2013175 (1976)","journal-title":"Math. Program."},{"unstructured":"Mezzadri, F.: How to generate random matrices from the classical compact groups. arXiv preprint arXiv:math-ph\/0609050 (2006)","key":"1726_CR18"},{"issue":"1","key":"1726_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10898-012-9874-7","volume":"57","author":"R Misener","year":"2013","unstructured":"Misener, R., Floudas, C.A.: GloMIQO: global mixed-integer quadratic optimizer. J. Glob. Optim. 57(1), 3\u201350 (2013)","journal-title":"J. Glob. Optim."},{"issue":"2\u20133","key":"1726_CR20","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s10898-014-0166-2","volume":"59","author":"R Misener","year":"2014","unstructured":"Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous\/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2\u20133), 503\u2013526 (2014)","journal-title":"J. Glob. Optim."},{"unstructured":"MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual (version 9.0) (2019)","key":"1726_CR21"},{"key":"1726_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Springer, Berlin (2004)"},{"unstructured":"Park, J.: Sparsity-preserving difference of positive semidefinite matrix representation of indefinite matrices. arXiv preprint arXiv:1609.06762 (2016)","key":"1726_CR23"},{"key":"1726_CR24","volume-title":"A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems","author":"HD Sherali","year":"2013","unstructured":"Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Springer, Berlin (2013)"},{"issue":"1\u20134","key":"1726_CR25","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1023\/A:1013819515732","volume":"22","author":"HD Sherali","year":"2002","unstructured":"Sherali, H.D., Fraticelli, B.M.: Enhancing RLT relaxations via a new class of semidefinite cuts. J. Glob. Optim. 22(1\u20134), 233\u2013261 (2002)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1726_CR26","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF00121304","volume":"2","author":"HD Sherali","year":"1992","unstructured":"Sherali, H.D., Tuncbilek, C.H.: A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Glob. Optim. 2(1), 101\u2013112 (1992)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1726_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01100203","volume":"7","author":"HD Sherali","year":"1995","unstructured":"Sherali, H.D., Tuncbilek, C.H.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim. 7(1), 1\u201331 (1995)","journal-title":"J. Glob. Optim."},{"unstructured":"The MathWorks Inc.: MATLAB R2018b (2014)","key":"1726_CR28"},{"unstructured":"Zhen, J., De Moor, D., Den Hertog, D.: An extension of the reformulation-linearization technique to nonlinear optimization problems. Working Paper (2021)","key":"1726_CR29"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01726-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01726-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01726-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T01:05:06Z","timestamp":1674349506000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01726-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,5]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1726"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01726-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,11,5]]},"assertion":[{"value":"6 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}