{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:27:41Z","timestamp":1775003261326,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004770","name":"Universit\u00e0 degli Studi di Parma","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004770","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The convex envelope value for a given function <jats:italic>f<\/jats:italic> over a region <jats:italic>X<\/jats:italic> at some point <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{x}\\in X$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>X<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be derived by searching for the largest value at that point among affine underestimators of <jats:italic>f<\/jats:italic> over <jats:italic>X<\/jats:italic>. This can be computed by solving a maximin problem, whose exact computation, however, may be a hard task. In this paper we show that by relaxation of the inner minimization problem, duality, and, in particular, by an enlargement of the class of underestimators (thus, not only affine ones) an easier derivation of good convex understimating functions, which can also be proved to be convex envelopes in some cases, is possible. The proposed approach is mainly applied to the derivation of convex underestimators (in fact, in some cases, convex envelopes) in the quadratic case. However, some results are also presented for polynomial, ratio of polynomials, and some other separable functions over regions defined by similarly defined separable functions.<\/jats:p>","DOI":"10.1007\/s10589-023-00534-8","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T20:01:51Z","timestamp":1697486511000},"page":"475-499","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A new technique to derive tight convex underestimators (sometimes envelopes)"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7138-8653","authenticated-orcid":false,"given":"M.","family":"Locatelli","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"534_CR1","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01096720","volume":"4","author":"CD Maranas","year":"1994","unstructured":"Maranas, C.D., Floudas, C.A.: Global minimum potential energy conformations of small molecules. J. Glob. Optim. 4, 135\u2013170 (1994)","journal-title":"J. Glob. Optim."},{"key":"534_CR2","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10898-004-2704-9","volume":"32","author":"CA Meyer","year":"2005","unstructured":"Meyer, C.A., Floudas, C.A.: Convex underestimation of twice continuously differentiable functions by piecewise quadratic perturbation: spline $$\\alpha $$BB underestimators. J. Glob. Optim. 32, 221\u2013258 (2005)","journal-title":"J. Glob. Optim."},{"key":"534_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10898-004-6455-4","volume":"30","author":"IG Akrotirianakis","year":"2004","unstructured":"Akrotirianakis, I.G., Floudas, C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Glob. Optim. 30, 367\u2013390 (2004)","journal-title":"J. Glob. Optim."},{"key":"534_CR4","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10898-005-0936-y","volume":"33","author":"Y Zhu","year":"2005","unstructured":"Zhu, Y., Kuno, T.: A global optimization method, QBB, for twice-differentiable nonconvex optimization problem. J. Glob. Optim. 33, 435\u2013464 (2005)","journal-title":"J. Glob. Optim."},{"key":"534_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10898-011-9685-2","volume":"52","author":"A Bompadre","year":"2012","unstructured":"Bompadre, A., Mitsos, A.: Convergence rate of McCormick relaxations. J. Glob. Optim. 52, 1\u201328 (2012)","journal-title":"J. Glob. Optim."},{"key":"534_CR6","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s10898-011-9664-7","volume":"51","author":"JK Scott","year":"2011","unstructured":"Scott, J.K., Stuber, M.D., Barton, P.I.: Generalized McCormick relaxations. J. Glob. Optim. 51, 569\u2013606 (2011)","journal-title":"J. Glob. Optim."},{"key":"534_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-005-0580-9","volume":"103","author":"CA Meyer","year":"2005","unstructured":"Meyer, C.A., Floudas, C.A.: Convex envelopes for edge-concave functions. Math. Program. 103, 207\u2013224 (2005)","journal-title":"Math. Program."},{"key":"534_CR8","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1023\/A:1008217604285","volume":"10","author":"A Rikun","year":"1997","unstructured":"Rikun, A.: A convex envelope formula for multilinear functions. J. Glob. Optim. 10, 425\u2013437 (1997)","journal-title":"J. Glob. Optim."},{"key":"534_CR9","first-page":"563","volume-title":"Frontiers in Global Optimization","author":"F Tardella","year":"2003","unstructured":"Tardella, F.: On the existence of polyhedral convex envelopes. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization, pp. 563\u2013574. Kluwer Academic Publishers, Dordrecht (2003)"},{"key":"534_CR10","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s11590-007-0065-2","volume":"2","author":"F Tardella","year":"2008","unstructured":"Tardella, F.: Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2, 363\u2013375 (2008)","journal-title":"Optim. Lett."},{"key":"534_CR11","unstructured":"De Rosa, A., Khajavirad, A.: Explicit convex hull description of bivariate quadratic sets with indicator variables. https:\/\/arxiv.org\/pdf\/2208.08703.pdf"},{"issue":"3","key":"534_CR12","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1137\/07069359X","volume":"19","author":"M Jach","year":"2008","unstructured":"Jach, M., Michaels, D., Weismantel, R.: The convex envelope of ($$n$$-1)-convex functions. SIAM J. Optim. 19(3), 1451\u20131466 (2008)","journal-title":"SIAM J. Optim."},{"key":"534_CR13","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10898-011-9747-5","volume":"51","author":"A Khajavirad","year":"2012","unstructured":"Khajavirad, A., Sahinidis, N.V.: Convex envelopes of products of convex and component-wise concave functions. J. Glob. Optim. 51, 391\u2013409 (2012)","journal-title":"J. Glob. Optim."},{"key":"534_CR14","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s10107-011-0496-5","volume":"137","author":"A Khajavirad","year":"2013","unstructured":"Khajavirad, A., Sahinidis, N.V.: Convex envelopes generated from finitely many compact convex sets. Math. Program. 137, 371\u2013408 (2013)","journal-title":"Math. Program."},{"key":"534_CR15","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s10898-016-0409-5","volume":"65","author":"M Locatelli","year":"2016","unstructured":"Locatelli, M.: Non polyhedral convex envelopes for 1-convex functions. J. Glob. Optim. 65, 637\u2013655 (2016)","journal-title":"J. Glob. Optim."},{"key":"534_CR16","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10898-018-0626-1","volume":"72","author":"M Locatelli","year":"2018","unstructured":"Locatelli, M.: Convex envelopes of bivariate functions through the solution of KKT systems. J. Glob. Optim. 72, 277\u2013303 (2018)","journal-title":"J. Glob. Optim."},{"key":"534_CR17","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/s10107-017-1138-3","volume":"169","author":"TT Nguyen","year":"2018","unstructured":"Nguyen, T.T., Richard, J.-P.P., Tawarmalani, M.: Deriving convex hulls through lifting and projection. Math. Program. 169, 377\u2013415 (2018)","journal-title":"Math. Program."},{"key":"534_CR18","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s10107-012-0581-4","volume":"138","author":"M Tawarmalani","year":"2013","unstructured":"Tawarmalani, M., Richard, J.-P.P., Xiong, C.: Explicit convex and concave envelopes through polyhedral subdivisions. Math. Program. 138, 531\u2013577 (2013)","journal-title":"Math. Program."},{"key":"534_CR19","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF00121658","volume":"9","author":"T Matsui","year":"1996","unstructured":"Matsui, T.: NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9, 113\u2013119 (1996)","journal-title":"J. Glob. Optim."},{"issue":"5","key":"534_CR20","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/j.orl.2017.06.008","volume":"45","author":"W Ben-Ameur","year":"2017","unstructured":"Ben-Ameur, W., Ouorou, A., Wang, G.: Convex and concave envelopes: revisited and new perspectives. Oper. Res. Lett. 45(5), 421\u2013426 (2017)","journal-title":"Oper. Res. Lett."},{"key":"534_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1025794313696","volume":"26","author":"S Kim","year":"2003","unstructured":"Kim, S., Kojima, M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26, 143\u2013154 (2003)","journal-title":"Comput. Optim. Appl."},{"key":"534_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-013-0710-8","volume":"143","author":"A Ben-Tal","year":"2014","unstructured":"Ben-Tal, A., Den Hertog, D.: Hidden conic quadratic representation of some nonconvex quadratic optimization problems. Math. Program. 143, 1\u201329 (2014)","journal-title":"Math. Program."},{"key":"534_CR23","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10107-020-01560-8","volume":"191","author":"AL Wang","year":"2022","unstructured":"Wang, A.L., Kilin\u00e7-Karzan, F.: The generalized trust region subproblem: solution complexity and convex hull results. Math. Program. 191, 445\u2013486 (2022)","journal-title":"Math. Program."},{"key":"534_CR24","unstructured":"Hsia, Y., Sheu, R.-L.: Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity. http:\/\/arxiv.org\/abs\/1312.1398"},{"key":"534_CR25","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s10107-013-0716-2","volume":"147","author":"V Jeyakumar","year":"2014","unstructured":"Jeyakumar, V., Li, G.Y.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. 147, 171\u2013206 (2014)","journal-title":"Math. Program."},{"issue":"3","key":"534_CR26","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1137\/050644471","volume":"17","author":"A Beck","year":"2006","unstructured":"Beck, A., Eldar, Y.C.: Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM J. Optim. 17(3), 844\u2013860 (2006)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"534_CR27","first-page":"635","volume":"15","author":"R Laraki","year":"2008","unstructured":"Laraki, R., Lasserre, J.B.: Computing uniform convex approximations for convex envelopes and convex hulls. J. Convex Anal. 15(3), 635\u2013654 (2008)","journal-title":"J. Convex Anal."},{"key":"534_CR28","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10107-011-0499-2","volume":"137","author":"AA Ahmadi","year":"2013","unstructured":"Ahmadi, A.A., Olshevsky, A., Parrilo, P.A., Tsitsiklis, J.N.: NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137, 453\u2013476 (2013)","journal-title":"Math. Program."},{"key":"534_CR29","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10107-008-0240-y","volume":"122","author":"JW Helton","year":"2010","unstructured":"Helton, J.W., Nie, J.: Semidefinite representation of convex sets. Math. Program. 122, 21\u201364 (2010)","journal-title":"Math. Program."},{"key":"534_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10898-012-9974-4","volume":"56","author":"JB Lasserre","year":"2013","unstructured":"Lasserre, J.B., Thanh, T.P.: Convex underestimators of polynomials. J. Glob. Optim. 56, 1\u201325 (2013)","journal-title":"J. Glob. Optim."},{"key":"534_CR31","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Den Hertog, D., Laurent, M.: Hidden Convexity in Partially Separable Optimization. Technical Report 2011\u201370. Tilburg University, Center for Economic Research (2011)","DOI":"10.2139\/ssrn.1865208"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00534-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00534-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00534-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T19:09:19Z","timestamp":1707764959000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00534-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["534"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00534-8","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"16 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no competing interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}